Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
Authors: Muheng Li, Ruqi Zhang
TMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems. ... We conduct a thorough empirical evaluation of our method Re SCO on various graph combinatorial optimization tasks, including Max Independent Set (MIS), Max Clique, Max Cut and Graph Balanced Partition. For all problems, we follow the experimental setup in Sun et al. (2023b). |
| Researcher Affiliation | Academia | Muheng Li EMAIL Department of Statistical Sciences University of Toronto Ruqi Zhang EMAIL Department of Computer Science Purdue University |
| Pseudocode | Yes | Algorithm 1 Reheated Sampling for Combinatorial Optimization 1: Input: temperature schedule T( ), sampling chain length L, value threshold ϵ, wandering length threshold N, sample size M, skip step threshold tskip 2: Initialize: state x0, critical temperature t = tskip, temperature indicator step t Temp = 1, maximum specific heat C = 0, reheated = false 3: for t = 1 to L do 4: xt SA-gradient-based-Sample(xt 1, T(t Temp)) To determine critical temperature t 5: if t tskip and not reheated then 6: Calculate ˆC(t) as in equation 10 7: if ˆC(t) C then 8: C ˆC(t), t t 9: end if 10: end if To detect wandering in contours 11: if Condition equation 8 holds then 12: t Temp t Reheat to critical temperature 13: end if 14: t Temp t Temp + 1 15: end for |
| Open Source Code | Yes | Through extensive experiments on various CO problems, we demonstrate that our method significantly advances over previous sampling approaches. The code is available at https://github.com/PotatoJnny/ReSCO. |
| Open Datasets | Yes | Following Sun et al. (2023b), we use the MIS benchmark from Qiu et al. (2022), consisting of one realistic dataset SATLIB (Hoos & Stutzle, 2000) and Erds Rényi(ER) random graphs of different sizes. ... Twitter: a realistic Twitter dataset (Leskovec & Krevl, 2014) |
| Dataset Splits | Yes | We directly test Re SCO on the test datasets provided by Goshvadi et al. (2023), which contains the following datasets: SATLIB: consists of 500 test graphs, each with at most 1347 nodes and 5978 edges. ER-[700-800]: consists of 128 test graphs with 700 to 800 nodes. ER-[9000-11000]: consists of 16 test graphs with 9000 to 11000 nodes. |
| Hardware Specification | Yes | The experiments were conducted on a single A6000 with multiple chains executed in parallel, using the same implementation used by the i SCO paper. |
| Software Dependencies | No | The paper does not explicitly state any specific software dependencies with version numbers (e.g., Python, PyTorch, TensorFlow versions or other libraries). |
| Experiment Setup | Yes | For Max Independent Set, Max Clique and Max Cut, we use a value threshold ϵ = 0.01, a wandering length threshold N = 100, and a sample size M = 100 for all tasks. The skip step threshold tskip varies by problem and can be easily set at the point where specific heat s initial sharp decrease ends. See Appendix D for more experimental details, and see Appendix E for discussions about how to choose hyperparameters. Table 6: Setting of hyper-parameters in the experiments. ... Initial Temperature T(0) 1.0 ... Ending Temperature T(L) 1e-5 ... Chain Length L 1M ... Temperature Schedule T( ) exponentially decay |