PaperlayerView exact revision on arXiv

Source-linked AI summary

HyCO: A Hybrid Neural Solver for Combinatorial Optimization

Yuheng Li, Di Yang, Haipeng Chen, Yanhai Xiong

arXiv:2609.07990v1cs.LGcs.AI

TL;DR

Sequential RL and global diffusion solvers have different regret-scaling behaviors, raising the question of how to combine them and choose a handover point. HyCO uses RL for a solution prefix and a conditional diffusion model for completion, with an adaptive trigger; it improves consistently over both backbones on TSP, MIS, and OP.

  • Problem

    Sequential RL and global diffusion solvers exhibit complementary regret behavior, motivating a principled way to combine them and select a handover point.

    Source: §1 · pp. 1–2

  • Method

    HyCO constructs a solution prefix with RL, hands completion to a conditional diffusion model, and uses policy entropy plus RL–DM disagreement as adaptive trigger signals.

    Source: §1 · p. 2

  • Results

    HyCO consistently improves over both backbones on TSP, MIS, and OP, with oracle validation and ablations supporting the adaptive trigger’s effectiveness.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    Under explicit error-scaling assumptions, a single RL-to-DM handover achieves strictly lower expected regret than either backbone and has a unique regret-minimizing trigger step.

    Source: §1 · p. 2

    The regret guarantees rely on a Lipschitz continuous relaxed objective and endpoint marginal-regret inequalities.

    Source: §4 · pp. 4–5

Abstract

from arXiv · show

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.

1 Introduction

RL and diffusion-model solvers have complementary regret patterns, motivating a hybrid that switches from RL construction to conditional diffusion completion. HyCO formalizes the handover and uses adaptive signals to detect when to switch.

1 Introduction

  • Neural solvers address scale challenges in NP-hard combinatorial optimization, where exact methods such as Concorde have exponential complexity.The paper frames RL construction solvers and global diffusion solvers as two representative neural approaches.Source: §1 · p. 1
  • RL has typically small early marginal regret but suffers super-linear horizon-wise error accumulation, while conditional DM regret stays constant or decreases as the prefix grows.The growing prefix constrains the remaining subspace, providing a structural crossing point for the handover.Source: §1 · p. 2
  • The proposed hybrid constructs a solution prefix with RL, then hands remaining decisions to a conditional DM; its trigger uses trajectory-level proxies because the optimal step is not directly observable there.The two proxies are RL policy entropy and disagreement between RL’s local preference and the DM-induced global prior.Source: §1 · p. 2
  • Under explicit assumptions, HyCO’s single RL-to-DM handover achieves lower expected regret than either backbone, and experiments show consistent improvements on TSP, MIS, and OP.Its adaptive trigger combines policy entropy and RL–DM disagreement; oracle validation and ablations support the trigger’s effectiveness.Source: §1 · p. 2

2 Related Work

Related work covers sequential RL solvers and global, non-autoregressive methods for combinatorial optimization. The paper distinguishes their limitations as horizon-wise error accumulation versus regret tied to the full solution-space dimension.

RL Solvers

  • RL solvers build solutions sequentially; work spans Pointer Networks [4], Transformer architectures, and later graph, learning, decoder, and meta-heuristic extensions.Despite efficiency, these solvers can accumulate horizon-wise errors and incur super-linear regret as problem scale grows.Source: §2 · p. 3

2 Related Work

  • The two research lines trade sequential error accumulation against the difficulty of generating high-dimensional solutions globally.The cited work motivates considering a hybrid rather than relying exclusively on either inference paradigm.Source: §2 · p. 3

Heatmap and Diffusion Models for CO

  • Global methods include heatmap approaches [31] [32], GCN edge predictions [33], and diffusion models for TSP [7] and graph-native DIFUSCO [8].These methods avoid horizon compounding but incur regret governed by solution-space dimensionality, making high-dimensional generation from scratch less precise.Source: §2 · p. 3

3 Preliminaries

The preliminaries describe RL as stepwise policy-based construction and diffusion models as holistic generation through iterative denoising. A diffusion model may condition completion on an existing solution prefix.

