Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
Authors: Muheng Li
Ruqi Zhang
Venue: Accepted by TMLR ()

Abstract: Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ``wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation.  Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.

Published in Transactions on Machine Learning Research (03/2025)
Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
Muheng Li
muheng. li@mail utoronto.co
Deportment of Statisticnl Sciences University of Toronto
Ruqi Zhang
rugiz&purdue.. edu
Department of Computer Science
Purdue University
Reviewed on OpenReview: https: /ttps://opeewee openreview net/ forum? id= 2FC
Abstract
Recently, gradient-based discrcte sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance compa- rable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which term "wandering in contours". This behavior refers to sampling new different solutions that share very similar objective values for long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce novel reheating mechanism inspired by the concept of critical tem- perature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling based and data-driven algorithms across a diverse array of CO problems.
1 Introduction
Combinatorial optimization (CO) refers to the problem that seeks the optimal solution from finite feasible set. This type of optimization is prevalent in numerous applications such as scheduling, network design, resource allocation, and logistics. CO problems are inherently complex due to the huge number of potential combinations, making the scarch for the optimal solution challenging.
To solve CO problems, various methods are developed. Fxact methods like Branch-and-Bouu (Land Doig. amm guarantee optimal solutions but computationally intensive for large problems. Heuristic approaches, such greedy algorithms (DeVore & Temlyakov, (196)). offer quick solutions but without an optimality guarantee. Integer linear programming (Schrijver, 1998 is effective for formulating problems
mathematically, yet it struggles with scalability. Recently, data-driven approaches using machine learning (Li aL 2018, Gasse et all, 2019 Khalil et all, 2017 Nair el all 2121; Karalias & Lonkas 2020) have seen rapid growth. However, they demand significant data and computational power and cannot be used off-the-shelf solvers for problems that differ from the training data.
Recently, sampling approaches have regained popularity in addressing CO problems. Simulated annealing (SA) (Kirkpatrick et all, 1983), a longstanding sampling method, has been widely applied in the CO field for several decades. However, these methods are often criticized for their inefficiency in high-ddiennsionl spaces, primarily due to their random walk behavior during the exploration (Dolahaye et all, 201H Nomaa
3 Andresenn, [998; Haddooc Millenthall, [192). Leveraging recent ad vancements gradient-based discrete
sampling (Grathwohl all 2021; Sun all 2024 ZI2K8: Zhang et al, 20zz). Sun (ΑлΚКо) demonstrates that sampling methods serve general solvers and achieve a more favorable balance between speed and
* Work done during internship Purdue University.

---

Published in Transactions on Machine Learning Research (03/2025)
solution quality compared to data-driven approaches for many CO problems, sometimes even outperforming commercial solvers and specialized algorithms.
In this paper, we pinpoint a critical limitation, termed wandering in contours, in current gradient-based sampling for CO. We observe that the sampling methods remain stuck in sub-optimal contours, defined as a set of diverse solutions with identical or very similar objective values, for a prolonged duration due to reliance on gradient information. This phenomenon severely harms both efficiency and solution quality. To tackle introduce novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics. Our approach involves resetting the temperature to theoretically informed threshold once the algorithm begins wandering, thus facilitating more effective exploration. We summarize our contributions as follows:
this problem,
We identify a key issue in gradient-based sampling for combinatorial optimization (CO), termed wandering in conlours: algorithms yield distinct solutions, yet with nearly identical objective values for extended periods duc to using gradient and low temperatures.
We then propose reheat mechanism where we reset the temperature to the critical temperature once the algorithm begins wandering, optimizing resource use and improving solution discovery.
Through extensive experiments on various CO problems, we demonstrate that our method signifi- cantly advances previous sampling approaches. The code is available at https://github.com
Potato.Jnny/ReSCO.
2
Related Work
Gradient-based Discrete Sampling Sampling in discrete domains has historically been challenging, with Gibbs sampling (Geman & Geman, [**I]) being a longstanding primary method. A significant improve- ment came with the introduction of locally balanced proposals by Zanolla (2019), leveraging local solution information for sampling in discrete neighborhoods. Gradient-based discrete samplers are derived by using gradient approximation (Grathwahl el. (02T), which become the most common implementations of locally balanced samplers. Later, Sun et. all (202T) proposes PAS to broaden the discrete sampling neighborhood, and Discrete Langevin developed by Zhang et all (2022) enables parallel updates in each step. Many discrete
samplers are developed based on variants of locally balanced proposals (Rhooes & Gulmann, 2022: Sun et all,
2022 ИIКRR: Xiang et al. 2028: Pynadath et al. 2024
Sampling for Combinatorial Optimization Sampling methods were once popular for solving com-
binatorial optimization (CO) problems, among which the most famous algorithm is simulated annealing SA has been successfully applied to a wide array of CO problems, including
(SA) Kirkpatrick et al. (11E%
TSP (Kirkpatrick el al]. [+06 scheduling (Van Laarhoven el. atlll, (MA)), ; and vehicle routing (Osmani [иио).
Though SA theoretically guarantees convergence to the global optimum under certain conditions, its use of random walk leads to slow convergence in high-dimensional discrete problems. Addressing this, Sum et al (2123al introduces an improved algorithm by integrating the gradient-basee discrete sampler into the SA framework, achieving superior solutions for complex CO problems more efficiently than many learning-based approaches.
3 Preliminaries
3.1 Combinatorial Optimization
We consider combinatorial optimization problems with the form:
min uz)) s.t. v(x)= = #
(1)
where is dimensional finite solution space. We assume Vr E O, the objective value u(x)) 2 and ((x)) I O. By introducing a penalty coefficient X, we obtain unconstrained optimization problem from Eq
2

---

Published in Transactions on Machine Learning Research (03/2025)
equation M (big enough À will ensure the equivalence of the optimal solutions):
min f(z) & u(x) Ao(z).
(2)
rEB
We can view it as an energy-based model, where x is a state and f(x) is the energy of the state.
3.2 Simulated Annealing
Simulated anncaling (SA) optimizes energy-base models by simulating a physical anncaling. employs a lemperature parameter T, and states sampled according to
Tπ(x) x exp(-I(x)/T))
(3)
Inhomogeneons SA performs a single sampling step at each while homogencous SA performs multiple steps. The temperature gradually decreases, and new solutions are accepted based on:
Pr(x + x') (x)(())epp-(((())
(4)
During the transition from high to low temperaturos, SA narrows the target distribution, shifting from wide exploration to targeted exploitation of low-energy states. SA is theoretically guaranteed to converge to the global optimal state as T goes to
3.3 Gradient-based Discrete Samplers
In locally balanced proposal (Zanela,, 2019), the update rule at the current state is given by:
qy, a) x g (T(U)/ K(x -
(5)
where TT-) is the larget distribution over the discrete space θ K is a kernel that decides the scale of the proposal, and g(-) balancing function. In energy-based models, we have x(x) x exp(-f(x)), i.. (1(x) in equation R. Then,
(y, x) x -
(6)
Using the finst-order Taylor expansion to approximate f(x) f(y), we then get the gradient-based discrete sampler. Here, assume f has natural continuous relaxation f. The gradient of is defined as ff(x)) Vf(x), E θ.
4 Pitfall of Gradient-based Discrete Sampling
E we present an intriguing phenomenon of gradient-based sampling in solving combinatorial opti- mization problems, which remarkably affects its perfor- mance and efficiency. In Section M we present a theo- retical analysis of this phenomenon and propose two ex- planations for its occurrence.
In Section
Stop Value Point Mitimum
Normal Sampling Stops Wondering Contours
R-2
4.1 Wandering in Contours
Cradient-based discrete sampling, when combined with simulated anncaling scttings, has shown considerable suc- cess in addressing large-scale combinatorial optimization (CO) problems (Sin et all, 2л23E; Goshvadi.e all, 20zz),
mainly due to its significantly accelerated convergence rate. The use of gradient information, though advanta- geous for locating good solutions quickly, also undermines
Figure 1 Visualization of the "wandering in con- tours" phenomenon.
3

---

Published in Transactions on Machine Learning Research (03/2025)
30
13.90e
40
0.010
0.009
10
30
0.008
Objectiv
26
Obyecbee
0.007
Converge to Stop Value
0.006
10
20
Wandering in Contours Stop Value Point
0.005
15
20
0.004
Optimal Value
Stop Value
-30
0.003
4000
5000
6000
7000
8000
8000
10000
1000
3000
5000
7000
9000
5000
6000
7000
8000 Step
9000 10000
Step
Stsp
(a)
(b)
(c)
4,0
Dispance from Point
300
3.5
Diltenee Cormeng
3.0
25
2.5
20
2.0
15
1.5
10
1.0
0.5
0.0
1000
2000
3000
800
1000
Poet-wendeeing
Post-corvergencee Slep
(d)
The wandering in contours phenomenon of a gradient-based discrete sampler maximum independent set problem. (a): The trajectory of objective values of traditional simulated annealing, where the algorithm updates the value slowly. (b): The trajectory of objective values of gradient-based sampling methods. The algorithm converges rapidly to a stop value solution (highlighted in green) and then stays close to this value. (c): The objective values after the stop point continue to fluctuate but stay very similar to or the same as the stop value. (d): Gradient-based samplers produce solutions with similar objective values but large distances from the stop point. (e): All the newly sampled solutions in traditional simulated annealing near each other.
Figure 2:
the core strength of simulated annealing to explore the solution space effectively. This leads a peculiar form of trap in the optimization process, which we term wandering in contours,
Wandering in Contours: After quickly converging to a sub-optimal stop value, the algorithm begins to sample new different solutions sharing objective values very similar to, or even the same as, the slop value for a long time.
We observe that "wandering contours" is prevalent across various gradient-bascd discrete sampling methods and CO problems. This behavior visualized Figure M. where the algorithm, upon reaching stop value, appears to wander within certain contour lines without making further progress.
Empirical evidence of this behavior is presented in Figure 2. Here, use gradient-baser discrete sampler, PAS (Smn all (0211,, within simulated annealing (SA) framework, for a maximum independent set problem, aiming to find the solution with the highest objective value. Compared to the slowly updating process of traditional SA depicted in Figure 2a, the simulated annealing with PAS rapidly converges to a sub-optimal solution (marked in green) within approximately 4,000 of the total 10,000 steps as shown in Figure 2T Following this convergence, the algorithm enters a phase of "wandering in contours", where generates new, different solutions, yet their objective values are very similar to the stop value, as demonstrated in Figure 2n & 2 This phenomenon is broadly present in various gradient-based discrete samplers, with evidence provided in Appendix AT
How "wandering in contours" different from convergence suboptimal points? "Wandering in contours" is distinct from being trapped in suboptimal points, a well-known phenomenon in machine
4

---

Published in Transactions on Machine Learning Research (03/2025)
learning and optimization (Zhang et all M0T7). While both involve lack of significant improvement, "wan- dering in contours" depicts a phemomenon that the algorithm will sample different solutions, which is just like the algorithm is still forwarding along a road and getting farther away from the beginning solution of "wandering in contours", but all the solutions on this road share similar objective values. This behavior is illustrated in Figure 2dl, where the new solutions sampled by the algorithm are getting far away from the stop solution, while they share almost the same objective values.
In contrast, convergence to the suboptimal points signifies that the algorithm has found a region containing the (sub)optimal solution. As mentioned in Cruz & Doreal (1999)), convergence indicates that the solutions sampled become increasingly clustered around the suboptimal solution. This clustering behavior can be observed in Figure 28, which shows the distance between the newly sampled solutions and the convergent. solution. It can be clearly seen that the newly sampled solutions are near each other.
4.2 What causes "wandering in contours"?
In the previous section, we observed that the sampler tends to "wander in contours" after reaching certain point, failing to make further progress. This section delves into an analysis of this phenomenon and identifies its underlying causes. We discovered that this behavior primarily stems from two factors: the misleading gradient information employed by discrete samplers, and the low-temperalure enviroument inherent in the simulated annealing framework. These two factors together significantly diminish the algorithm's 'ss ability to escape suboptimal solutions, leading it to persist in the "wandering in contours" pattern.
Misleading Gradient Information In gradient-basee discrete sampling algorithms, the gradient (x())) will be incorporated in the proposal to generate the next state. The quality of the proposed state thus highly depends on whether the gradient information is useful.
It is well-established that gradient-based methods in continuous spaces are susceptible to converging to local optima because gradient information can be misleading. This issue becomes even more pronounced in discrete optimization problems, where the gradient utilized by discrete samplers derived from a natural continuous relaxation of the original discrete domain (as discussed in the preliminarics section). In such relaxed continuous spaces, local minima may not correspond to feasible discrete solutions. Instead, they may be encircled by a cluster of feasible discrete solutions sharing very similar objective values. The misleading gradient will then lead the algorithm to jump around these feasible solutions, causing the wandering in contours behavior.
We take a 1-dimensional discrete optimization problem as an example:
4
min ZEN
-2 σ
x²
3
The global minimum of the function is located at 0, as illustrated in Figure 69 Within the continuous relaxation of the domain N, there exists a local minimum at 2.5. This local minimum is surrounded by the feasible discrete solutions at z = 2 and I = 3. The gradient- based discrete samplers will be influenced by gradient. information to move towards the local minimum at x = 2.5. However, since x = 2.5 is not a feasible solution in the discrete domain, the algorithm would ultimately converge to either x: = 2 or x = 3, and then jump to the other directed by the gradient. This behavior can lead to the algorithm oscillating between these two suboptimal solutions.
Low Temperature Environment The low-temperature stage is critical phase in the simulated anneal- ing process, featuring rapid convergence toward the final solution as the algorithm reduces its random exploration. However, during this phase, the exploration capabilities of gradient-based discrete samplers, enabled by the randomness in the proposal distribution, rapidly diminish, making them less likely to escape from suboptimal solutions.
We take one of the gradient-based discrete sampler DMALA (Zhang et all 2022) as an example, and the following analysis also applied to the other gradient-based based discrete samplers. The update rule of DMALA at temperature 7 is:
5

---

Published in Transactions on Machine Learning Research (03/2025)
1.75
Local Mrinum
CtarsPort Eas Port
Globw Minmum
PAS
Avengn Excrping Rate
0.5
DMALA
0.4
DLMC
13
406
622
0.1
02
0.0
0.5
0.0
0.5
1,0
X 2.
1.5
2.0
3,0
66
Temparature
(a)
(b)
(c)
Figure 3: (a): Illustration of the discrete optimization landscape for the function 1 fx00 + x2 Directed by the gradient information, the gradient- based discrete samplers will oscillate between two discrete solutions and 3 near the local minimum 2.5. (b): Visualization of ((21,x2) from equation M In the experiment, we start from the local minimum (0,0) (marked as green) and test whether the discrete samplers can reach the global minimum 1) (marked as red); (c): The average escaping rate of three gradient-based discrete samplers, which defined as the probability of escaping from local minimum (0, 0) to the global minimum 11, by running 20 sampling steps different temperatures, declines sharply as temperature decreases.
-x;) p(a[(x) = moftmax [Vf())
(x) - x;
T
20:
When T' is low, the magnitude of the gradient term increases significantly. As a result, the values inside the softmax function become highly varied for different x'. This results in more concentrated probability dis- tribution after laking the softmax function. Consequently, the selection process becomes more deterministic and less random, as the algorithm strongly favors certain directions. This means that when the temperature is low, once the gradient information is misleading, as discussed before, the gradient-based discrete sampling is more prone to the "wandering in contours" behavior and less likely to escape from it.
Morcover, at low temperature T, the probability of accepting a worse solution x' simulated anncaling is lower, making it harder to jump out of the local optima by hill-climbing, i.e., temporarily accepting worse solutions for eventually reaching superior ones.
We now show the effect of low temperature by toy example. We consider the following discrete optimization problem:
3 )
(21, -(x1 + x2)((x + x2 (21.22))(0.1)
min
This function features a local minimum (0,0) and a global minimum (1, 1), and hill-climbing is needed for escaping from (0,0) to 11, as illustrated in Figure RE
We employed three distinet gradient-based discrete samplers DMALA (hang et all 2022), DLMC (Smn all (023)), and PAS (Smn et all, 202T) to address this optimization problem under varying constant lemperature conditions. Initiating from the local minimum (0,0), each sampler executed 20 sampling steps at various constant temperatures to assess their ability to transition to the global minimum 1I, Repeating 100,000 experiments for each temperature setting allowed us to calculate an average escaping rate, defined as the likelihood of successfully moving from (0,0) to 1) within 20 steps.
The results, shown in Figure MG clearly illustrate a sharp decline in the escaping rate as temperature de- creases across all samplers. This trend underscores the critical influence of temperature in gradient- basod discrete samplers within the simulated annealing framework, particularly highlighting how lower tempera- tures significantly reduce the algorithm's ability to escape from suboptimal solutions.

---

Published in Transactions on Machine Learning Research (03/2025)
5 Gradient-based Sampling with Reheat
To address the challenges outlined in Section H, we propose a reheat mechanism, which strategically raises the temperature upon detecting the algorithm's wandering, This approach addresses misleading gradient information by flattening the proposal distribution over different candidates at higher temperatures, adding randomness and aiding the escape from suboptimal states. The reheat directly tackles low-temperature limitations by increasing the temperature, facilitating more dynamic exploration process. Intuitively, reheat works by resetting the temperature a higher value. It usually contains two key steps: (1) Detect when to reheat. (2) Increase the temperature to predefined higher value. Below, we present reheat. method for gradient-based discrete samplers in detail.
Our idea of reheating is non-trivial. The reheating mechanism is different from existing stepsize-tuning methods explored in MCMC literature, and a detailed discussion is provided in Appendix Q While simulated annealing with reheating has been proposed before (Abraamson et. all, 1998; Anagnostopoulos el all, 2010), its usage remains very limited. This is primarily due to the slow convergence rate of the original simulated annealing (SA). Reheat was designed to aid simulated annealing in escaping local optima, but the slow convergence of SA made it challenging to even reach local optimum. Consequently, the reheat mechanism often had minimal impact on enhancing simulated annealing's performance and, in certain cases, could even degrade it. On the contrary, gradient-based discrete samplers can converge to the local optimum quickly, which re-energizes the rehcating strategy. Integrating simulated anncaling with gradient-base based discrcte samplers offers a situation where the reheat mechanism becomes effective.
5.1 Detecting When to Reheat
The first critical step of our reheat mechanism is accurately detecting the "wandering in contours" behavior. Considering that the objective values during wandering remain very similar, this behavior can be detected by measuring the variation between the objective values.
For this purpose, we set a value threshold, e, and a wandering length threshold, N. These parameters are used to assess the changes in the objective values f(z)) at cach step t. Specifically, we monitor the absolute differences in consecutive objective values, and if these differences fall below e for N consecutive steps, we infer that the algorithm is exhibiting "wandering in contours". Formally, the algorithm is considered to be wandering in contours at step t if:
f(x (ic--i)((zz--i-e f(( <,, = 0, 0........NN-
.
(8)
Hyperparamelers and N can be tailored to specific problems and the expected variability in the objective values. Generally, smaller e makes the detection more sensitive to minor changes, and a smaller N reduces tolerance for spending time on similar values. We studied their practical effect in Section DRNK
5.2 Selecting the Reset Temperature
After detecting "wandering in contours", choosing appropriate reset temperature is critical. If the reset temperature is too low, then the sampler will not have enough exploration ability to accept worse solutions temporarily and diminish the influence of gradient information. If the reset temperature too high, then the sampler will act like an incfficient random walk for a long time.
5.2.1 Critical Temperature
To identify the optimal reset temperature, utilize the concept of critical temperature T. in physical anncaling (Landan & Lifshifz (196). This temperature marks the phase transition from disordered to ordered states, fundamentally changing physical properties. Similar phase Transitions have been observed in simulated annealing (Kirkpatrick et all (ANK). Above Te, the sampler's search is random and broad. Below Te, the sampler is selective, with a higher tendency to reject worse solutions. It is also observed that the search will be trapped in single valley below Te, making it hard to jump out of the wandering in contours (Strobl & Barken, 201G). Hence, T, serves as critical balance between exploration and exploitation.
7

---

Published in Transactions on Machine Learning Research (03/2025)
The efficiency of simulated annealing around T. has been reported in numerous studies. Kirkpatrick et al. (TM8)) demonstrated that during phase transition, the search becomes more efficient. Strobi & Barked (20TT) showed that when using simulated annealing to solve phylogeny reconstruction, the search is constrained to a small valley of the search space when the temperature below Te. The search efficiency around T. can also be seen in Figure of (Cai Ma. 2010)).
While some algorithms (Basu & Frazen, TEMT design the initial and final temperatures, its use for reheating is less common. Abramson et all (μннн) proposes reheating strategy tied to function cost that implicitly involves Te. However, this method lacks theoretical support and is sensitive to hyperparamcters. Instead, our approach directly reheats to the critical temperature, which injects just the right amount of stochastic energy back into the system, enabling it to escape "wandering in contours" without incurring excessive randomness high-temperature regime.
Ma MITURR) have used critical temperature Te to
5.2.2 Specific Heat
Determining the critical temperature simulated anncaling requires identifying the phase transition point during optimization, which is characterized by peaks in specific heal (Kirkpatrick et arl 1983; Stroh Barker, 20TT) Tn statistical physics, the system's energy at temperature T, denoted E(T),, adheres to the Boltzmann distribution. Thus, the expected energy of system can be seen function of the temperature, E[E(T)). The specific heat at temperature T, denoted as Cr, is traditionally defined in thermodynamics as the rate of change of the expected energy E[E(T)] temperature (AArts ef 1987), given by CT (E[E(T) Integrating over the Boltzmann distribution allows deriving specific heat in terms of energy variance:
CT oE(((T))
(9)
T2
where (E(T)) the variance of the system energy at T.
5.2.3 Determination of Critical Temperature
To determine the critical temperature based on specific heat, first denote T(t) the temperature at step 1, C(I) the specific heat at lemperature T(I), and xa the solution sampled at step I, then by selecting appropriate sample size M, we define the approximation of C(t)
as:
C(I) M ((.))) f(x)))) T()2
12 M
(10)
where (1f(xt-M41) ... (xx))) represents the variance in objective values over the most recent steps. The critical temperature Te can be determined T(*"), where arg max C(t). However, SA with 12M gradient-based discrete samplers convergences rapidly in the initial stage, resulting in an abnormal initial peak in specific heat (due the high variance). As the annealing progresses, the specific heat quickly decreases, eventually stabilizing at level more typical of critical temperature. This behavior is shown in Figure Ha
To address the abnormal peak, we introduce "skip step" threshold, denoted as fakip, ensuring that the initial transient behavior is excluded from the analysis. Thus, the critical temperature is identified as T(**), where
arg max C(t).
(11)
Ealpp
Our method diverges from traditional SA reheat strategics Abbanson ef all 1898) by accounting for inho- mogeneous chains and addressing gradient-based methods' unique abnormal peaks.
8

---

Published in Transactions on Machine Learning Research (03/2025)
of of
Random walk PAS
-2000
Value
8
4000
Random wakk
-6000
PAS
5000
15
Reheating Foints
10000
10
Stop Value Poin
10
Result of ISCD
0
25
50
75
160
125
150
175
200
120
200
902
400
540
900
2000
4000
6000
8000
10000
2000
4000
6003
8000
10000
(a)
(b)
(c)
(d)
Figure 4: (a): Comparison of the first 200 steps shows that SA with PAS, a gradient-based discrete sampler, achieves fast initial improvement, then slows, unlkke traditional SA's steady progress. (b): From steps 100 to 600, SA with PAS initially has much higher specific heat, which then quickly drops and stabilizes, in contrast to SA's steady specific heat levels. (c): After converging to the stop value point, iSCO begins to wander in contours and wastes the rest of the steps. (d): Upon detecting "wandering in contours", ReSCO reheats to the critical temperature, facilitating an escape from this behavior and discovering better solutions.
Table 1: Left: Average approximation ratio of different methods two MaxClique tasks, where iSCO-N and ReSCO-N represent running N sampling chains for each problem; Right: Runtime of single-chain iSCO, single-chain ReSCO, and 32-chain iSCO on MIS tasks on a machine with a single NVIDIA RTX A6000 GPU.
Method
Twitter
RBttet
EPM (Karalias & Loukes [[X()
0.921
0.788
Method
SATLIB
ER-[700-800)
(9-0000-11000)
AFF
(Wang et all (12)
0.926
0.787
RUN-CSP (Tönshoff all (PPT
0.987
0.789
iSCO-1
40 min
8 min
193 min
iScO-1 (Snn et all (1285)
0.971
0.795
ReSCO-1
69 min
17 min
234 min
iSCO-16
(Smn et all 207877
1.000
0.854
iSCO-32
826 min
225 min
1746 min
ReSCO-1 (ours)
0.972
0.811
ReSCO-16 (ours)
1.000
0.859
5.3 Reheated Gradient- based Discrete Sampling for Combinatorial Optimization
Combining results in Section n and TV we obtain the Reheated Sampling for Combinatorial Optimization algorithm (ReSCO), which is summarized in Algorithm ReSCO is compatible with any gradient- discrete sampler. In this paper, we use the same sampler as Sun all (2023E). ReSCO adds minimal overhead, the reheat mechanism can be cheaply implemented, which is verified in the experiments section.
6 Experiments
We conduct thorough empirical evaluation of our method ReSCO on various graph combinatorial optimiza- tion tasks, including Max Independent Set (MIS), MaxClique, MaxCut and Graph Balanced Partition. For all problems, we follow the experimental setup in Sun et all (20235).
We found that ReSCO requires minimal hyperparameter tuning. For Max Independent Set, MaxClique and MaxCut, we use a value threshold c 0.01, a wandoring length threshold N 100, and a sample size M 100 for all tasks. The skip step threshold lakip 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. For Graph Balancod Partition, the value threshold is adjusted per problem set, and the details are provided in Appendix Hi
We present the results of experiments on Max Independent Set and MaxClique in this section, and put the problem description and datasct information in Appendix H. The problem description, datasct information and experimental results of MaxCut and Graph Balanced Partition are presented in Appendix G and H respectively.
9

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm Reheated Sampling for Combinatorial Optinization
temperature schedule T(-), sampling chain length L, value threshold e, wandering length thresh- old N, sample sive M, skip step threshold lskip
Input:
2: Initialize: state critical temperature & = fskip, temperature indicator step Temp = 1, maximum
specific heat = reheated = false
3: for = to do St f- -SA--radient-baseee www.-baasddSSlpee......-- ( ((Temp))
To determine critical temperature 8
if 2 tskip and not reheated then Calculate ((t) as in equation I if C(I) 2 C then C + C(t) t-
end if
10:
end if
b To detect "wandering in contours"
11:
Condition equation holds then
12: TTmpp + p. Reheat to critical temperature
13: end if
14:
TTempp TTemp" +1
15:
end for
Table 2: Results of ReSCO and recently proposed methods when solving (70-FR-(700-800 problem set.
ReSCO surpasses all of them and obtains the best result on this problem set to our knowledge.
ReSCO-32
GFlowNets (Kim all, 2024
DIFUSCO
T2T
Method
(ours)
(Sun Yang, 2023
all 2124
Results
45.24
41.14
40.35
41.37
6.1
Results and Analysis
6.1.1 Multiple Chains
We report the results of MIS and MaxClique in Table B and Table (Left) respectively, with KaMIS serving the baseline against which we measure performance drop. We see that ReSCO under the multi- chain setting surpassed all learning- based and sampling methods and even found better solutions than using optimization solvers in some tasks.
We also compare the results ReSCO and other recently proposed methods which also run experiments on MIS-EER-1700-S00, and the results are reported in Table shows that ReSCO surpasses all of the recently proposed methods and obtains the best result on this problem set to our knowledge.
6.1.2 Single Chain
When comparing the results between iSCO and RoSCO under multi-chain setting, the improvements of ReSCO may seem minor. This is because running multi-chains can mitigate the wandering in contours problem to some extent, but the extra computational cost compared to the single-chain setting is extremely large.
We report the runtime of single-chain iSCO, single-chain ReSCO and multi-chain (32-chains) iSCO when solving MIS problem sets in Table M (Right). The experiments were conducted on a single A6000 with multiple chains executed in parallel, using the same implementation used by the iSCO paper. We see that the runtime of 32-chain iSCO least times of the runtime of single-chain iSCO, and the runtime of 32-chain iSCO is 28 times of the runtime of single-chain iSCO when solving MIS-ERR|(700-88
10

---

Published in Transactions on Machine Learning Research (03/2025)
Table 3: Results of MIS on three benchmarks provided by Quu et all (2022). Baselines involve methods using optimization solvers (OR), Reinforcement Learning (RL), Supervised Learning (SL) equipped with Tree
Search (TS), Greedy decoding (G), and Sampling (S). S-N represents running N chains for each problem.
Methods that can't produce results in 10x time limit of DIMES are labeled N/A.
SATLIB
(RR-770-800)
ER-[9000-11000
Method
Type
Size f
Drop +
Size
Drop
Size 1
Drop +
KaMIS Gurobi
OR
425.96"
44.87*
381.31
OR
425.95
0.00%
41.38
7.78%
N/A
N/A
SL+TS
N/A
N/A
38.8
13.43%
N/A
N/A
Intel ct all
SL+G
420.66
1.48%
34.86
22.31%
284.63
25.35%
DGL (Bol her el. all, 2022
SL+TS
N/A
N/A
37.26
16.96%
N/A
N/A
LwD [A hn all, 2020
RL+S
422.22
0.88%
41.17
8.25%
345.88
9.29%
RL+G
421.24
1.11%
38.24
14.78%
320.50
15.95%
DIMES Qiu et al
2022
RL+S
423.28
0.63%
42.06
6.26%
332.80
12.72%
S-1
422.65
0.78%
43.37
3.3%
377.44
1.0%
iSCO
(unn et all 20236
S-32
424.16
0.42%
45.16
-0.6%
383.50
-0.5%
S-1
422.76
0.75%
44.18
1.5%
378.25
0.8%
ReSCO(Ours)
S-32
424.21
0.42%
45.24
-0.8%
383.75
-0.6%
Table 4: Results of Simulated Annealing with different gradient- based samplers aith/without reheat using single-chain setting on MIS-FRR-(000800] problem set. Reheat improves the results for all the gradient-based samplers.
PAS (ISCO/ReSCO)
DMALA
DLMC
Sampler
(Zhang all 2022
(Sun all 2ORKE
Without reheat
43.37
42.92
42.94
With reheat
44.18
43.58
43.64
When we turn to the single-chain setting (which is the common setting in most algorithms). the improvement of ReSCO is significant. For example, under the single-chain setting, iSCO obtains 43.37 while ReSCO obtains 44.18 on MIS-ERR-1000-800 problem set, and iSCO obtains 377.44 while ReSCO obtains 378.25 on LIS-ER--9000-11000 problem set (see Table B).
Also, single-chain ReSCO surpasses single-chain iSCO given the same runtime when solving MIS-ER- 800]. We compare the performance of single-chain iSCO and single-chain ReSCO given the same runtime when solving MIS-ER-1700-S00), and report the results in Figure mr.. Though iSCO performed better in the first 200 seconds, it was surpassed by ReSCO the remaining 800 seconds. Besides, iSCO showed a tendency to stay that level while ReSCO still showed an incrcasing trend.
6.2 Effect and Applicability of Reheat Mechanism
We further study the effect of reheat by applying ReSCO and iSCO on a MIS problem. As illustrated in Figure en iSCO (Bc) begins "wandering in contours" within 5,000 steps, failing to find improved solutions thercafter. In contrast, ReSCO (Hdl) manages to escape from "wandering in contours" each time after reheating (marked as green points) and identify better solutions, outperforming iSCO.
Furthermore, we test simulated annealing with three different gradient- based samplers with/without without reheat mochanism on MIS-ER-(700-800) problem set with a singlo-chain setting show the effect of rcheat on different samplers. As can be seen in Table reheat mechanism improves the results of all three gradient- based samplers, proving its efficacy and broad applicability.
11

---

Published in Transactions on Machine Learning Research (03/2025)
45
by DMALA
43.7
48.6
40
35
43.5
Sampled
43.5
Bast Objectvv
30
43.3
Reheat Results
Mon-Rihheal Result
43.3
Non-Rahal Raheat Result
43.2
43.2
ReSCO
15
ISCO
43.0
43.0
42.9
200
400
600
800
1000
100
500
1000
2000
3000
4000
100
500
1000
2000
3000
4000
Time (5)
Wandering Length Threshold M
Werder ing Length Tireshold N
(a)
(b)
(c)
Figure 5: (a): The best value obtained by single-chain iSCO and single-chain ReSCO within the same runtime when solving the MIS-ER-|700-8000 problem set. (b): Performance of Reheated DMALA under different wandering length threshold settings. (c): Performance of Reheated DLMC under different wandering length threshold settings.
6.3
Ablation Study
6.3.1 Final Temperature
To evaluate ReSCO's robustness against variations in the cooling schedule, we conducted experiments on the RBtest dataset with various final temperatures (we did not consider initial temperature due to its demonstrated insensitivity (Sun el all 20237)
We reported the results in Figure 19 which indicate that ReSCO consistently outperforms iSCO on all final temperature values and is relatively robust to different values. In contrast, iSCO's performance declines noticeably with low final temperatures. This suggests that ReSCO's reheat mechanism enables it to be adaptive across a range of temperatures by reheating to the critical temperature each time the current temperature is too low for it to find better solutions.
6.3.2 Chain Length
With constant initial and final temperatures, extending the chain length and slowing the cooling rate generally improves results. We tested the impact of chain length on performance using the RBtest dataset under a single-chain setup, keeping initial and final temperatures at and 10-3, respectively, and varying chain lengths from 1K to 40k. Results illustrated in Figure HE show that extending the chain length boosts performance for both algorithms, with ReSCO consistently outperforming iSCO at varying chain lengths.
6.3.3 Wandering Length Threshold
Among the four new hyperparameters introduced in ReSCO (e, M, N)) determining the wandering length threshold N poses the greatest challenge due to the varying nature of "wandering in contours" across different problems. In fact, setting N too large reduces ReSCO back to iSCO. To assess N's impact on ReSCO's performance, we performed experiments a single-chain setting on the SATLIB and ER-[9900-- 11000) datasets with varying N values, using iSCO's outcomes as reference baseline.
As demonstrated in Figures M and M ReSCO exhibits robust performance across varying wandering length thresholds. It consistently outperforms iSCO in finding better solutions for both datasets, regardless of the threshold chosen.
This claim is further substantiated by Figure sif and STG other gradient-basod discrete samplers: DMALA (Zhang et all, 2022) (Left) and DLMC (Sun ct all, 20235) (Right). We report the results of these two samplers under different wandering length threshold settings when solving (TS--RR- problem set. Both reheated DMALA and DL.MC outperformed their
where we implemented the reheat mechanism in
12

---

Published in Transactions on Machine Learning Research (03/2025)
Apautration Palto
0.810
0.09
0.66
SP9
0.008
2.MM
RebCO
270
Re500
2.83
5CO Powu
1500
0.62
RiéCO
Rx900
3778
1500
1900
12"
10"
10"
10"
10
1x.
5k
10k
20c
201
40c
1000
2303
3000
4000
5000
1000
2000
3000
4020
5000
Tamporata stre
Langh
Larger
(a)
(b)
(c)
(d)
Figure 6: Ablation studics on final temperature (a), chain longth (b), and wandcring length threshold (c) & (d).
reheated counterparts across all threshold settings. These results align with those observed for ReSCO, further demonstrating the robustness and effectiveness of our reheat mechanism across different samplers.
However, cannot find specific pattern of how the wandering length threshold influences the results. We leave this for future direction.
7 Conclusions and Limitations
In this paper, we identify a problematic behavior observed in gradient-based discrete samplers for combi- natorial optimization, denoted as "wandering in contours". To counteract this issue, we introduce a novel reheat mechanism inspired by the principles critical temperature and specific heat. This approach enables effective detection of this undesired behavior and resets the temperature an optimal level that ensures balance between exploration and exploitation. Our extensive experimental results validate the efficacy of the proposed method. However, there is still room for improvement. We list few future directions below:
Hyperparameter Tuming Although ReSCO requires minimal hyperparameter tuning, further research on optimizing its parameters could improve its performance. For example, determining the wandoring length threshold N remains challenging, and developing a more systematic approach for setting this hyperparameter is an important direction for future work.
Broader Applicability While our reheating mechanism significantly enhances gradient-based discrete samplers for various combinatorial optimization (CO) problems, its reliance on gradient information limits its applicability to CO problems with non non-differentiable objectives. A future research is to extend our method to non-diffcrentiabl CO problems and more general optimization tasks in the future.
Theoretical Analysis We have demonstrated the effectiveness of our reheat mechanism through extensive experiments. However, theoretical analysis of the reheat mechanism is still lacking. Providing thcoretical foundation for our method will offer deeper insights into its behavior.
References
Emile HL Aarts et al. Simulated annealing: Theory and applications. 1987.
David Abramson, Mohan Krishnamoorthy, and Hemry Dang. Simulated amnealing cooling schedules for the school timetabling problem. Asia-Pacific Journal of Operational Research, 16:1 22, 1999.
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent. sets. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceudings of Machine Learning Research, pp.
PMLR, 2020.
A. Anagnostopoulos, L. Michel, P. Van Hentenryck, and Y. Vergados. simulated anncaling approach the traveling tournament problem. Journal of Scheduling, 9(2):177-193, 2006. ISSN 1099-1425. doi: 10. 10.1007/410051-000-77188
13

---

Published in Transactions on Machine Learning Research (03/2025)
Christophe Andrieu and Johannes Thoms. A tutorial adaptive meme. 343-373, 2008.
Statistics and computing, 18:
Atanu Basu and L. Neil Frazer. Rapid determination the critical temperature in simulated annealing inversion. Science, 449(4975):1409-1477 1990.
Maximilian Böther, Otto KiSSig, Martin Taraz, Sarel Cohen, Karen Scidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization, 2022.
Weiwei Cai and Lin Ma. Applications of critical temperature in minimizing functions of continuous variables with simulated annealing algorithm. Computer Physics Communications, 181(1):11-16, 2010a. ISSN 0010-4655.
Weiwei Cai and Lin Ma. Applications of critical temperature in minimizing functions of continuous variables with simulated anncaling algorithm. Computer Physics Communications, 181 (1):1111,, 2010b. ISSN 0010-4655. doi: https://doi.org/ (0..0166..ccc22000000.00 00.00000...............
JR Cruz and Chang Chung Yu Dorea. Simple conditions for the convergence of simulated annealing type algorithms. Journal of applied probability, 3584):885 8885-99,, 1998.
Hanjun Dai, Xinshi Chen, Yu Li, Xin Gao, and Le Song. A framework for differentiable discovery of graph algorithms. 2020.
Daniel Delahaye, Supatcha Chaimatanan, and Marcel Mongeau. Simulated annealing: From basics to appli- cations. Handbook of metaheuristics, pp. 1-35, 2019.
Ronald A DeVore and Vladimir N Temlyakov. Some remarks greedy algorithms. Advances in computa- tional Mathemalies, 5:173 187, 1996.
K. Fukumizu and Amari Local minima and plateaus in hierarchical structures of multilayer perceptrons. Neural Networks, 1333)3317-377, 2000. ISSN 0893-6080.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6):721-741, 1984.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Sussman Grathwohl, Dale Schuurmans, and Hanjun Dai. DISCS: A benchmark for discrete sampling. In ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023.
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops Look a gradient: Scalable sampling for discrete distributions. In International Conference on Machine Learning, pp. 3831-3841. PMLR, 2021.
Jorge Haddock and John Mittenthal. Simulation optimization using simulated anncaling. Computers B industrial engineering, 22(4):387-335 395, 1992.
H. Hoos and Stutzle. Satlib: An online resource for research on sat. In H. van Maaren P. Gent and T. Walsh (eds.), SAT2000, pp. 283 292. IOS Press, 2000.
Nikolaos Karalias and Andreas Loukas. Frdos goes neural: an unsupervised learning framework for com- binatorial optimization on graphs. Advances in Neural Information Processing Systems, 33:6659 6672, 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Minsu Kim, Sanghyeok Choi, Jiwoo Son, Hyeonah Kim, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with gllownets for combinatorial optimization. arXiv preprint arXim:2003.07041 2024.
Scolt. Kirkpatrick, C Daniel Gelalt Jr, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671 680, 1983.
Ailsa H Land and Alison G Doig. An automatic method for solving discrete progremming problems. Springer, 2010.
Lev Davidovich Landau and Evgeny Mikhailovich Lifshitz. Thcoretical physics, vol. 5: Statistical physics, 1976.
Jure Leskovec and Andrej Krevl. SNAP Datascts: Stanford large network dataset collection. http://ssmt stanford. edu/data, June 2014.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Bianciia and Roman Garnett (eds.), Advances in Newral Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 537-546, 2018a.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in newral information processing systems, 31, 2018b.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint drXiv:2012.13349, 2020.
Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. arXiv preprint arXiv: 1903.00614, 2019.
Yaghout Nourani and Bjarne Andresen. A comparison of simulated anncaling cooling strategies. Journal of Physics A: Mathematical and General, 31 (11)):3337, 1998.
Ibrahim Hassan Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of operations research, 41:421-451. 1993.
Patrick Pynadath, Riddhiman Bhattacharya, Arun Hariharan, and Ruqi Zhang. Gradient-based discrete sampling with automatic cyclical scheduling. Advances in Neural Information Processing Systems, 2024.
Ruizhoug Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems 35, 2022.
Benjamin Rhodes and Michael Gutmann. Enhanced gradient-based meme in discrete spaces, 2022.
Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
Maximilian A. R. Strobl and Daniel Barker. On simulated annealing phase transitions in phylogeny re- construction. Molecular Phylogenetics and Evolution, 101:46 55, 2016. ISSN 1055-7903. doi: https: 10t.:/....................
Haoran Sun, Hanjun Dai, Wei Xia, and Arun Ramamurthy. Path auxiliary proposal for meme in discrete space. In International Conference on Learning Representations, 2021.
Haoran Sun, Hanjun Dai, and Dale Schuurmans. Optimal scaling for locally balanced proposals in discrete spaces, 2022.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Haoran Sun, Hanjum Dai, Bo Dai, Haomin Zhou, and Dale Schuurmans. Discrete langevin samplers via wasserstein gradient flow. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 6290-6313. PMLR, 25-27 Apr 2023a.
Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 32859-3222 32874. PMLR, 23-20 29 Jul 2023b.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Ad- vances in Neural Information Processing Systems, 36:3706-377 37000-373,.-00 2023.
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maximum constraint satisfaction. Frontiers Artif. Intell, 3:580607, 2020. doi: 10.3389/fral 2a.00//fra.2200000 wtt.:/ai.....0000000 580005
Peter JM Van Laarhoven, Emile HL Aarts, and Jan Karel Lenstra. Job shop scheduling by simulated annealing, Operations research, 40(1):113 125, 1992.
Haoyu Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimiza- tion with principled objective relaxation. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022. ISBN 9781713871088.
Haikun Wei, Jun Zhang, Florent Cousseau, Tomoko Ozeki, and Shun-ichi Amari. Dynamics of learning near singularities in layered networks. Neural Computation, 20(3):813-848 843- 2008. doi: 10.1162/neco.2000 2007. 12-06-414.
Yue Xiang, Dongyao Zhu, Bowen Lei, Dongkuan Xu, and Ruqi Zhang. Efficient informed proposals for dis- crete distributions via newtons series approximation. In International Conference on Artificial Intelligence and Statistics, pp. 7288-7310. PMLR, 2023.
Ke Xu, Frédéric Bousscmart, Fred Hemery, and Christophe Lecoutre. Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 171 534, 2007. doi: 10.1016/j.
Yuki Yoshida and Masato Okada. Data-dependence of plateau phenomenon learning with neural net- workstatistical mechanical analysis. Journal of Statistical Mechanics: Theory and Experiment, 2020(12): 124013, December 2020. ISSN 1742-5468.
Giacomo Zanella. Informed proposals for local meme in discrete spaces. Journal of the American Statistical Association, 855)55 Apr 2019. doi: 10. (0.1000/01221455 100114592200000 251..15555....
Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochastic gradient meme for bayesian deep learning. arXiv preprint arXiv:1902.0980 039332 2019.
Ruqi Zhang, Xingchao Liu, and Qiang Liu. A Langevin-like sampler for discrete distributions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Mochine Learning PMLR, 17-23 Jul 2022.
Research, pp.
Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pp. 1980 2022. PMLR, 2017.
16

---

Published in Transactions on Machine Learning Research (03/2025)
A Broad Existence of "Wandering in Contours"
To demonstrate the widespread occurrence of wandering in contours in gradient-based discrete samplers, analyzed the trajectory of the objective values of DMALA (Zhang et all 2022), as depicted in Figure M.
Figure 7 (Left) reveals that DMALA begins to wander in contours after 4000 steps, and wastes about 3000 steps before it escapes from wandering in contours. However, it continues to wander contours as soon as il escapes and wastes the rest sleps oblaining no improvement. Figure @ (Right) illustrates that the objective values continue to fluctuate but remain very similar or identical to the stop value, indicating that DMALA is indeed wandering in contours after this point.
The behavior exhibited in Figure 0 closely resembles that shown in Figures 20 & 26 This similarity sug- gests that despite DMALA's simultancous update of all dimensions, which thcorctically allows for more comprehensive exploration, it still exhibits wandering in contours nearly identical to PAS (Sun el all, 2021).. This observation provides strong evidence that wandering in contours a common phenomenon among gradient-based discrete samplers.
40
+3.999e1
0.010
35
0.009
Objective Value
30
Objective Value
25
0.008
Stop Value
20
Converge to Stop Value Wandering in Contours Stop Value Points Optimal Value
0.007
15
0.006
10
5
0.005
1000
3000
5000
7000
9000
7500
8000
8500
9000
9500
10000
Step
Step
Figure 7: Left: The trajectory of objective values of DMALA, which is similar to Figure ME showing the existence of "Wandering in Contours". Right: A detailed view of objective value after DMALA wanders in contours. Its similarity with Figure 2n further proves the existence of "Wandering in Contours" DMALA.
B Comparison of "Wandering in Contours" with Plateau Phenomenon
The "wandering in contours" behavior observed in gradient- discrete sampling with simulated annealing resembles the Plateau Phenomenon Fnkumizn X7 Amari (2n0)); Wei ct all (2008); Yoshida Ar Okadal (2020), encountered in the training of deep learning models. In deep learning, a plateau refers to a phase where the training Joss decreases at an exceedingly slow rate over many epochs. This is akin to "wandering in contours", where the algorithm repeatedly samples solutions around a stop value without making progress. This similarity highlights a pervasive challenge in gradient- based optimization algorithms, extending across both continuous and discrete domains. Addressing the platean phenomenon typically involves modifying neural network architectures, approach that does not translate to the discrete sampling problems discussed in this paper.
C Comparison of Reheating with Stepsize-tuning Methods
Rehcating mochanism fundamentally different from existing stopsizo-tuning methods explored in MCMC literature (Zhang et al., 2014 Andrien Thoms, 2003). Stepsize tuning methods, such as adaptive step- size (Andrieu & Thoms
2008) cyclical stepsize (Zhang et. all 201), control how far the next state will
17

---

Published in Transactions on Machine Learning Research (03/2025)
be from the current state without changing the stationary distribution. In contrast, reheating mechanism changes the stationary distribution through temperature adjustment.
In fact, stepsize-tuning methods cannot effectively mitigate the problem of wandering in contours. To illustrate this, consider the update rule of the DMALA (Zhang et all 2022))
1 [Vf(z)) m.)
(x) x²)
p(a((=) Softmax
2a
When wandering in contours occurs, the temperature T' inside the algorithm tends to be very small even close to O. In this case, regardless of how the stepsize is tuned, the gradient term remains dominant in the update rule. Consequently, the misleading gradient information perpetuates the wandering in contours behavior.
To empirically validate this, we conducted experiments using the iSCO algorithm on three MIS problems. Upon detecting wandering in contours, we adjusted the stepsize an larger values ag and recorded the final ratios (ISCO result divided by bascline result) shown in Table F
Table 5: Effect of Stepsize-tuning on solving Wandering in Contours
Q1
022
Problem
Problem 2
Problem
0.2
0.2
0.79
0.83
0.83
0.2
1
0.79
0.83
0.83
0.2
10
0.79
0.83
0.83
0.2
105
0.79
0.83
0.83
0.2
00
0.79
0.83
0.83
As evident from Table D. increasing the stepsize when wandering in contours is detected does not improve performance across all three problems. This empirical evidence supports our theoretical argument that stepsize-tuming is ineffective in addressing the wandering in contours issue.
Settings of Experiments
We report the settings of all the experiments in Table
Table 6: Setting of hyper-parameters in the experiments. ERI represents ER-[770-8000 problem set, and ER2 represents ER- BR-19000-11000) problem set.
MIS
MaxClique
MaxCut
Datasels
SATLIB
ERI
ER2
Twitter
RBttst.
Optsicom
BA
Initial Temperature T(0)
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Ending Temperature T(L)
1c-5
1c-3
1c-3
1c-2
1c-3
1c-3
1c-6
Chain Length L
1M
200k
400k
1k
1k
25k
50k
Temperature Schedule T(-)
exponentially decay
Sample Size
100
100
100
100
100
100
100
Value Threshold
0.01
0.01
0.01
0.01
0.01
0.01
0.01
Wandering Length Threshold N
100
100
100
100
100
100
100
Skip Step tskip
500
200
350
100
130
100
200
E Determination of Hyperparameters
Beyond the experiments conducted in this paper, we give some methods to choose the four hyperparameters in ReSCO here.
18

---

Published in Transactions on Machine Learning Research (03/2025)
The value threshold should be small number that cover the value fluctuations caused by wandering in contours. A practical heuristic we found is setting to be 10 times the minimal increment in objective values. This approach has proven effective in our experiments for identifying wandering in contours, where was consistently set at 0.01 across all experiments.
The sample size M can be subjectively selected within a certain range without significantly affecting the reheating mechanism.
The skip step tstep is easily identified at the point where the specific heat ends its initial sharp decline.
The wandering length threshold N is bit more difficult to decide. As discussed in Section iR the only requirement for N is that it should not be too small (no smaller than 100), otherwise reheat will happen too often. And in practice, N will not influence the final results too much. Figure mG & Mi prove it: for all the chosen numbers varying from 100 and 5000, the results of ReSCO outperform the results of iSCO. In fact, iSCO can be seen as special case of ReSCO with an extremely large N (i.c. larger than the chain length), in which reheat will never happen.
F Problem Setup for MIS and MaxClique
F.1 Max Independent Set
Problem Description Given graph G (V, F)) where [V| d, the Max Independent Set (MIS) problem aims to find the largest set of vertices no two of which are adjacent. Representing the inclusion of node i in the set as x₁ = and exclusion as 2; = 0, the MIS problem can be framed as the optimization problem:
max (0.1)
1=1
subject to:
T5 = V(,))E
Denote the adjacency matrix of G as A, by selecting a penalty term X, we can construct the energy function
as:
Ax 2
f(x) = T; +
We choose = 1.0001, which is the same as Sun et all (2123)), and report -f(x) as the final result.
Datasets Following Sun all (20230), we use the MIS benchmark from Qiu el al. (2022), consisting of one realistic dataset SATLIB (Hoos & Striza 201) and ErdsRényi(ER)) random graphs of different sizes. We directly test ReSCO the test datasets provided by Goshvadi all (202k). which contains the following datasets:
SATLIB: consists of 500 test graphs, each with at most 1347 nodes and 5978 edges.
ER-0080-:00):: consists of 128 test graphs with 700 to 800 nodes.
ER-|9000-11000]; consists of 16 test graphs with 9000 to 11000 nodes.
F.2 Max Clique
Problem Description Given graph G (V, E) with |V d, the Max Clique (MC) problem secks the largest subset of vertices such that every two distinet vertices are adjacent. Using binary representation
where z; = 1 indicates node is part of the clique and 2; 0 otherwise, the MC problem can be defined
19

---

Published in Transactions on Machine Learning Research (03/2025)
max 26 (0.1)
subject to:
Fy0 =0 0, v(i,) $ E
Letting A' be the adjacency matrix of the graph complement, we can establish the energy function:
x A'x
f(x)
24
2
1=1
To align with prior work, we set À 1.0 as Sun et all (2023L), and the result reported (f()).
Datasets Following Sun et all (202210), we test ReSCO on:
RB: synthetic datascts generated with R.B model ct.ll 2007)) consists of 500 graphs, each with
at most 475 nodes;
Twitter: a realistic Twitter datasct (Leskovec Krey 201 most 247 nodes.
consists of 196 graphs, each with
G Experimental Information on MaxCut
Problem Description Given an undirected graph G (V, where [V] d, the MaxCut problem aims to partition V into two disjoint subsets such that the number of edges between the subsets is maximized. Each vertex i is assigned to partition represented by 2; E (0,1), where x; 1 indicates that vertex is in one subset and x; = 0 indicates it's in the other. Then MaxCut problem can be formulated as:
(2x; - 1))(2r, - 1)
Σ
max ae ()
(LJ)E
We can directly construct the energy function due to MaxCut is unconstrained, which is:
(2x; 1)(2x, 1)
f(x) =- Σ
2
(J)EE
and we report -x(x) ad the final result.
Datasets
Following Sun (2023b), we apply the benchmark in (Dai al. 2020) and (Karalias M and and choosing the following datasets:
Loukas
2P2
BA: synthetic datasets generated with BarahásiAlbert model, consisting of 1000 graphs, with nodes number varying from 16 to 1000;
Optsicom: realistic datasets consisting of ten graphs, each with at most 125 nodes.
20

---

Published in Transactions on Machine Learning Research (03/2025)
Table 7: The improvement of approximation ratios compared to iSCO on MaxCut Problems; The second line of BA graphs represents the nodes number of graphs the dataset.
BA graphs
Methods
Optsicom
16-20
32-40
64-75
128-150
256-300
512-600
1024-1100
ReSCO
+0
+2e-6
+0
+0
+le-4
+ +le4
+1e-5
+0
Results Because iSCO has been shown surpass all the learning- bearningbbased methods and classical methods in baselines and obtained even better results compared to optimization solvers, only report the improve- ment of approximation ratios of ReSCO compared to iSCO with the single-chain setting the two datasets in Table ?
It's clear that the results obtained by iSCO and RcSCO are almost the same, and ReSCO surpasses iSCO slightly on several datasets. This is because iSCO has found solutions that are good enough, making exploring other parts of the solution space less useful.
H Experimental Information on Graph Balanced Partition
Problem Description and Datasets The Graph Balanced Partition problem aims divide the nodes of given graph G (V, E) into K disjoint subsets ,,,... S2, while simultancously minimizing the number of edges that run between different partitions and ensuring that the partitions remain balanced in size. We apply the same settings and implementations as in (Goshvadi et_ all, 2023), and compare the results of ReSCO-1 (ours) and iSCO-1
(Sun al, (0235) using the following three metries:
Objective Value: Computed based on the edge-cut ratio and balanceness, as described in (Gosh- Vadi ot all, 2023). This metric reflects both the efficiency minimizing the cut edges and the degree of balance among partitions.
Edge Cut Ratio:
Mcasures the proportion of edges in the graph that are cut between different partitions. lower edge cut ratio indicates fewer inter-partition connections, which is desirable.
Balanceness: Quantifies how evenly the nodes are distributed across the partitions. A high bal- anceness indicates that the partitions are of similar size, adhering to the balance constraint.
We compare the results of ReSCO-1 and iSCO-1 on five widely used TensorFlow graphs: VGG, MNIST-conv, ResNet, AlexNet, and Inception-v3. Detailed information regarding these graphs can be found in (Nazi ef all, 2019).
Hyperparameter Setting For all the Graph Balanced Partition experiments, our setup is the same as in (Sun et all (023T). For the additional hyperparameters in ReSCO-1, we set the skip step takip 200k, and the wandering length threshold N 1k. The value threshold is adjusted per problem set, which is reported in Table R
Table 8: Value Thresholds for Different Graph Balanced Partition problem sets.
Problem Sets
VGG
MNIST-conv
ResNet
AlexNet
Inception-v3
Value Threshold
0.5
0.5
0.5
2
Results We report the Objective Value, Edge cut ratio, and Balanceness of solutions found by ReSCO-1 and iSCO-1 on the five TensorFlow graphs in Table g.
As shown, ReSCO-1 consistently outperforms iSCO-1 across all five tasks in terms of Objective Value, the primary metric directly optimized in the experiments. This remonstrates the effectiveness of our proposed
21

---

Published in Transactions on Machine Learning Research (03/2025)
Table 9: Performance of ReSCO-1 and iSCO-1 on Graph Balanced Partition problems.
Metric
Method
VGG
MNIST-conv
ResNet
AlexNet
Inception-v3
Objective Value f
iSCO-1
-261.86
-68.52
-6483.95
-104.60
-4565.87
ReSCO-1
-211.28
-53.67
-644944
-72.18
-4563.21
Edge cut ratio
iSCO-1
0.058
0.051
0.100
0.041
0.056
ReSCO-1
0.059
0.025
0.099
0.025
0.055
Balanceness
iSCO-1 0.95
0.92
0.99
0.97
0.99
ReSCO-1 0.97
0.62
0.99
0.94
0.99
reheat mechanism. Although Edge Cut Ratio and Balanceness are not explicitly optimized by the objective, ReSCO-1 still achieves better Edge Cut Ratio in four out of five tasks. For Balanceness, the results obtained by ReSCO-1 are competitive in most problem sets.
22


Reviews:
[{"review_id": "2cHrEpdpjv", "reviewer": "Reviewer_jKxQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n- The problem of wandering in contours in gradient-based sampling for combinatorial optimization is pointed out.\n- A solution for wandering in contours problem, a reheating mechanism based on the critical temperature, is proposed.\n\n[Weaknesses]\n- The proposed reheating technique seems somewhat straightforward. The theoretical justification of its algorithm design is unclear. For example, the detection of wandering in contours is affected by the scale of the objective function and is not invariant to the monotonically increasing transformation of $f$.\n- The experimental evaluation might be limited. The previous work [Sun et al. 2023b] also tackles the balanced graph partition and traveling salesman problems, whereas this paper only treats MIS, MaxClique, and MaxCut.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a simulated annealing method using gradient-based sampling for combinatorial optimization. Specifically, the authors point out the problem, termed wandering in contours, observed in existing methods and introduce the reheating technique into gradient-based sampling methods to improve the search efficiency. The experimental evaluation shows that the proposed method outperforms existing gradient sampling-based simulated annealing methods and data-driven algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- As the experimental evaluation in this paper seems to be limited, it would be better to discuss the performance of the proposed method on various combinatorial optimization problems. Particularly, the performances on the balanced graph partition and traveling salesman problems treated in the previous paper [Sun et al. 2023b] will be useful.\n- [Minor comment] To apply the gradient-based discrete sampling to combinatorial optimization, the objective function $u$ and constraint function $v$ should be differentiable with respect to solution $x$. Therefore, problems to which gradient-based discrete sampling methods can be applied are limited compared to ordinary simulated annealing. The limitation of the proposed method and gradient-based sampling for combinatorial optimization should be clarified.", "broader_impact_concerns": "I do not have concerns about the ethical implications of this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XZkPbkiiGW", "reviewer": "Reviewer_j436", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The manuscript is well-structured and well-written. The experimental study is comprehensive.\n2. The combination of gradient-based sampling and reheating boosts the overall performance, which is a meaningful improvement in the area.\n\nWeakness: \n1. Section 4.2, the analysis of what causes \"wondering in contours\" is not strongly convincing. Some \"wondering in contours\" phenomenons may be caused by misleading gradient information, but the main reason of such phenomenon could come from the problem itself: combinatorial problems' landscape is often multi-modal, that is, multiple solutions can have the same (or very similar) objective values. Gradient-based methods are very likely  \"wonder in contours\" over this landscape.\n2. Section 4.2, The explaination of low temperature environment of simulated annealing (SA) is questionable.  At the low temperature stage, SA tends to exploit a neighbor region, resulting in falling into a local optima, rahter than forwarding along a road and getting farther away from the beginning solution (i.e., wondering in contours).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript reports the \"wondering in contours\" phenomenon in combinatorial optimization and  proposes the reheated gradient-based discrete sampling to tackle the phenomenon. The main contribution is the combination of gradient-based sampling and reheating, which enhances the exploration over the search space.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Regarding Weakness 1, please refine the analysis of  \"wondering in contours\". A suggestion is empirically investigating whether arbitrary gradient-based method (not only SA) can wonder in contours. If so, \"wondering in contours\" comes from the problem landscape, rather than caused by misleading gradient. \n2. Regarding Weakness 2, please correct the explaination of low temperature environment of SA.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "e5cY9IcMIx", "reviewer": "Reviewer_zis4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper proposes a novel reheating mechanism that addresses a key inefficiency in gradient-based discrete sampling, enhancing solution quality in combinatorial optimization.\n2) Strong empirical results are provided, showing significant improvements across multiple benchmark problems.\n3) The motivation is clearly stated, and the practical impact of the reheating mechanism is well-supported by the numerical experiments.\n\nWeaknesses: Theoretical guarantees, such as convergence proofs for the simulated annealing framework, are lacking.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel reheating mechanism to address the inefficiencies of gradient-based discrete sampling methods for combinatorial optimization (CO). It identifies a critical issue termed \"wandering in contours,\" where the algorithm gets stuck exploring solutions with similar objective values. The paper introduces a reheating mechanism inspired by physics concepts such as critical temperature and specific heat, which facilitates escaping from these suboptimal contours. The proposed approach shows significant empirical improvements over existing sampling-based and data-driven CO methods on Max Independent Set and MaxClique.\n\nThe contributions of this paper are clear and practical, and the proposed reheating mechanism adds a valuable layer of robustness to existing sampling approaches for CO. However, while the empirical results are promising, the work lacks theoretical guarantees, such as the convergence analysis. Adding such theoretical guarantees would strengthen the impact and provide a deeper understanding of the effectiveness of the proposed reheat method. Overall, the paper presents an interesting and useful enhancement to discrete sampling techniques and is a solid contribution to the field.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Adding theoretical guarantees would strengthen the impact and provide a deeper understanding of the effectiveness of the proposed reheat method.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommend acceptance.

I am marking this as "accept with minor revision" to allow the authors to incorporate changes addressing the reviewer comments into the paper, especially regarding the comments of Reviewers jKxQ and j436, as this was not done during the discussion phase.

Please note that TMLR does not have a strict page limit, so you can just add the results of the new experiments in the main text.
Decision: Accept (poster)