Summary
Combinatorial optimization problems involve finding the best choice among many possible options, which can be very hard for computers. The paper shows that two common AI techniques, reinforcement learning and diffusion models, have strengths and weaknesses at different stages of solving these problems. The authors propose a new method called HyCO that combines both approaches, starting with reinforcement learning and switching to diffusion models when appropriate. They prove this hybrid method performs better than using either technique alone and create a system to decide the best time to switch during solving. Experiments confirm that HyCO consistently improves the quality of solutions.
What this means in practice
- •For logistics planners: Improve route and delivery planning algorithms with a hybrid AI approach that reduces errors over long decision sequences.
- •For manufacturing schedulers: Use a combined reinforcement learning and diffusion model method to generate more efficient production schedules by minimizing compounded planning mistakes.
Authors
Yuheng Li, Di Yang, Haipeng Chen, Yanhai Xiong
Abstract
Sequential reinforcement learning (RL) solvers and global diffusion model (DM) solvers for neural combinatorial optimization exhibit complementary failure modes under an optimization-regret view. The former enjoys small marginal regret in the early construction stage, but suffers from horizon-wise compounding errors with super-linear regret growth; the latter avoids horizon compounding but incurs linear or sublinear regret w.r.t. the dimension of the remaining unsolved subspace. We propose Hybrid Neural Solver for Combinatorial Optimization (HyCO), a hybrid inference algorithm that constructs a solution prefix with an RL solver and adaptively switches to a conditional DM to complete the remaining decisions. To characterize why such hybridization helps, when to trigger the handover, and how to realize it in practice, we first develop a unified error-scaling theoretical framework and prove that, under explicit error-scaling assumptions, i) the hybrid structure achieves strictly lower expected regret than either backbone alone, and ii) there exists a unique optimal trigger step that minimizes the hybrid regret. We then design a lightweight adaptive trigger that combines policy entropy and RL-DM disagreement to detect trajectory-level signals of the regime shift as a practical proxy, since the optimal trigger step is defined at the expected-regret level and is not directly computable on individual trajectories. Experimental results on diverse benchmarks demonstrate that HyCO achieves consistent improvements over both backbones and support the empirical effectiveness of adaptive triggering.