3.1 Sequential Inference with RL Solvers

  • RL inference selects feasible actions sequentially from a learned policy, with greedy decoding as one option; early choices constrain later decisions and local errors can compound.The method requires a linear number of forward passes relative to solution length.Source: §3.1 · p. 3

3.2 Global Inference with Diffusion Models

  • A diffusion model generates a complete solution holistically through a discrete denoising process and can condition generation on prior information such as a tour prefix.For TSP, the solution may be represented as a binary adjacency matrix whose entries are gradually corrupted and then denoised.Source: §3.2 · p. 3
  • Diffusion inference starts from random noise and iteratively samples less noisy states until producing a clean solution, using the current state and conditioning prefix.The reverse process is represented by a learned transition distribution and is described as capturing complex global dependencies.Source: §3.2 · p. 3

4 Unified Regret Framework and Optimal Trigger Analysis

The framework compares RL and conditional-DM regret under a unified metric, then analyzes how their different scaling behaviors determine a handover. Under stated conditions, it yields a unique regret-minimizing trigger and a hybrid with lower expected regret than either backbone.

4 Unified Regret Framework and Optimal Trigger Analysis

  • The unified regret metric compares expected objectives under a solver output distribution and an optimal target distribution; the RL and conditional-DM forms specialize this comparison to their respective outputs.The analysis assumes a Lipschitz continuous relaxation of the objective and connects diffusion-model training KL divergence to regret.Source: §4 · p. 4
  • Conditional-DM regret scales with the square root of the unsolved-subspace dimension under a per-dimension score-matching error condition.The unsolved dimension counts decision variables not fixed by the prefix.Source: §4 · p. 4
  • RL regret exhibits super-linear scaling with decision horizon, expressed as O(h^α) in the framework’s comparison of scaling behaviors.The passage motivates this scaling through horizon-wise error accumulation and standard finite-horizon RL regret bounds.Source: §4 · pp. 4–5
  • The hybrid assigns h decisions to RL and the remaining d − h variables to the conditional DM, producing a unique trigger step under the stated scaling and boundary conditions.At the optimum, the marginal regrets balance: r_RL(τ*) = r_DM(τ*).Source: §4 · p. 5
  • Under those conditions, the hybrid has strictly lower expected regret than either pure RL or pure DM, but the optimal trigger is not directly observable on an individual trajectory.That gap motivates a practical lightweight trigger in the following section.Source: §4 · pp. 4–5

5 HyCO: Single-Trigger Hybrid Inference Algorithm

HyCO makes one RL-to-DM handover, using trajectory-level signals as a proxy for the theoretically optimal trigger. Its pipeline combines a corrected RL continuation with full diffusion proposals.

5 HyCO: Single-Trigger Hybrid Inference Algorithm

  • At most one RL-to-DM handover achieves lower regret than either backbone under the analysis, with the theoretical trigger at equal marginal regret.HyCO uses a lightweight trigger as a trajectory-level proxy for that expected-regret balance.Source: §5 · p. 5, §5.2 · p. 6

5.1 Single-Trigger inference pipeline

  • At the trigger, HyCO corrects the RL path’s next action using a diffusion candidate while also generating full diffusion proposals, then returns the best solution.The parallel RL continuation provides a valid-solution fallback if diffusion produces no feasible or high-quality completion.Source: §5.1 · pp. 5–6

5.2 Lightweight trigger as a trigger proxy

  • HyCO triggers when either policy entropy or RL–DM disagreement is large, because the marginal-regret balance cannot be evaluated directly on an individual trajectory.High entropy signals no clearly dominant action; large disagreement signals that RL’s preferred action conflicts with the DM’s global preference.Source: §5.2 · p. 6
  • To estimate disagreement efficiently, HyCO probes the DM on RL’s Top-M candidate prefixes, scores their structural consistency, and compares the restricted RL distribution with a diffusion prior using KL divergence.The energy score masks to edges in each partial tour, measuring DM confidence in those proposed connections.Source: §5.2 · p. 6

6 Experiments

