Combinatorial optimization problems arise in a wide range of applications
from diverse domains. Many of these problems are NP-hard and designing
efficient heuristics for them requires considerable time and experimentation.
On the other hand, the number of optimization problems in the industry
continues to grow. In recent years, machine learning techniques have been
explored to address this gap. We propose a framework for leveraging machine
learning techniques to scale-up exact combinatorial optimization algorithms. In
contrast to the existing approaches based on deep-learning, reinforcement
learning and restricted Boltzmann machines that attempt to directly learn the
output of the optimization problem from its input (with limited success), our
framework learns the relatively simpler task of pruning the elements in order
to reduce the size of the problem instances. In addition, our framework uses
only interpretable learning models based on intuitive features and thus the
learning process provides deeper insights into the optimization problem and the
instance class, that can be used for designing better heuristics. For the
classical maximum clique enumeration problem, we show that our framework can
prune a large fraction of the input graph (around 99 % of nodes in case of
sparse graphs) and still detect almost all of the maximum cliques. This results
in several fold speedups of state-of-the-art algorithms. Furthermore, the model
used in our framework highlights that the chi-squared value of neighborhood
degree has a statistically significant correlation with the presence of a node
in a maximum clique, particularly in dense graphs which constitute a
significant challenge for modern solvers. We leverage this insight to design a
novel heuristic for this problem outperforming the state-of-the-art. Our
heuristic is also of independent interest for maximum clique detection and
enumeration.

该研究提出了一种基于机器学习的框架来扩大组合优化算法，并使用可解释的学习模型来提供更深层次的洞见，以设计更好的启发式方法，在最大团枚举问题中展示了该框架的性能，并从中获得启示设计了一种新的启发式方法。

组合优化中的细粒度搜索空间剪枝和启发式学习

Learning fine-grained search space pruning and heuristics for  combinatorial optimization

We propose a multi-stage learning approach for pruning the search space of
maximum clique enumeration, a fundamental computationally difficult problem
arising in various network analysis tasks. In each stage, our approach learns
the characteristics of vertices in terms of various neighborhood features and
leverage them to prune the set of vertices that are likely not contained in any
maximum clique. Furthermore, we demonstrate that our approach is domain
independent -- the same small set of features works well on graph instances
from different domain. Compared to the state-of-the-art heuristics and
preprocessing strategies, the advantages of our approach are that (i) it does
not require any estimate on the maximum clique size at runtime and (ii) we
demonstrate it to be effective also for dense graphs. In particular, for dense
graphs, we typically prune around 30 \% of the vertices resulting in speedups
of up to 53 times for state-of-the-art solvers while generally preserving the
size of the maximum clique (though some maximum cliques may be lost). For large
real-world sparse graphs, we routinely prune over 99 \% of the vertices
resulting in several tenfold speedups at best, typically with no impact on
solution quality.

本文提出一种多阶段学习方法，用于枚举最大团子集的搜索空间修剪，并展示其在不同领域图实例上的良好表现。