DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
Authors: Zhiqing Sun, Yiming Yang
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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 TSP-10000. |
| Researcher Affiliation | Academia | Zhiqing Sun Language Technologies Institute Carnegie Mellon University zhiqings@cs.cmu.edu, Yiming Yang Language Technologies Institute Carnegie Mellon University yiming@cs.cmu.edu |
| Pseudocode | No | The paper describes algorithms in text but does not include structured pseudocode blocks or figures explicitly labeled as “Algorithm” or “Pseudocode.” |
| Open Source Code | Yes | Our code is available at https://github.com/Edward-Sun/DIFUSCO. |
| Open Datasets | Yes | We generate and label the training instances using the Concorde exact solver [3] for TSP-50/100 and the LKH-3 heuristic solver [39] for TSP-500/1000/10000. [...] We use the training split of 49500 examples from [46, 92] and train DIFUSCO for 50 epochs with a batch size of 128. |
| Dataset Splits | No | The paper explicitly mentions generating and using 'training instances' and 'test instances' for experiments, but it does not specify or provide details on a separate validation set or how data splits for training, validation, and testing are performed to ensure reproducibility for all three. |
| Hardware Specification | Yes | All the methods are trained with 8 NVIDIA Tesla V100 Volta GPUs and evaluated on a single NVIDIA Tesla V100 Volta GPU, with 40 Intel(R) Xeon(R) Gold 6248 CPUs @ 2.50GHz. |
| Software Dependencies | No | The paper does not provide specific version numbers for software dependencies such as programming languages, libraries, or frameworks used for implementing the models or running experiments (e.g., Python, PyTorch, CUDA versions). |
| Experiment Setup | Yes | For all TSP and MIS benchmarks, we use a 12-layer Anisotropic GNN with a width of 256. T = 1000 denoising steps are used for the training of DIFUSCO on all datasets. We use a simple linear noise schedule for {βt}T t=1, where β1 = 10 4 and βT = 0.02. For TSP-50: We use 1502000 random instances and train DIFUSCO for 50 epochs with a batch size of 512. |