NLD4CO: Neural Langevin Dynamics for Combinatorial Optimization

Langevin Dynamics (LD) provides a principled framework for solving combinatorial optimization problems (COPs) via gradient-guided stochastic search. However, classical LD faces two bottlenecks: 1) the utilization of uniform initialization may affect its convergence speed; 2) when applied to COPs such as routing problems that cannot be naturally formulated as Quadratic Unconstrained Binary Optimization (QUBO), classical LD suffers from slow convergence and inferior performance compared to existing learning-to-construct (L2C) methods, as it requires manually designed discrete proposals for updates. These proposals are typically local and induce abrupt transitions in the solution space, hindering escape from local optima and degrading performance. To address these issues, we propose NLD4CO, a unified framework that synergizes data-driven learning with LD. It introduces two instantiations: explicit-gradient (EG) and implicit-gradient (IG). NLD-EG accelerates sampling efficiency for energy-based problems via neural warm-start initialization. NLD-IG utilizes the corrective direction predicted by a consistency model as an implicit score function to guide the search, making structured, globally coordinated transitions for general COPs. Extensive evaluations on MIS, MWIS, TSP, and CVRP demonstrate that NLD4CO achieves SOTA performance, delivering superior solution quality with competitive or lower runtime.