Experiments evaluate HyCO on TSP, MIS, and Orienteering Problem benchmarks, comparing solution quality and trigger behavior. HyCO improves over both backbones, and its adaptive trigger tracks instance-wise oracle triggers closely.

6 Experiments

  • The evaluation covers 2D Euclidean TSP, MIS, and OP at multiple scales, and tests both solution quality against RL and DM backbones and trigger alignment against oracle grid search.TSP instances have 50, 100, 500, or 1000 nodes; metrics include average tour length, optimality gap, and average solution time.Source: §6 · p. 7, §6.1 · p. 7

6.1 Experimental Settings

  • The experiments compare HyCO with exact and heuristic solvers and learning-based RL and DM methods, using public TSP datasets and Concorde-derived optimal solutions for training and gap calculation.The conditional DM is adapted from DIFUSCO’s GNN architecture and trained with masked loss and curriculum learning for prefix-conditioned completion.Source: §6.1 · p. 7

6.2 Performance Gains over Backbone Solvers

  • HyCO reduces the TSP-50 RL gap from 1.76% / 0.64% to 0.03%, the MIS gap by 6.12% over LWD, and OP gaps by 8.21% over AM and 3.53% over DM.On MIS, it also improves over prefix_Coexpander by an average of 1.75% under the same small candidate budget.Source: §6.2 · pp. 8–9, Table 1 · p. 8, Table 3 · p. 9

6.3 Oracle Trigger Validation: Adaptive vs. Instance-wise Best Fixed

  • Across benchmarks, adaptive trigger locations are within 2.5% normalized step distance of the instance-wise oracle, with reported relative cost differences from 0.036% to 2.330%.The larger deviations on TSP-500 and ER-700–800 suggest greater sensitivity to small trigger shifts on larger or structurally more complex instances.Source: §6.3 · p. 9, Table 4 · p. 9

7 Conclusion

HyCO combines sequential RL construction with conditional DM completion and uses entropy and model disagreement to proxy the regret-balanced handover. Experiments show improvements over both backbones, while broader solver pairings remain a future direction.

7 Conclusion

  • HyCO combines sequential RL construction with conditional DM completion, using policy entropy and model disagreement as trajectory-level proxies for the regime transition.Experiments on TSP, MIS, and OP show consistent improvement over both backbones; oracle validation and ablations support the adaptive dual-signal trigger.Source: §7 · pp. 9–10
  • The authors suggest complementary error scaling may extend to other solver pairings with analogous properties, leaving that generalization for future work.The theoretical analysis in this paper focuses on RL and DM backbones.Source: §7 · pp. 9–10

Technical Appendices and Supplementary Material

The appendix justifies the Lipschitz regularity of the continuous objective relaxation and uses it to connect optimization regret to distances between solver distributions. This connection supports bounds through Wasserstein distance and, under additional conditions, KL divergence.

A.1 On the Validity and Applicability of Assumption 4.2

  • The multilinear extension is continuously differentiable on the compact unit hypercube, so its gradient is bounded and the relaxed objective is L-Lipschitz.The appendix cites linear TSP and quadratic MIS objectives as examples where the gradient remains bounded.Source: §A.1 · p. 14

A.2 Proof of Lemma 4.3

  • The regret gap between distributions is bounded by ℓ times their Wasserstein-1 distance, which can then be related to KL divergence under suitable conditions.Pinsker’s inequality gives a bound for arbitrary target distributions on a bounded domain; the Talagrand route assumes a concentrated target satisfying a Log-Sobolev inequality.Source: §A.2 · pp. 14–15, §A.1 · p. 14

A.3 Proof of Lemma 4.4: Dimension-Dependent Regret of Conditional DM

The appendix derives dimension-dependent regret for conditional diffusion and motivates super-linear regret scaling for sequential RL. Under these scalings, the hybrid regret has a unique minimizing trigger and is strictly lower there than either pure solver’s regret.

