- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
Diffusion-based methods for combinatorial optimization often add noise directly in the discrete solution space. However, combinatorial solutions are discrete and strongly constrained, which does not naturally match the smooth transport of standard continuous diffusion. To address this, LCO-Diff introduces an instance-conditioned variational autoencoder to transform discrete combinatorial solutions into a diffusion-native latent space. The method consists of two stages: the first stage is an instance-conditioned VAE, and the second stage is a latent-space rectified-flow denoiser. At inference time, it starts from standard Gaussian noise, performs a small number of denoising steps, then decodes the result into a heatmap, and repairs it into a feasible solution using lightweight greedy insertion and local search.
Critical strengths
S1. Diffusion-native latent space from an instance-conditioned VAE is used to learn a node-level continuous representation, so that standard Gaussian diffusion/flow can operate directly in this space without designing solution-space corruption for each problem. S2. Problem-specific feasibility is moved to the decoding interface. The generation side is problem-agnostic, while the decoding side handles constraints such as those in TSP, CVRP, and TSPTW using greedy insertion plus local search. S3. The renoise cycle reuses the Gaussian noising from training, requiring no new operators or retraining, and can convert additional test-time computation into quality improvements. S4. Good storytelling, with a clear motivation. S5. Wide experiments cover several CO problems such as TSP, MIS, CVRP, and TSPTW, and can handle routing problems where solution-space noise is hard to define, such as CVRP and TSPTW.
Critical weaknesses
W1. The embedder must be frozen before the denoiser can be trained; switching problems requires retraining both the embedder and the denoiser. Compared with PT-Denoise's no retraining, this implies higher deployment cost. It does not support plug-and-play. W2. Problem-agnostic holds only on the generation side: inference still requires decode-then-repair, with greedy insertion + 2-opt for TSP, capacity-aware 2-opt for CVRP, and time-window-penalized 2-opt for TSPTW; problem-specific repair operators still exist, merely relocated to the decoding interface. W3. Parameter tuning: the renoise factor ρ is still tuned per problem, ρ=0.4 for TSP-500, ρ=0.1 for TSP-1000, ρ=0.75 for MIS, and ρ=0.5 for CVRP/TSPTW. It is not entirely tuning-free.
Questions for authors
See above in Weaknesses.
Response to Reviewer Dg5a
Thank you for your thoughtful review and for recognizing how the learned latent space supports both candidate generation and test-time refinement. Your comments help us explain what it takes to apply LCO-Diff to a new problem class and how the solver handles that problem’s constraints during inference.
Thank you for pointing us to PT-Denoise. We agree that reusing a pretrained model has a practical advantage when adapting to a new task. We have discussed PT-Denoise in the related work in our revised manuscript and clarify the training requirements of each approach.
In our current setup, a new problem class requires training both the embedder and the denoiser. Freezing the embedder after the first stage gives the denoiser a fixed latent target. Based on our approximate timings, training the embedder takes about 1/10 as long as training the denoiser, or roughly 10% of the combined model training time. This stage provides the representation used for both generation and refinement. The inference gains illustrate the value of that investment. On TSP-500 at C=8, LCO-Diff achieves a 0.0065% gap in 8 seconds, compared with 0.0665% in 10 seconds for the raw-space continuous baseline in Table 5.
We appreciate the opportunity to clarify the role of post-processing. Our design focuses on improving how the model proposes and refines candidates. Each cycle re-encodes the incumbent and refines it along the Gaussian path used during training. The decoder then constructs a discrete solution, and task-specific local search such as 2-opt can further improve its quality.
The learned refinement can already outperform strong prior solvers with greedy decoding alone. On MIS-RB, LCO-Diff uses greedy decoding with no additional local search. Increasing the number of refinement cycles from 4 to 256 reduces the gap from 1.12% to 0.06%. At 256 cycles, LCO-Diff reaches 0.06% in 13.1 minutes, compared with 0.22% in 35.2 minutes for the best-gap GenSCO setting reported in Table 2. We will clarify that the shared procedure concerns candidate generation and refinement in latent space, and that additional local search can be used where it improves solution quality.
Thank you for pointing out the different values in Table 13. The parameter ρ controls how strongly we perturb the incumbent along the same Gaussian path. A smaller value preserves more information about the current solution, while a larger value allows broader exploration. Since the denoiser is trained across the interpolation path, we can adjust this balance for a task or instance size using the same checkpoint.
Several of our evaluated settings already share a value. CVRP and TSPTW both use ρ=0.5, and both MIS graph families use ρ=0.75. With ρ=0.5 fixed, for example, the CVRP-100 gap falls from 0.49% to 0.11% as C increases from 8 to 512. We have revised Section 3.3 to make the distinction explicit. The Gaussian renoising rule is shared, and its strength can be chosen at inference time to suit the problem.
Thank you again for your constructive suggestions. We hope the training measurements and the greedy-only MIS results help quantify the cost and benefit of learning the latent representation. We appreciate the opportunity to clarify which parts of generation and refinement are shared across tasks and which choices depend on the problem.