Constraint Optimization Problems (COP) pose intricate challenges in
combinatorial problems usually addressed through Branch and Bound (B\&B)
methods, which involve maintaining priority queues and iteratively selecting
branches to search for solutions. However, conventional approaches take a
considerable amount of time to find optimal solutions, and it is also crucial
to quickly identify a near-optimal feasible solution in a shorter time. In this
paper, we aim to investigate the effectiveness of employing a depth-first
search algorithm for solving COP, specifically focusing on identifying optimal
or near-optimal solutions within top $n$ solutions. Hence, we propose a novel
heuristic neural network algorithm based on MCTS, which, by simultaneously
conducting search and training, enables the neural network to effectively serve
as a heuristic during Backtracking. Furthermore, our approach incorporates
encoding COP problems and utilizing graph neural networks to aggregate
information about variables and constraints, offering more appropriate
variables for assignments. Experimental results on stochastic COP instances
demonstrate that our method identifies feasible solutions with a gap of less
than 17.63% within the initial 5 feasible solutions. Moreover, when applied to
attendant Constraint Satisfaction Problem (CSP) instances, our method exhibits
a remarkable reduction of less than 5% in searching nodes compared to
state-of-the-art approaches.

该论文探讨了针对约束优化问题，采用深度优先搜索算法以在前 n 个解中寻找最优或近似最优解，并提出了一种基于 MCTS 的新型启发式神经网络算法，结合编码约束优化问题和利用图神经网络聚合变量和约束信息的方法，实验结果表明该方法能够快速找到初始的 5 个可行解中与最优解间隔小于 17.63% 的解，并在应用于约束满足问题时，与最先进方法相比，搜索节点数减少不到 5%。