A.3 Proof of Lemma 4.4: Dimension-Dependent Regret of Conditional DM

  • Conditional DM regret is governed by the dimension deff of the unsolved subspace, with initialization and discretization errors scaling linearly in deff.The proof projects the dynamics onto the free subspace; its covariance trace, which governs discretization drift, also scales linearly with deff, assuming per-dimension score error on that manifold.Source: §A.3 · p. 15

A.4 Justification of Lemma 4.5: Super-linear RL Horizon Scaling

  • Finite-horizon RL regret analyses motivate super-linear horizon scaling, but do not directly characterize neural policy-gradient CO solvers.The appendix also notes that autoregressive neural CO solvers’ solution quality often degrades as construction steps increase, consistent with the modeling choice.Source: §A.4 · p. 16

A.5 Proof of Theorem 4.6: Existence and Uniqueness of the Optimal Trigger Step τ ∗

  • The unique optimal trigger τ* balances RL and DM marginal regret, and its hybrid regret is strictly lower than either pure solver’s.RL marginal regret increases while DM marginal regret is non-increasing, producing the unique global minimum.Source: §A.5 · pp. 16–17

B.1 TSP Performance Results

HyCO’s TSP evaluations report gains across sequential backbones, while further benchmarks and ablations test its transfer, adaptive handover, and trigger behavior. Results also show that the best handover timing varies across problem classes and scales.

B.1 TSP Performance Results

  • HyCO improves TSP solution quality across AM, POMO, and LEHD, with the TSP-1000 gap falling from over 20% to about 5% for AM.Its gains also persist against 16-sample conditional diffusion on TSP-100, with 0.02% versus 0.04% gap using a single guided completion (S = 4).Source: §B.1 · p. 18

B.2 MIS Performance Results

  • On ER-700-800, HyCO achieves a 5.76% gap versus 13.16% for RL and 9.16% for diffusion; on RB-Large, it reduces RL error from 15.31% to 5.28%.At S = 5, HyCO also remains competitive with or superior to baselines using S = 64.Source: §B.2 · p. 19, Table 7 · p. 19

B.3 OP Performance Results

  • On OP-200, HyCO reaches a 1.08% gap, compared with 4.15% for prefix_Coexpander (s = 8) and 2.77% for prefix_Coexpander (s = 64).HyCO takes 2.70s per OP-200 instance, comparable to prefix_Coexpander (s = 64).Source: §B.3 · pp. 19–20, Table 8 · p. 20

B.4 Adaptive Trigger vs. Fixed-time Triggering

  • Adaptive triggering beats the validation-selected best fixed schedule across TSP and MIS, reducing gaps from 0.026% to 0.020% on TSP-100 and from 1.20% to 0.12% on SATLIB.On TSP-500 the gap falls from 5.66% to 3.56%; on ER-700–800, adaptive triggering improves over the fixed schedule by 3.22%.Source: §B.4 · p. 20, Figure 2 · p. 21

B.5 Cross-Dataset Trigger Statistics

  • Average handover timing varies substantially by task and scale: TSP-100 tends to trigger early, while larger TSP, MIS, and OP benchmarks can trigger later.This pattern is consistent with an adaptive rather than fixed early handover.Source: §B.5 · p. 20, Table 9 · p. 21

C Ablation Study of HyCO

  • Ablations report that combining policy entropy with RL–DM disagreement performs better than either signal alone, while instance-dependent triggering improves over fixed schedules.The studies also examine sensitivity to the DM energy-probe timestep, RL candidate pool size for KL estimation, and DM exploration threshold.Source: §B.4 · p. 20, C Ablation Study of HyCO · p. 21

C.1 Hyperparameter Sensitivity of Triggering and DM Exploration

The ablations examine the robustness of trigger and exploration settings and the contribution of combining entropy with KL divergence. The dual-signal trigger supports the strongest performance, while several parameter choices materially affect the results.

