DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization

• URL: http://arxiv.org/abs/2302.08224v2
• Date: Sat, 2 Dec 2023 21:27:23 GMT
• Title: DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
• Authors: Zhiqing Sun, Yiming Yang
• Abstract summary: We introduce a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete 0, 1-vector optimization problems. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.
• Score: 51.517956081644186
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0, 1}-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.

Related papers

• Neural Solver Selection for Combinatorial Optimization [23.449310200885893]
  We propose the first general framework to coordinate neural solvers, which involves feature extraction, selection model, and selection strategy. We show that the proposed framework can effectively distribute instances and the resulting composite solver can achieve significantly better performance.
  arXiv  Detail & Related papers  (2024-10-13T02:05:41Z)
• Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems [15.435730759218776]
  We develop a novel Quantum-Inspired Mean Field (QIMF) probabilistic model that approximates solutions to Quadratic Unconstrained Binary Optimization problems. Our empirical studies demonstrate significant improvements in solution evaluation for large-scale problems of portfolio selection, the weighted maxcut problem, and the Ising model.
  arXiv  Detail & Related papers  (2024-06-01T01:53:11Z)
• Implicit Stochastic Gradient Descent for Training Physics-informed Neural Networks [51.92362217307946]
  Physics-informed neural networks (PINNs) have effectively been demonstrated in solving forward and inverse differential equation problems. PINNs are trapped in training failures when the target functions to be approximated exhibit high-frequency or multi-scale features. In this paper, we propose to employ implicit gradient descent (ISGD) method to train PINNs for improving the stability of training process.
  arXiv  Detail & Related papers  (2023-03-03T08:17:47Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  State-of-the-art convex learning methods can perform far worse than their centralized counterparts when clients have dissimilar data distributions. We show this disparity can largely be attributed to challenges presented by non-NISTity. We propose a Train-Convexify neural network (TCT) procedure to sidestep this issue.
  arXiv  Detail & Related papers  (2022-07-13T16:58:22Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem [5.906031288935515]
  We present a hybrid data-driven approach for solving the Traveling Salesperson Problem (TSP) based on Graph Neural Networks (GNNs) and Guided Local Search (GLS) Our approach finds solutions with an average optimality gap of 2.5%, a 10x improvement over the next best learning-based benchmark.
  arXiv  Detail & Related papers  (2021-10-11T14:06:08Z)
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning [8.819672165548477]
  We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP)
  arXiv  Detail & Related papers  (2020-10-30T00:57:50Z)
• Efficient and Scalable Bayesian Neural Nets with Rank-1 Factors [36.56528603807598]
  We propose a rank-1 parameterization of BNNs, where each weight matrix involves only a distribution on a rank-1 subspace. We also revisit the use of mixture approximate posteriors to capture multiple modes, where unlike typical mixtures, this approach admits a significantly smaller memory increase. For ResNet-50 on ImageNet, Wide ResNet 28-10 on CIFAR-10/100, and an RNN on MIMIC-III, rank-1 BNNs achieve state-of-the-art performance across log-likelihood, accuracy, and calibration.
  arXiv  Detail & Related papers  (2020-05-14T17:58:59Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)

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.