Constraint programming is known for being an efficient approach for solving
combinatorial problems. Important design choices in a solver are the branching
heuristics, which are designed to lead the search to the best solutions in a
minimum amount of time. However, developing these heuristics is a
time-consuming process that requires problem-specific expertise. This
observation has motivated many efforts to use machine learning to automatically
learn efficient heuristics without expert intervention. To the best of our
knowledge, it is still an open research question. Although several generic
variable-selection heuristics are available in the literature, the options for
a generic value-selection heuristic are more scarce. In this paper, we propose
to tackle this issue by introducing a generic learning procedure that can be
used to obtain a value-selection heuristic inside a constraint programming
solver. This has been achieved thanks to the combination of a deep Q-learning
algorithm, a tailored reward signal, and a heterogeneous graph neural network
architecture. Experiments on graph coloring, maximum independent set, and
maximum cut problems show that our framework is able to find better solutions
close to optimality without requiring a large amounts of backtracks while being
generic.

本文提出了一种结合深度 Q 学习算法、定制奖励信号和异构图神经网络架构的通用学习过程，用于在约束编程求解器中获取值选择启发式，并在图着色、最大独立集和最大割问题上进行实验，表明该框架能够在通用的前提下，找到更接近最优解的更好解决方案，而无需大量回溯。

在通用约束编程求解器内训练深度 Q 学习代理

Training a Deep Q-Learning Agent Inside a Generic Constraint Programming Solver

When combined properly, search techniques can reveal the full potential of
sophisticated branching heuristics. We demonstrate this observation on the
well-known class of random 3-SAT formulae. First, a new branching heuristic is
presented, which generalizes existing work on this class. Much smaller search
trees can be constructed by using this heuristic. Second, we introduce a
variant of discrepancy search, called ALDS. Theoretical and practical evidence
support that ALDS traverses the search tree in a near-optimal order when
combined with the new heuristic. Both techniques, search and heuristic, have
been implemented in the look-ahead solver march. The SAT 2009 competition
results show that march is by far the strongest complete solver on random k-SAT
formulae.

本文介绍了一种新的分支启发式方法和一种称作 ALDS 的搜索技术。在 SAT 2009 竞赛上的表现表明，这两种技术结合在一起可以极大地降低搜索树的大小。

随机 3-SAT 问题的搜索与启发式算法的共生

Symbiosis of Search and Heuristics for Random 3-SAT

Complete tree search is a highly effective method for tackling MIP problems,
and over the years, a plethora of branching heuristics have been introduced to
further refine the technique for varying problems. Recently, portfolio
algorithms have taken the process a step further, trying to predict the best
heuristic for each instance at hand. However, the motivation behind algorithm
selection can be taken further still, and used to dynamically choose the most
appropriate algorithm for each encountered subproblem. In this paper we
identify a feature space that captures both the evolution of the problem in the
branching tree and the similarity among subproblems of instances from the same
MIP models. We show how to exploit these features to decide the best time to
switch the branching heuristic and then show how such a system can be trained
efficiently. Experiments on a highly heterogeneous collection of MIP instances
show significant gains over the pure algorithm selection approach that for a
given instance uses only a single heuristic throughout the search.

本文提出了一种选择最适合子问题的启发式算法的方法，并实验验证在各种 MIP 示例中，该方法相较于传统的使用单一启发式算法的算法选择方法，在目标值上表现更优。