  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.