C.1 Hyperparameter Sensitivity of Triggering and DM Exploration

  • 0.02% optimality gap remains stable across DM energy-probe timesteps from 100 to 900.The authors report that the single-step energy probe does not require meticulous timestep tuning.Source: §C.1 · p. 21, Table 10 · p. 22
  • 1.30% optimality gap and 43.0% trigger rate with only 5 RL candidates indicate that too small a KL-probe pool is unreliable.The default pool size is 15 candidates.Source: §C.1 · pp. 21–22, Table 11 · p. 22
  • 0.12% optimality gap with a 0.2 candidate-selection threshold contrasts with the 0.02% gap reported for the default threshold of 0.8.The threshold controls the breadth of DM exploration after triggering.Source: §C.1 · p. 22, Table 12 · p. 22

C.2 Necessity of Dual-Signal Trigger Design

  • 0.09% and 0.05% optimality gaps for KL-only and entropy-only triggers, respectively, show that both signals are needed for top performance.The authors describe policy uncertainty and model disagreement as complementary signals.Source: §C.2 · p. 22, Table 13 · p. 23

D Implementation Details of Prefix_Difusco and RL models

The implementation pairs a prefix-conditioned diffusion model with RL backbones and uses curriculum training and deterministic decoding to complete valid tours. Model training and inference settings vary with TSP scale, while backbone configurations follow the original implementations for comparability.

D.1 Model Architecture

  • Prefix_Difusco adapts DIFUSCO’s GNN for conditional generation, encoding prefix-node features and a global LSTM prefix vector alongside diffusion timestep information.Its 12-layer denoising GNN outputs a logit for each potential edge.Source: §D.1 · p. 23

D.2 Training Procedure

  • Training corrupts optimal-tour adjacency matrices over 1,000 diffusion steps and applies BCE loss only to suffix edges, with prefixes sampled from optimal tours.A curriculum moves from long, easier prefixes toward shorter, harder completion tasks.Source: §D.2 · pp. 23–24

D.2.1 Training for TSP-50; D.2.2 Training for TSP-100

  • TSP-50 and TSP-100 models are trained from scratch with five-stage curricula that progressively focus on shorter prefixes.The curricula end with prefixes of 1–10 nodes to improve early-step decisions.Source: §D.2.1 · p. 24, §D.2.2 · p. 24

D.2.3 Training for TSP-500

  • TSP-500 uses TSP-100 weights and a five-stage fine-tuning curriculum, with an accelerated schedule of about 20 epochs.The schedule balances performance and computational cost.Source: §D.2.3 · p. 24

D.2.4 Training for TSP-1000

  • TSP-1000 is initialized from TSP-100 and fine-tuned for 25 epochs over four curriculum stages, progressing from long to short prefixes.Later stages focus on shorter prefixes, down to length 1.Source: §D.2.4 · pp. 24–25

D.3 Decoding Algorithms

  • For decoding, edge probabilities are symmetrized and divided by Euclidean distance, then candidates are sorted by score.This deterministic greedy strategy is inspired by DIFUSCO [8].Source: §D.3 · p. 25
  • The decoder fixes prefix edges, greedily builds a spanning path while enforcing degree and cycle constraints, then closes it into a Hamiltonian cycle.The final edge connects the two path endpoints.Source: §D.3 · p. 25

D.4 Hyperparameters

  • HyCO uses original DIFUSCO and RL4CO architectural configurations to isolate gains from framework logic; inference parameters reflect a preliminary speed-quality analysis.The listed configurations cover Prefix_Difusco, the Attention Model, and POMO.Source: §D.4 · p. 25

E Limitations and Broader Impacts

The theoretical analysis depends on explicit assumptions about the RL and diffusion-model backbones. The paper also notes potential applications and the need for safeguards in sensitive deployments.

E Limitations and Broader Impacts

  • HyCO’s theoretical analysis relies on explicit RL and DM error-scaling and boundary assumptions; other solver pairings may require re-examining them and adapting trigger signals.Source: E Limitations and Broader Impacts · p. 25
  • Possible applications include routing, scheduling, logistics, and resource allocation, though HyCO is not tied to a specific high-stakes deployment.Source: E Limitations and Broader Impacts · p. 27
  • In sensitive domains, suboptimal objectives or incorrect solutions could affect access to resources or services; the paper calls for domain-specific constraints, validation, and human oversight.Source: E Limitations and Broader Impacts · p. 27
Loading 2609.07990v1…