Lagrangian relaxation is a versatile mathematical technique employed to relax
constraints in an optimization problem, enabling the generation of dual bounds
to prove the optimality of feasible solutions and the design of efficient
propagators in constraint programming (such as the weighted circuit
constraint). However, the conventional process of deriving Lagrangian
multipliers (e.g., using subgradient methods) is often computationally
intensive, limiting its practicality for large-scale or time-sensitive
problems. To address this challenge, we propose an innovative unsupervised
learning approach that harnesses the capabilities of graph neural networks to
exploit the problem structure, aiming to generate accurate Lagrangian
multipliers efficiently. We apply this technique to the well-known Held-Karp
Lagrangian relaxation for the travelling salesman problem. The core idea is to
predict accurate Lagrangian multipliers and to employ them as a warm start for
generating Held-Karp relaxation bounds. These bounds are subsequently utilized
to enhance the filtering process carried out by branch-and-bound algorithms. In
contrast to much of the existing literature, which primarily focuses on finding
feasible solutions, our approach operates on the dual side, demonstrating that
learning can also accelerate the proof of optimality. We conduct experiments
across various distributions of the metric travelling salesman problem,
considering instances with up to 200 cities. The results illustrate that our
approach can improve the filtering level of the weighted circuit global
constraint, reduce the optimality gap by a factor two for unsolved instances up
to a timeout, and reduce the execution time for solved instances by 10%.

应用图神经网络预测准确的 Lagrangian 乘子，作为生成 Held-Karp 松弛界限的初始值，并通过这种方法改进分支界定算法的过滤过程，从而加速优化证明的过程。