# Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation

Source: [Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation](<https://www.sota2.com/research/paper/68fa7ab11e209131cea84a7a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-03-13T05:00:04.336Z

Authors: Haoyu Lei, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia

Published: 2025-02-15T08:04:00.000Z

## Abstract

Diffusion-based Neural Combinatorial Optimization (NCO) has demonstrated effectiveness in solving NP-complete (NPC) problems by learning discrete diffusion models for solution generation, eliminating hand-crafted domain knowledge. Despite their success, existing NCO methods face significant challenges in both cross-scale and cross-problem generalization, and high training costs compared to traditional solvers. While recent studies on diffusion models have introduced training-free guidance approaches that leverage pre-defined guidance functions for conditional generation, such methodologies have not been extensively explored in combinatorial optimization. To bridge this gap, we propose a training-free inference time adaptation framework (DIFU-Ada) that enables both the zero-shot cross-problem transfer and cross-scale generalization capabilities of diffusion-based NCO solvers without requiring additional training. We provide theoretical analysis that helps understanding the cross-problem transfer capability. Our experimental results demonstrate that a diffusion solver, trained exclusively on the Traveling Salesman Problem (TSP), can achieve competitive zero-shot transfer performance across different problem scales on TSP variants, such as Prize Collecting TSP (PCTSP) and the Orienteering Problem (OP), through inference time adaptation.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Orienteering Problem on OP-50 (Prize, Gap)](<https://www.sota2.com/research/sota/orienteering-problem-on-op-50-prize-gap.md>): Orienteering Problem; OP-50; Prize: 28.21.

- [Prize-Collecting Traveling Salesperson Problem on PCTSP-50 (Metrics: Cost, Gap)](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesperson-problem-on-pctsp-50-metrics-cost-gap.md>): Prize Collecting Traveling Salesperson Problem; PCTSP-50; Optimality Gap: 3.57.

- [Prize-Collecting Traveling Salesperson Problem on PCTSP-100](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesperson-problem-on-pctsp-100.md>): Prize Collecting Traveling Salesperson Problem; PCTSP-100; Optimality Gap: 9.61.

- [Prize-Collecting Traveling Salesman Problem on PCTSP Average across scales 20, 50, 100](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesman-problem-on-pctsp-average-across-scales-20-50-100.md>): Prize-Collecting Traveling Salesman Problem; PCTSP Average across scales 20, 50, 100; Average Optimality Gap: 9.7.

- [Orienteering Problem on OP-50](<https://www.sota2.com/research/sota/orienteering-problem-on-op-50.md>): Orienteering Problem; OP-50; Gap: 6.11.

- [Orienteering Problem on OP Average across scales 20 50 100](<https://www.sota2.com/research/sota/orienteering-problem-on-op-average-across-scales-20-50-100.md>): Orienteering Problem; OP Average across scales 20 50 100; Average Gap: 7.26.

- [Prize-collecting Traveling Salesman Problem on PCTSP 500 (Metrics: Cost, Time)](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesman-problem-on-pctsp-500-metrics-cost-time.md>): Prize-Collecting Traveling Salesman Problem; PCTSP 500; Cost: 14.5.

- [Prize-collecting Traveling Salesman Problem on PCTSP-1000](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesman-problem-on-pctsp-1000.md>): Prize-Collecting Traveling Salesman Problem; PCTSP-1000; Cost: 21.7.

- [Orienteering Problem on OP-20](<https://www.sota2.com/research/sota/orienteering-problem-on-op-20.md>): Orienteering Problem; OP-20; Optimality Gap: 3.11.

- [Prize-Collecting Traveling Salesperson Problem on PCTSP-20](<https://www.sota2.com/research/sota/prize-collecting-traveling-salesperson-problem-on-pctsp-20.md>): Prize Collecting Traveling Salesperson Problem; PCTSP-20; Optimality Gap: 4.2.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2502.12188>)

[PDF](<https://arxiv.org/pdf/2502.12188.pdf>)
