Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling

• URL: http://arxiv.org/abs/2502.12188v1
• Date: Sat, 15 Feb 2025 08:04:00 GMT
• Title: Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling
• Authors: Haoyu Lei, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia,
• Abstract summary: 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. Existing NCO methods face challenges in both cross-scale and cross-problem generalization, and high training costs compared to traditional solvers. We propose a general energy-guided sampling framework during inference time that enhances both the cross-scale and cross-problem generalization capabilities of diffusion-based NCO solvers without requiring additional training.
• Score: 27.898573891403075
• License:
• 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 have introduced training-free guidance approaches that leverage pre-defined guidance functions for zero-shot conditional generation, such methodologies have not been extensively explored in combinatorial optimization. To bridge this gap, we propose a general energy-guided sampling framework during inference time that enhances both the cross-scale and cross-problem 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 solution generation on TSP variants, such as Prize Collecting TSP (PCTSP) and the Orienteering Problem (OP), through energy-guided sampling across different problem scales.

Related papers

• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  We introduce OptVQ, a novel vector quantization method that employs the Sinkhorn algorithm to optimize the optimal transport problem. Our experiments on image reconstruction tasks demonstrate that OptVQ achieves 100% codebook utilization and surpasses current state-of-the-art VQNs in reconstruction quality.
  arXiv  Detail & Related papers  (2024-12-19T18:58:14Z)
• Liner Shipping Network Design with Reinforcement Learning [1.833650794546064]
  This paper proposes a novel reinforcement learning framework to address the Liner Shipping Network Design Problem (LSNDP) Our approach employs a model-free reinforcement learning algorithm on the network design, integrated with aLIB-based multi-commodity flow solver.
  arXiv  Detail & Related papers  (2024-11-13T22:49:16Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  Diffusion generative models can consider a broader range of solutions and exhibit stronger generalization by learning parameters. We propose a new framework, which leverages intrinsic distribution learning of diffusion generative models to learn high-quality solutions.
  arXiv  Detail & Related papers  (2024-08-13T07:56:21Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
  This work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural optimization. In particular, we design a powerful yet lightweight instance-conditioned Routing adaptation module for the NCO model. We develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution.
  arXiv  Detail & Related papers  (2024-05-03T08:00:19Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Rethinking Clustered Federated Learning in NOMA Enhanced Wireless Networks [60.09912912343705]
  This study explores the benefits of integrating the novel clustered federated learning (CFL) approach with non-independent and identically distributed (non-IID) datasets. A detailed theoretical analysis of the generalization gap that measures the degree of non-IID in the data distribution is presented. Solutions to address the challenges posed by non-IID conditions are proposed with the analysis of the properties.
  arXiv  Detail & Related papers  (2024-03-05T17:49:09Z)
• Operator Learning Enhanced Physics-informed Neural Networks for Solving Partial Differential Equations Characterized by Sharp Solutions [10.999971808508437]
  We propose a novel framework termed Operator Learning Enhanced Physics-informed Neural Networks (OL-PINN) The proposed method requires only a small number of residual points to achieve a strong generalization capability. It substantially enhances accuracy, while also ensuring a robust training process.
  arXiv  Detail & Related papers  (2023-10-30T14:47:55Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Learning to Solve Routing Problems via Distributionally Robust Optimization [14.506553345693536]
  Recent deep models for solving routing problems assume a single distribution of nodes for training, which severely impairs their cross-distribution generalization ability. We exploit group distributionally robust optimization (group DRO) to tackle this issue, where we jointly optimize the weights for different groups of distributions and the parameters for the deep model in an interleaved manner during training. We also design a module based on convolutional neural network, which allows the deep model to learn more informative latent pattern among the nodes.
  arXiv  Detail & Related papers  (2022-02-15T08:06:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.