Hybrid algorithm improves solving tough optimization problems efficiently
HyCO: A Hybrid Neural Solver for Combinatorial Optimization
Machine LearningArtificial Intelligence
Summary
Combinatorial optimization involves finding the best arrangement from many possibilities, which is very hard for computers. The authors found that two common AI methods struggle in different ways: one makes small errors early but gets worse over time, while the other avoids error buildup but slows down as the problem gets smaller. They created a hybrid approach that starts with the first method and then switches to the second at just the right moment. This switch lowers errors and speeds up finding good solutions, as shown both theoretically and in tests. Their technique includes a smart way to decide when to switch, making the approach practical.
Combinatorial optimizationReinforcement learningDiffusion modelsHybrid algorithmsRegret analysisError scalingPolicy entropyAdaptive triggeringTrajectoryOptimization regret
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.