Regularized Langevin Dynamics for Combinatorial Optimization
Authors: Shengyu Feng
Yiming Yang
Venue: ICML 2025 poster (2025)
Keywords: Combinatorial Optimization; Neural Combinatorial Optimization; Simulated Annealing; Langevin Dynamics
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We proposed a novel sampling framework called regularized langevin dynamics for combinatorial optimization, applying it to both simulated annealing method and neural network solvers.

Abstract: This work proposes a simple yet effective sampling framework for combinatorial optimization (CO). Our method builds on discrete Langevin dynamics (LD), an efficient gradient-guided generative paradigm. However, we observe that directly applying LD often leads to limited exploration. To overcome this limitation, we propose the Regularized Langevin Dynamics (RLD), which enforces an expected distance between the sampled and current solutions, effectively avoiding local minima. We develop two CO solvers on top of RLD, one based on simulated annealing (SA), and the other one based on neural network (NN). Empirical results on three classic CO problems demonstrate that both of our methods can achieve comparable or better performance against the previous state-of-the-art (SOTA) SA- and NN-based solvers. In particular, our SA algorithm reduces the runtime of the previous SOTA SA method by up to 80\%, while achieving equal or superior performance. In summary, RLD offers a promising framework for enhancing both traditional heuristics and NN models to solve CO problems. Our code is available at https://github.com/Shengyu-Feng/RLD4CO.

Regularized Langevin Dynamics for Combinatorial Optimization
Shengyu Feng' Yiming Yang'
Abstract
due to their non-convex nature and often NP-hard com- plexity, making them intractable in polynomial time by exact solvers. Traditional CO algorithms often rely on hand- crafted domain-specific heuristics, which are costly and difficult to design, posing significant challenges in solving novel or complex CO problems.
This work proposes a simple yet effective sam- pling framework for combinatorial optimization (CO). Our method builds on discrete Langevin dy- namies (LD), an efficient gradient-guided genera- tive paradigm. However, we observe that directly applying L.D often leads to limited exploration. To overcome this limitation, we propose the Reg- ularized Langevin Dynamics (RLD), which en- forces an expected distance between the sampled and current solutions, effectively avoiding local minima. We develop two CO solvers on top of RLD, one based on simulated annealing (SA), and the other one based on neural network (NN). Empirical results on three classic CO problems demonstrate that both of our methods can achieve comparable or better performance against the pre- vious state-of-the-art (SOTA) SA- and NN-based solvers. In particular, our SA algorithm reduces the runtime of the previous SOTA SA method by up to 80%, while achieving equal or superior per- formance. In summary, RLD offers a promising framework for enhancing both traditional heuris- tics and NN models to solve CO problems. Our code is available at https: : //gtttbt....////// com/ Seennguu-Peggge Feng/RID4CO. RLD4CO.
Recent advances in simulated annealing (SA) (Kirkpatrick et al., 1983) and neural network (NN)-based learning (Ben- gio et al., 2020; Cappart et al., 2023) algorithms have rede- fined approaches to combinatorial optimization by minimiz- ing dependence on manual heuristics:
Simulated Annealing: SA is general-purpose purpose opti- mization algorithm that explores the solution space probabilistically, avoiding dependence on problem- specific heuristics. Although its cooling schedule and acceptance criteria require some design decisions, SA is highly adaptable across diverse problems free from detailed domain knowledge (Johnson et al., 1991).
Neural Network Models: NN-based methods lever- age supervised learning (Kool et al., 2019; Zhang et al., 2023; Sun & Yang. 2023; Li et al., 2023; 2024), re- inforcement learning (Khalil et al., 2017; Qiu et al., 2022; Feng & Yang, 2025) or unsupervised learning (Karalias & Loukas, 2020; Wang et al., 2022; Wang & Li, 2023; Sanokowski et al., 2024) to learn opti- mization strategies directly from data. By automating the process, these models replace hand-crafted heuris- ties with learned representations and decision-making processes, enabling tailored solutions refined through training rather than manual adjustment.
1. Introduction
Combinatorial Optimization (CO) problems are central chal- lenges in computer science and operations research (Pa- padimitriou & Steiglitz, 1998), with diverse real-world ap- plications such as logistics optimization (Chopra & Meindl, 2001), workforce scheduling (Ernst et al., 2004), finan- cial portfolio management (Rubinstein, 2002; Lobo et al., 2007), distributed computing (Zheng al., 2022; Feng et al., 2025a), and bioinformatics (Gusfield, 1997). Despite their wide-ranging utility, CO problems are inherently difficult
Langevin dynamics (LD) (Welling & Teh, 2011) and re- lated diffusion models (whose inference is built on LD) (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song & Er- mon, 2019; Song et al., 2020) have greatly advanced the recent development of SA- and NN-based solvers. The key idea of LD to guide the iterative sampling via the gradient for more efficient searching/generation process. This gradient-informed approach has been adapted to the discrete Nomain-examppe 2021), PAFS (Sun et al., 2022), and the discrete Langevin sampler (Zhang et al., 2022) and yields SA solvers that attain state-of-the-art (SOTA) results on various CO bench-
'Language Technologies Institute, Carnegie Mellon University. Correspondence to: Shengyu Feng cectnnguf@ccscmu..cde
include GWG (Grathwohl et al.,
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Regularized Langevin Dynamics for Combinatorial Optimization
marks (Sun et al., 2023). Meanwhile, discrete diffusion models have also shown substantial gains. For example, DIFUSCO (Sun & Yang, 2023) adopts continuous diffusion models from computer vision to address the discrete nature of CO problems, outperforming previous end-to-end neural models in both the solution quality and computational ef- ficiency, Additionally, DiffUCO (Sanokowski et al., 2024) generalizes DIFUSCO by eliminating the need for labeled training data, using unsupervised learning for CO problems. However, existing discrete LD/diffusion methods are mostly adapted from the methods in the continuous domain, this raises important questions: Is there any difference between continuous optimization and combinatorial optimization? Do these adapted methods sufficiently consider the nature of discrete data? Exploring these questions is the central focus of this paper.
2. Related Work
2.1. Simulated Annealing for CO
Simulated Annealing (SA) (Metropolis et al., 1953; Hast- ings, 1970; Neal, 1996; IBA, 2001) is a classic metaheuristic for combinatorial optimization (WANG et al., 2009; Bhat- tacharya et al., 2014; Tavakkoli-Moghaddaa et al., 2007; Seçkiner & Kurt, 2007; Chen & Ke, 2004). However, tradi- tional SA methods often require up to millions of sampling steps for convergence, which limits its applicability on large- scale instances. The recent advances in discrete Markov Chain Monte Carlo (MCMC) offer the potential solutions by accelerating the convergence with locally- ooaall-balanced pro- posals (Zanella, 2017). For example, GWG (Grathwohl et al., 2021) uses first-order approximation to estimate energy changes within the 1-Hamming-bal neighborhood, steering each proposal toward high-density regions. To mit- igate local-optima issues caused by small neighborhoods, PAS/PAFS (Sun et al., 2022) instead samples d coordinates sequentially at each step. Their SA variant iSCO (Sun et al., 2023) achieves SOTA performance on various CO bench- marks. To address the inefficiency of sequential sampling in PAS/PAFS, Zhang et al. (2022) derive a discrete Langevin sampler from the continuous domain, assigning gradient- informed change probabilities to all coordinates in parallel. However, direct transformation of the discrete Langevin sampler into an SA framework overlooks key domain dif- ferences, resulting in severe local-optima issues. In this work, we build on these discrete MCMC developments by proposing simple method that unifies parallel sampling with effective local-optima escape.
Our key observation is that the optimization process is more prone to local optima in discrete domain than in a con- tinuous one. That is, local optima in continuous domain typically have a zero gradient (under the smoothness condi- tion), but this is often not true in a discrete domain, where the gradient may be very large in magnitude, but pointing to an infeasible region. Such a difference makes the escap- ing of local optima more difficult in a discrete domain than in a continuous one, with the common strategy of adding random noise as in LD. We propose to address this issue by enforcing a constant norm of the expected Hamming dis- tance between the sampled solution and the current solution during the searching process. In other words, we control the magnitude of the update in LD,, encouraging the search to explore more promising areas. We name this sampling method Regularized Langevin Dynamics (RLD). We apply RLD on both SA- and NN-based CO solvers, leading to Regularized Langevin Simulated Annealing (RLSA) and Regularized Langevin Neural Network (RLNN). Our em- pirical evaluation on three CO problems demonstrate the significant improvement of RLSA and RLNN over both SA and NN baselines. Notably, RLSA only needs 20% runtime to outperform the previous SOTA SA baselines. And it shows a clear efficiency advantage with either less or more sampling steps. Compared with previous diffusion models, RLNN could be efficiently trained with a local optimiza- tion objective in an unsupervised manner, eliminating the need for labeled data or the estimation of a long-term return throughout the sampling process.
2.2. Neural Solvers for CO
The neural network (NN) models have recently garnered vast attention in solving CO problems (Bengio et al., 2020; Cappart et al., 2023; Feng et al., 2025b). The NN-based solvers could be roughly categorized into three classes ac- cording to the training methods, namely the supervised learning-based (Li et al., 2018a; Gasse et al., 2019; Sun & Yang, 2023; Li et al., 2023; 2024), reinforcement learning- based (Khalil et al., 2017: Qiu et al., 2022; Feng & Yang, 2025), and unsupervised learning- leamiig-bbseed (Karalias & Loukas, 2020; Wang et al., 2022; Wang & Li, 2023; Zhang et al.,
2023; Sanokowski et al., 2024). Although neural networks offer strong expressivity, the end-to-end neural solvers still struggle with the inherent non-convexity of CO problems. To address this, recent works (Sun & Yang. 2023; Li et al., 2023; 2024) have introduced discrete diffusion models, leveraging their success in capturing complex, multimodal distributions from image generation. However, these diffu- sion approaches depend on high-quality training data-often expensive to generate for large-scale CO instances, some- times requiring hours per instance. DiffUCO (Sanokowski
To summarize, we propose a new variant of discrete Langevin dynamics for combinatorial optimization by regu- larizing the expected update magnitude on the current solu- tion at each step. Our method is featured by its simplicity, effectiveness, and wide applicability to both SA- and NN- based solvers, indicating its strong potential in addressing CO problems.
2

---

Regularized Langevin Dynamics for Combinatorial Optimization
al., 2024) alleviates this by using unsupervised learning guided by energy-based models, but its training still relies reinforcement learning across the entire sampling trajectory, leading to inefficiency. In contrast, our RLNN method could be optimized only through a local objective, dramatically improving training efficiency while achieving comparable performance to SOTA NN-based solvers.
where s(x) V log p(x) is known as the score function (gradient of the log likelihood), and a 0 represents the step size. By iteratively performing the above update, the sample x would eventually end up at stationary distribution approximately equal to p(x).
Recently, Zhang et al. (2022) have extended LD to a discrete Langevin sampler by rewriting Equation
3. Preliminary
((x(Ix)= = exp( 1 x (x))
xx'
2n
7(x)
3.1. Combinatorial Optimization Problem
(5)
exp (xx(()) (xxx - -x)
2m |
x
Following Papadimitriou & Steiglitz (1982), we formulate the combinatorial optimization (CO) problem as con- strained optimization problem, i.e.,
((x)
The above distribution could be factorized coordinatewisely. i.e., q(x'lx) II ((x[1x), into a set of categorical dis- tributions:
min a(x) s.t. b(x) =0 0, x- (0.1).8
L 2 (xx))((x+- - x.) (X x2
where a(x) stands for the target to optimize and b(x) 2 0 corresponds to the amount of constraint violation (0 means no violation). In particular, we focus on the penalty form that can be written as
((x|xx x exp
(6)
2c
When x is a binary vector, we can obtain the flipping (chang- ing the value of x; from to 1, or 1 to 0) probability:
min H(x) a(x) + (b((x), XE(O,IJA
(2)
(({ = 1 - x x) = (2 2x,)
1
(7)
2xx
where 8 > is the penalty coefficient that should be suffi- ciently large, such that the minimum of Equation 2 corre- sponds to the feasible solution in Equation 1. H (x) is also generally named as the energy function, and its associated energy-based based model (EBM) is defined as
where af-) stands for the sigmoid function.
In particular, it can be shown that the discrete Langevin sam- pler is a first-order approximation to the locally-balanced proposal (Zanella, 2017):
Pr (x) = exp(- H(x)/T)
q(x(xx) x Vp(x))/pxx)xxxxxxx) x'),
(8)
(3)
7
where k(.,.) is a symmetric function corresponding to here, and log 1(x'(x)) - log)(x) (inside the exponential) is approximated by s(x) ( x).
where 7 > 0 the temperature controlling the smoothness of (x)), and Z = Exe( exp(-H(xx/7 is the nor- malization factor, typically intractable. When is small, the probability mass of p- tends to concentrate around low- energy samples, making the task of solving Equation equivalent to sampling from pr (x). Markov Chain Monte Carlo (MCMC) (Lecun et al., 2006) the most widely used method for sampling from the EBM defined above. How- ever, directly applying MCMC may lead inefficiencies due to the non-smoothness introduced by the small t. To mitigate this issue, the simulated annealing (SA) technique is commonly employed to gradually decrease towards zero during the MCMC process.
exp
xx x 2a
4. Method
4.1. Regularized Langevin Dynamics
Although the discrete Langevin sampler can be directly converted into an SA solver by annealing the temperature т, it nonetheless frequently gets stuck in local optima (see Figure 1 in Section 5.3). As decreases, the gradient term dominates the transition probabilities, driving the flipping probabilities to zero and confining the next sample a very small neighborhood of the current solution. In order to effectively avoid this undesired behavior, we propose to regularize the expected Hamming distance, i.e., the number of changed coordinates between the sampled and current solutions. Concretely, we start from a locally-balancee proposal and impose:
3.2. Langevin Dynamics
Langevin dynamics (LD) (Welling & Teh, 2011) is an effi- cient MCMC algorithm initially developed in the continuous domain. It takes a noisy gradient ascent update at each step to gradually increase the logliieli of the sample:
q(x' (x) X
xx)x s.t. E Exxx' x) Ham(x', x)] = d,
a x' = =+ g. sxx + Vas, &~ C~, INxN), (4)
(9)
3

---

Regularized Langevin Dynamics for Combinatorial Optimization
where Ham(.,)) stands for the Hamming distance and d represents the regularized step size. For simplicity, we always treat d as positive integer in our design. Note that, k(x.x' x') does not necessarily remain symmetric (and thus the locally-ball -ealll-balanced condition may not be satisfied) once the regularization constraint is enforced; instead, it can be chosen to satisfy the constraint at each state.
We call the resultant SA algorithm Regularized Langevin Simulated Annealing (RISA), whose details are summarized in Algorithm 1.
Algorithm Regularized Langevin Simulated Annealing
I: Input: T, d and TO
2: Initialize x E {0, 1 1) ; x*
t
x
Since the exact ratio p(x')/ p(x) is typically intractable, we follow the discrete Langevin sampler to substitute its first-
3: for t = 1, , -''dd t-1
do
4: I f- To
T
order Taylor series expansion:
A <- (2x - 1) ④ (x)
for i 1.... do
x(x'lx) exp ( [x(x)) - -x) x'),
p p- ( A - e))
(10)
8:
C~ w.-Bernoulllg (p)
(Hiss))))amm(* s.t. 1x(x((xx) (Ham(x', xx]] d.
9:
x x, - c) - x:)
10: end for
Empirically, this simple regularization technique substan- tially reduces the tendency to get stuck in local optima. We therefore call our approach Regularized Langevin Dynamics
11: if H(x) < H(x*) then
12: x* f-x
13: end if
(RLD) and proceed describe how it integrates into both SA- and NN-based CO solvers.
14: end for
15: return x*
4.2. Regularized Langevin Simulated Annealing
When x is binary, we could follow Zhang et al. (2022) to let k(x,''' x') = exp [|x' -xll; and explicitly write out the 2a
It is worth noting that k(x,x') = exp sen here just for simplicity, but other strategies may perform just as well. For instance, one could omit the - term and instead normalize the sigmoid outputs:
| xx1x
is cho-
20
expectation in Equation 10 with the flipping probabilities:
(=((x))( Eobaessi 2x,)
N
Σ
d. (11)
2a
a s(x); (1 11-220 2x,))
Pt
d.
(15)
1 s(x); (1 2x,))
Since the gradient of the energy function could be computed in a closed form for various CO problems, here we first assume V (x) is available. Note that the score function of the EBM could be written as
P. min (1, max 0.p:):
(16)
that P. d. Investigating alternative kernel functions normalization strateies-pootentillly adapted to specific problem structures- -off-oofffre-- a promising avenue for future work aimed at further minimizing the approximation error.
8- (x) log p- (x) 1 VH(x).
(12)
To avoid clutter, we denote A = (2x- - 1) @ OOHHHHSS (x), whose i-th coordinate approximates the drop of the energy function we flip the value of x;.
In our implementation, the elementwise sampling is run in parallel and we maintain independent SA processes simultaneously. The whole algorithm could be implemented in a few lines and accelerated with GPU-based deep learn- ing frameworks, such as PyTorch (Paszke et al., 2017) and Jax (Bradbury et al., 2018). An example Py Torch code is attached in Appendix C.
The exact solving of Equation 11 is challenging due to the presence of the sigmoid function. However, when r 0, we observe that the sigmoid function is approximately indicator function:
1) = 20x
1 20x
lim σ T -
A;
0).
(13)
Given the overall RLSA framework, we now address the question of how to compute the gradient of the energy func- tion. Numerous CO problems are defined on graphs and could be formulated in the quadratic form, known QUBO (Lucas, 2014). Let G (V, E) be an undirected graph, with node set V = [1, ... .N., .N. edge set E E V x V, and adja- cency matrix A E {0, N0,1)NxN, In this work, we focus on the following three problems, which have been commonly used in benchmark evaluations for CO solvers
2T
2T
This property allows us to efficiently regularize the SA algorithm with the d-th largest element in A, denoted as
A (d)- We then obtain the flipping probabilities by letting te where 2 0 (e.g., 10-9) is optional:
T
1x4 =1 1 - o
2T (A: - A(3) -
-))
(14)
4

---

Regularized Langevin Dynamics for Combinatorial Optimization
Maximum Independent Set. The maximum independent set (MIS) problem aims to select the largest subset of nodes of the graph G, without any adjacent pair. Denote selected node as x, = 1 and an unselected one as X, = O, the energy function of MIS could be expressed as
(Sun et al., 2022). However, V often lacks a closed- form expression or is too costly compute directly, neces- sitating the gradient approximation. To evaluate RLD under these conditions, we employ neural network to approx- imate the sampling distribution qo [x((xx), thereby demon- strating its effectivenesss even when only an approximate gradient is available.
N Σ
H(x) -
X +
Σ X,X
Here we still utilize mean-field decomposition, letting go [x) = n 2o (xx[[xx) The RLD update in Equation 10 could be translated into the following training loss
1=1
(FJ)EE
(17)
= = x 3 x T Ax
2
As this is a quadratic function, it is straightforward to com- pute the gradient of the energy function as
(o:D(0;x,d,)))) (xx (=(()(
N
(24)
Σ c0(2; - -x11-
H((x) = - +1 AAx.
(18)
The first term minimizes the conditional expectation of the energy function after the one-step update. When the expectation is tractable, this term is equivalent to the unsupervised learning loss of Erdöes Goes Neural (EGN) (Karalias & Loukas, 2020); otherwise, we could optimize this loss by estimating the policy gradient, i.e., By (x)) (x(')) V log go (x') xx] via Monte Carlo methods. In this work, we focus on verifying the effectiveness of RLD and adopts the unsupervised training loss for simplicity. The second term regularizes the expected Hamming distance be- tween the two solutions, with À being the regularization coefficient. We name this NN-based solver as Regularized Langevin Neural Network (RLNN).
Maximum Clique. The maximum clique (MCI) stands for the largest subset of nodes in graph such that every two nodes in the set are adjacent each other. It could actually be expressed as the MIS problem in the complete graph, with the energy function:
H(x)
x +
Σ x, (L,))E
(19)
In order to represent the energy function with the adjacency matrix A, we can write the penalty as (EEM x,)²
ΣN" x² x2)12 Eiiyee x, reformulating the energy function and its gradient as
We train RLNN in a similar fashion to reinforcement learn- ing through sampling and update, but without the need to account the future states except the immediate next one. This allows RLNN cireumvent the high variance in esti- mating the future return when trained with long sampling process. In detail, each time we sequentially sample T" sam- ples with the current proposal distribution (x [x), then for each sample, we train RLNN to minimize the loss in Equa- tion 24. The training algorithm of RLNN is summarized in Algorithm 2.
8 (1 xx)² xx xT
H(x) - xx x
(20)
VI(() = -1 ((1 x)1 111 ----xxAAx Axx).
(21)
Maximum Cut. The maximum cut (MCut) problem looks to partition the nodes into two sets so that the number of edges between two sets is maximized. Here we x; and x; 0 to represent the belonging to two sets, and the energy function could be expressed as
Algorithm 2 Regularized Langevin Neural Network
- (2x; - 1)(;x; - 1)
1: Input: T', A
H(x) = - Σ
2
Initialize
(i,))EE
(22)
3: while the stopping criterion is not met do
= x Ax - 1 Ax,
4: Initialize x E N {x}
5: for 1 t= 1,... T' do
whose gradient could be accordingly computed as
6: x' ~ (x(xxx))
7: D + (x
( = A(2x - 1).
(23)
x x x'
9: end for
4.3. Regularized Langevin Neural Network
10: 0 4 ming EXED A,))
11: end while
The efficacy of gradient-guidet SA solvers. including RLSA, is critically dependent on the knowledge of V (x)
12: return 0
5

---

Regularized Langevin Dynamics for Combinatorial Optimization
Similarly, we maintain K" parallel sampling processes in our implementation to obtain more efficient training data collection. During the inference time, we simply sample from (x (x) sequentially for T steps with K processes run in parallel. Note that temperature annealing is not used here as we do not find it useful and we simply leave r = 1.
With the same example, we could also see why the stan- dard discrete Langevin sampler (Zhang al., 2022) with constant step size fails here. Since LD is first-order approx- imation of the docally-balancee proposal (Zanella, 2017). a small a is needed to make the approximation accurate. How- ever, a small a would also lead to a strong penalization on the magnitude of the update. At local optima, A < 0 would further discourage the change, as indicated in Equation 7. Therefore, additional efforts are needed to help LD escape the local optima beyond the force of random noise. This dis- tinction between combinatorial and continuous optimization highlights the significance of RLD.
4.4. Connection to Normalized Gradient Descent
Our proposed RLD method is closely related to the normal- ized gradient descent (NGD) method (Cortés, 2006) in the continuous domain:
V fx(x) VV f 1x)]l2
= OF
(25)
5. Experiments
NGD is developed to address the vanishing/exploding gradi- ent by normalizing the L2 norm of the gradient for scale- invariant update at each step. Our method, especially RLSA, could be treated as a discrete version of this approach by regularizing the Hamming distance between the solutions before and after the update. And both methods accelerate the descent under the smoothness condition.
5.1. Experimental Setup
Benchmark datasets. Following Zhang et al. (2023), we evaluate MIS and MCI using Revised Model B (RB) graphs (Xu & Li, 2000), and we evaluate MCut using Barabási- Albert (BA) graphs (Barabási & Albert, 1999). Following Qiu et al. (2022), we also include Erdós-Rényi (ER) graphs for MIS. As in prior work, each graph type is generated at two scales:
The key difference between the two lies in the case when (d)) < O, RLSA could not be translated into gradient descent algorithm to minimize the energy function, since a = إفي < 0 (ignore e) reverses the direction of gradient descent. Instead, RLSA should be treated now as a way to escape local optima without dramatically increasing the energy function. Utilizing Equation 5, we can fully express the proposal at this state as
RB and BA graphs: small (200-300 nodes) and large (800-1200 nodes).
ER graphs: small (700-800 nodes) and large (9000- 11000 nodes).
The large-scale ER graphs serve as transfer-testing set for models trained on small-scale ER. We append a suffix "-[ n-N J" to each graph name to indicate its size range.
exp(
(x))11
g(x'1x (x)
27
2A
(26)
((x)
For RB and BA (both scales) and ER-[700-800J, we use 1000 graphs for training, 100 for validation, and 500 (RB/BA) or 128 (ER-(700-800) for testing. ER-[9000- 11000] is reserved solely for testing (16 graphs).
It should be noted that the density of g(x'|x) increases with respect to the distance from x 2A.,y (x)x,, which is the gradient ascent direction (note that A(d) is negative here) of the energy function. This behavior is desirable due to the different property of the local optima in the discrete data, which may not vanish to zero but point to an infeasible region (i.c.. with A negative in all coordiantes).
Baselines. Following Qiu et al. (2022) and Zhang et al. (2023), categorize our baselines the classical oper- ations research solvers (OR), (human-designed) heuristic solvers (H), supervised learning-base based solvers (SL), rein- forcement learning- based solvers (RL), and unsupervised learning-base based solvers (UL). For MIS, we have the integer linear programming solver Gurobi (Gurobi Optimization, LLC, 2023) and MIS-specific solver KAMIS (Großmann et al., 2023) as the OR baselines, and the recent SA method iscO (Sun et al., 2023) heuristic baseline. In the SL category, we include INTEL (Li et al., 201 8b), DGL (Böther et al., 2022), and DIFUSCO (Sun & Yang. 2023). In the RL category, we have PPO (Ahn et al., 2020) and DIMES (Qiu et al., 2022). In the UL category, we use LTFT (Zhang et al., 2023) and DiffUCO (Sanokowski et al., 2024). For
Let us take MIS as an example, whose local optimum corresponds to a maximal independent set, that is, each unselected node has least one neighbor in the set. At the local optimum, the gradient at the selected node x; is (x(;;; = -1, which points to the direction of increasing x,, and is infeasible since x; < 1. Similarly, the gradient at an unselected node is bounded by (x); 2 -1+ B > O, which points to the direction of decreasing the value, and is also infeasible. Since the gradient descent direction is not informative, RLSA would try escape this local optima but avoid the steepest direction increase the energy function, i... the gradient ascent direction x (2(0) (x)...
For
6

---

Regularized Langevin Dynamics for Combinatorial Optimization
Table Comparative results on the Mximum independent Set (MIS) problem. On each dataset, we bold the best result and color the second-best one in green. By "best" or "second best", we exclude the OR solvers (Gurobi and KaMIS) as their runtime is excessively large, preventing a fair comparison with the methods other categories.
MIS
RB-[200-300]
RB-1800-1200]
FR-[700-800]
FR-[9000-11000]
METHOD
TYPE
SIZE t
TIME 4
SIZE t
TIME 4
SIZE f
TIME 4
SIZE t
TIME 4
Gurobi
OR
19.98
47.57m
40.90
2.17h
41.38
50.00m
KaMIS
OR
20.10
1.40h
43.15
2.05h
44.87
52.13m
381.31
7.60h
PPO
RL
19.01
1.28m
32.32
7.55m
INTEL
SL
18.47
13.07m
34.17
20.28m
34.86
6.06m
284.63
5.02m
DGL
SL.
17.36
12.78m
34.50
23.90m
37.26
22.7 Im
DIMES
RL
42.06
12.01m
332.80
12.72m
DIFUSCO
SL
18.52
16.05m
41.12
26.67m
LIFT
UL
19.18
32s
37.48
4.37m
DiffUCO
UL
19.24
54s
38.87
4.95m
iSCO
H 19.29
2.71m
36.96
11.26m
42.18
1.45m
365.37
1.10h
RLNN
UL 19.52
1.64m
38.46
6.24m
43.34
1.37m
363.34
11.76m
RLSA
H
19.97
35s
40.19
1.85m
44.10
20s
375.31
1.66m
Table 2. Comparative results on the Maximan Clique (MCI) and Maximum Cut (MCut) problems. On each dataset, we bold the best result and color the second-best one in green. By "best" or "second best", we exclude the OR solvers (Gurobi and SDP) as their runtime excessively large, preventing fair comparison with the methods in other categories.
MCI
RB-1200 (200-220000 3001
RB-1800 1200]
MCut
BA-[200 [A-[200-3000 300]
BA-[800 1200]
METHOD
TYPE
SIZE t TIME 4
SIZE
TIME
METHOD
TYPE
SIzE f
TIME 4
SIZE
TIME 4
Gurobi
OR
19.05
lm55s
33.89
19.67m
Gurobi
OR
730.87
8.50m
2944.38
1.28h
SDP
OR
SDP
OR
700.36
35.78m
2786.00
10.00h
Greedy
H
13.53
25s
26.71
25s
Greedy
H
688.31
13s
2786.00
3.12m
MFA
14.82
27s
27.94
2.32m
MFA
704.03
1.60m
2833.86
7.27m
EGN
UL
12.02
41s
25.43
2.27m
EGN
693.45
46s
2870.34
2.82m
LTFT
UL
16.24
42s
31.42
4.83m
LTFT
UL. 704.30
2.95m
28641661
21.33m
DifTUCO
UL
16.22
1.00m
DifFUCO
UL. 727.32
1.00m
2947.53
3.78m
iSCO
H
18.96
54s
40.35
11.37m
iSCO
H
728.24
1.67m
2919.97
4.18m
RLNN
UL
18.13
1.36m
35.23
7.83m
RLNN
UL. 729.00
1.58m
2907.18
3.67m
RLSA
18.97
23s
40.53
1.27m
RLSA
H
733.54
27s
2955.81
1.45m
the non-MIS problems, the baselines include two OR meth- ods, which are Gurobi and a semi-definite programming method (SDP) for MCut; three heuristic methods, which are greedy, mean-field annealing (MFA) (Bilbro al., 1988) and iSCO (Sun et al., 2023); and three UL methods, which are EGN (Karalias & Loukas, 2020), LTFT (Zhang et al., 2023) and DiffUCO (Sanokowski et al., 2024), respectively. For most of these methods, we report their published results (Qiu et al., 2022; Zhang et al., 2023; Sun & Yang, 2023; Sanokowski al., 2024; Li et al., 2024). If an NN solver only compare with the variant
Implementation Details. Our implementation is based on PyTorch Geometric (Fey & Lenssen, 2019) and Accelerate (Gugger et al., 2022). We use two servers for the RLNN training, one with 8 NVIDIA RTX A6000 GPUs and the other with 10 NVIDIA RTX 2080 Ti GPUs. We evaluate all methods on the first server, using a single A6000 GPU. We find the efficiency of RLNN highly susceptible to the inductive bias of the NN architecture, c.g., a two-parameter linear model enough to fit the gradient of MIS in Equation 19. Since the main focus of our evaluation to verify the effectiveness of RLD under the approximate gradient, we keep the model architecture of RLNN basically the same as the ones used in prior works (Qiu et al., 2022; Sanokowski et al., 2024). Future work may further optimize the neural architecture by injecting more prior knowledge about the problem structure, as in Yau et al. (2024). In our experiment, we parameterize RLNN with a five-layer GCN (Kipf & Welling, 2017) with 128 hidden dimensions. Due to the
has multiple variants, with the longest runtime (typically corresponding to the best result). We rerun the official code of iSCO' on our datasets due to the inconsistency of time measurement in this work, where the average runtime of iSCO is compared to the total runtime of its baselines. For a fair comparison, we run iSCO with the same number of steps and trials as we do for RLSA.
penttps//githhn www.hhwww..cceeeeemmmeeeeeeeeeee wtt.coom/oooocoo wwt..//ogge--reeeacc///deeeeeee
7

---

Regularized Langevin Dynamics for Combinatorial Optimization
MIS RB-[200-300]
MIS RB-1800-1200]
MIS ER-[700-800]
MIS ER-[9000-11000
1.0
1.0
1.0
1.0
Primal Gap
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
100
200
300
200
400
200
400
2000
4000
MCI RB- 300D
MCI RB- RB-[800-1200)
MCut BA-[200-300]
MCut BA-[800-12000
1.0
1.0
0.3
0.3
Primal Gap
0.8
0.8
0.6
0.6
0.2
0.2
0.4
(a=0.3)
0.4
0.1
0.1
0.2
LD (a=0.01)
0.2
LD (a-0.001)
0.0
0.0
0.0
0.0
50
400
200
Step
Step
Step
Step
Figure 1. Primal-gap trajectories for SA solvers using RLD versus the standard discrete LD method (Zhang al., 2022). The RLD (corresponding to RLSA) curve is shown in red, and the remaining curves (in distinct colors) correspond to discrete LD with various step-size settings. Solid lines denote the mean primal gap over the test set, and shaded regions represent the standard deviation.
increasing computational complexity at each step, we also accordingly reduce the number of sampling steps and trials of RLNN compared to RLSA, with other hyperparameters kept the same. We include more details in Appendix A.
to the SOTA NN baselines, RLNN shows a performance comparable to DiffUCO on the RB graphs and clearly out- performs DIMES on ER. Moreover, it should be pointed out that DiffUCO can require up to two days of training even on small graphs, e.g., RB-[200-300) whereas RLNN com- pletes the training in under three hours regardless the graph scales, while delivering comparable performance. This high- lights RLNN's 's superior training efficiency against previous diffusion models, thanks its local training objective.
5.2. Main Results
In performance evaluation, we compare the mean value of the achieved moolem--peciffe objective (larger is better) of each method on each problem, including the set size for MIS, clique size for MCI and cut size for MCut. In addi- tion, we compare the total runtime (lower is better) of each method throughout the test set by sequentially evaluating each instance. Since OR solvers are guaranteed to find the optimal solution with enough runtime, we do not include them for comparison.
Table 2 summarizes our comparative results on MCI and MCut. RISA retains clear efficiency advantage over iSCO. Although iSCO matches RLSA's performance on MCI at both scales, RLSA and RLNN still outperform all other base- lines. On MCut, RLSA consistently leads; while RLNN, DiffUCO, and iSCO achieve comparable results-al all signif- icantly better than the remaining methods.
Table reports our results on the MIS problem. RLSA achieves significant improvements over SOTA NN-based methods on both RB and ER graphs, with similar or even shorter runtime. Moreover, RLSA consistently outperforms iSCO, another gradient-guided SA method, with the same number of sampling steps and independent trials. Due to its parallel sampling design, RLSA requires only 5-20% of iSCO's 's runtime while delivering better objective values.
We also include extended comparisons between iSCO and RLSA with ten times more sampling steps in Appendix B, which confirms the above findings. Overall, both RLSA and RLNN remain highly competitive across our benchmarks, with RISA delivering impressive results on every dataset at minimal computational cost.
5.3. Ablation Study
Based on less prior knowledge (using an approximate gra- dient), RINN shows a lower performance than RISAA, but still claims the second-best result in two of the four datasets. On [RR[900--1000 graphs, RLNN matches iSCO's per- formance but uses under 20% of the runtime. Compared
To verify the effectiveness the proposed regularization in RLD, we conduct the ablation study on RLSA and RLNN, respectively. We first compare RLD with the standard dis- crete LD (Zhang al., 2022) for SA, searching the step
8

---

Regularized Langevin Dynamics for Combinatorial Optimization
Table Ablation study the effectiveness of regularization in RLNN. The numhers correspond the set size (larger is better).
MIS
MCI
MCut
METHOD
RB-[200-300]
ER-[700-800]
RB-[200-300]
[A-[[200-30]]
RLNN w/o regularization
18.64 64
37.73
16.62 18.13
730.20
RLNN w/ regularization
19.52
43.34
729.00
MIS RB-[200-300]
MCI RB-1200-300]
remains flat on MIS or even deteriorates after more training epochs on MCI. This highlights that only using the unsuper- vised loss of EGN makes sample diversity a critical concern. By contrast, the regularization term encourages RLNN to gather more diverse training samples and explore more effec- tively during inference, resulting in the stable performance gains shown by the blue curve throughout training.
21
W/ Reg.
w/o Reg.
Size
19
16-
18
14
17
10
20
40
20
30
Training Epochs
Training Epochs
In fact, the idea of RLNN also parallels well-known re- inforcement learning techniques to encourage exploration, such as curiosity-driven exploration (Pathak et al., 2017) and soft policies (Haarnoja et al., 2017; 2018).
Figure 2. Training curves of RLNN with or without regularization. Validation performance (set/clique size) is shown.
size over the set (0.1, 0.01, 0.001.. All other hyperpa- rameters are kept the same as in RLSA Figure 1 compares the dynamics of the primal gap (Berthold, 2014) across the sampling process. Here, the primal gap on each instance is defined as
6. Conclusion & Limitation
In this work, we point out the specific challenge from the lo- cal optima in combinatorial optimization (CO), and propose a novel sampling framework called Regularized Langevin Dynamics (RLD) to tackle the issue CO. On top of that, we develop two CO solvers, one based on simulated anneal- ing (SA), and the other one based on neural networks. Our empirical evaluation three classic CO problems demon- strate that our proposed methods can achieve state-of-the-art (SOTA) or near-SOTA performance with high efficiency. In particular, our proposed SA method consistently outper- forms the previous SA baseline using only 20% running time, while RLNN significantly improves the training effi- ciency of previous diffusion models. In summary, RLD is a simple yet effective framework that shows great potential in addressing CO problems.
[H(X) H(X' max (IX
if H() 2 O; otherwise,
(27)
where x corresponds to the best solution found so far and x" is a pre-computed optimal (or best known) solution.
is evident that the standard discrete LD always ends up at sub-optimal solution except on MCI. The searching could easily get stuck in local optimum, indicated by the flat stage. In contrast, RLSA typically converges in fewer than 100 steps without becoming trapped. Note that our search set already includes the most common gradient-descent step sizes used for continuous problems, and even a smaller step size (e.g., 0.001) yields worse results. Unlike continuous optimization, combinatorial optimization presents unique challenges; RLD is specifically designed to address these.
In this work, we only consider binary data for ease of anal- ysis. Although the whole framework could be generalized, its effectiveness remains unclear in other CO problems with categorical, integer, or mixed integer variables. Future work may also extend it to other CO problems with global con- straints, such as the Traveling Salesman Problem. Besides, we have only given an intuitive explanation of RLD in this work, but the theoretical understanding of RLD is generally missing. We also expect to address this part in the future.
We next perform ablation study on the regularization term in Equation 24 for RLNN training. Specifically, we train RLNN on small-scale graphs both with and without regularization, and report results in Table 3. Adding regular- ization significantly improves RLNN's performance in most cases, with the exception of MCut-likeli because MCut is unconstrained and is less prone to local optima. On all other benchmarks, training RLNN without regularization proves almost ineffective. Figure visualizes this effect by plotting the set/clique size on the validation set (larger is better) for MIS and MCL.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
From Figure 2, the curve without regularization (orange)

---

Regularized Langevin Dynamics for Combinatorial Optimization
References
Chopra, S. and Meindl, P. Strategy, planning, and operation. Supply Chain Management, 15(5):71-855 2001.
Ahn, S., Seo, Y., and Shin, J. Learning what to defer for maximum independent sets. In Proceedings the the 37th In- ternational Conference on Machine Learning, (CML'20. oog. 2020.
Cortés, J. Finite-time convergent gradient flows with ap- plications to network consensus. Automatica, 42: 19:3993- 2000, 11 2006. doi: 10. 2ttllf.auttmmaiic.2206.....0000
Barabási, A.-L. and Albert, R. Emergence of scal- ing in random networks.
Science, 286(5439): 509-512, 1999. doi: 10.1 11126ccieecc.286.5553
Erstt A. T., Jiang, H., Krishnamoorthy, M., and Sier, D. Staff scheduling and rostering: A review applications, methods and models. European Suropean.jouraal of operational research, 153(1):3 2004.
509. URL https:/ /wwp://wwww.ooo http::wwwww...eecetotowowwwwwe.w org/doi/ abs/10.
286 5439.509.
Bengio, Y., Lodi. A., and Prouvost, A. Machine learning for combinatorial optimization: methodological tour d'horizon, 2020.
Feng, S. and Yang, Y. Sorrel: subopiimalldemoosttttion guided reinforcement learning for learning to branch. In The 39th Annual AAAI Conference on Artificial Intelli- gence, 2025.
Berthold, T. Heuristic algorithms in global minlp solvers. 2014. URL https: http://aa....aaa.aa....//aa.aa.a was.mmnnnicccoa............aa.aa
Feng, S., Kim, J., Yang. Y., Boudreau, J., Chowdhury, T., Hoisie, A., Khan, R., Kilic, O. O., Klasky, S., Ko- rchuganova, T., Nilsson, P., Outschoom, I. M., Park, K., Podhorszki, N., Ren, Y., Suter, F., Vatsavai, S. S., Yang, W., Yoo, S., Maeno, T., and Klimentov, Alter- native mixed integer linear programming optimization for joint job scheduling and data allocation in grid com- puting, 2025a. URL https: http:///rxvvvv.ooo abs/ 2502 2502.00261. 00261.
Bhattacharya, A., Ghatak, S., Ghosh, S.. Das, R. K., and Bengal, W. Simulated annealing approach onto vlsi circuit partitioning. 2014. URL atttps://api. semant www.hlar....ooooooooooocoooo aapllla.org..
wwtp:l...rrrooooooooe/eeea www.chaa......ooororr.p..e. 331 97762.
Bilbro, G., Mann, R., Miller, T., Snyder, W., van den Bout, D., and White, M. Optimization by mean field annealing. In Touretzky, D. (ed.), Advances in Neural Information Processing Systems, volume 1. Morgan-Kaufmang Kaufmann, 1988. URL https: /tttss:/pprcceediin neurriiiinnnnnnns....e.... cc cccppppe__fllespppprr////////1
Feng, S., Sun, W., Li, S., Talwalkar, A., and Yang, Y. A comprehensive evaluation of contemporary ml-based solvers for combinatorial optimization, 2025b. URL
acfaccaaeccdcc8809222227737 paper. pdf.
Fey, M. and Lenssen, J. E. Fast graph representation learning with PyTorch Geometrie. In ICLR Workshop Repre- sentation Learning on Graphs and Manifolds, 2019.
Böther, M., KiBig, O., Taraz, M., Cohen, S., Seidel, K., and Friedrich, T. What's wrong with deep learning in tree search for combinatorial optimization. In In- ternational Conference on Learning Representations, forum?
Gasse, M., Chételat, D., Ferroni, N., Charlin, L.,, and Lodi, A. Exact combinatorial optimization with graph convolu- tional neural networks. In Advances in Neural Informa- tion Processing Systems 32, 2019.
2022. URL id md=dk0Hzd
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman- S., and Zhang, Q. JAX: composable transformations Python+NumPy programs, 2018. URL http:// htt.bb/ttthhuttec// com/ gwwgl///oeeeeooooooooooo jax.
Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D. K., and Maddison, C. J. Oops took a gradient: Scalable sam- pling for discrete distributions. ArXiv, abs/2102.04509, 2021. URL https: : //api. semanticschoaar. org Corpporrrussaacc :2:
Cappart, Q., Chételat, D., Khalil, F. B., Lodi, A., Morris, C.,, and Veličković, P. Combinatorial optimization and rea- soning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 2023. 2023.
Großmann, E.,, Lamm, S., Schulz, C., and Strash, D. Find- ing near-optimal weight independent sets at scale. In Proceedings of the Genetic and Evolutionary Compu- lation Conference, GECCO '23, pp. 293-302, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701191. 3583131.3590352 URL https: http:///ooi.or/100// 3t0.//553311115005.3
Chen, Y. L. and Ke, Y.I.. Multi-objective var planning for large-scale power systems using projection-basee two-layer simulated annealing algorithms. 2004. URL https::/api.. /ttppppp///pppeeeeetaiiiioooooo wtw.aapssssmmatsschsssaaaaa /rrg CorpuSIDD:116697225
doi: 10.1145/
10

---

Regularized Langevin Dynamics for Combinatorial Optimization
Gugger, S., Debut, L.,, Wolf, T., Schmid, P., Mueller, Z., Mangrulkar, S., Sun, M., and Bossan, B. Ac- celerate: Training and inference at scale made sim- ple, efficient and adaptable. huggi weggiinnfaccc wawfae///eeeee acce acceelecaaae erate, 2022.
Khalil, E., Dai, H., Zhang. Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Guyon, I., Luxburg, U. V., Bengio, S.. Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https::/ www.rroooeeddddn....e........... ec /iaapprr_iee//pppee//////////
httss///ggttutcccco com/
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https: /www. gurobi. com.
Gusfield, D. Algorithms on stings, trees, and sequences: Computer science and computational biology. Acm Sigact News, 28(4):41-66 1997.
pdf.
Kipf, T. N. and Welling, M. Semi-supervised classi- fication with graph convolutional networks. In In- ternational Conference Learning Representations, 2017. URL i id=SJU4ayYgl.
Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. Reinforce- ment learning with deep energy-based based policies. 2017.
net hereerrrriee.ne//orum
Haarnoja. T., Zhou, A., Abbeel, P., and Levine, S. Soft actor- critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Confer- ence on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1861-1870. PMLR, 10-15 Jul 2018. Utthttps: http:///occeedddeee ngs mlrr press/ /v0es//v0// haaraaaaaaaaaaa Bb html.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. Op- timization by simulated annealing. Science, 220 (4598):671 1-680, 1983. doi: 2..112//cieecc.2224455
671. URL abs / 10/ wwee111//ccicnee 220 4598 671.
www.::scieneeee...e......eee.eee org/doi/
Kool, W., van Hoof, H., and Welling, M. Attention, learn solve routing problems! In International Conference on Learning Representations, 2019. URL https:// openreview net forum? BeeeiiddBByyxBBBeee sRaYm.
Hastings. W. K. Monte carlo sampling meth- ods using markov chains and their applications. Biometrika, 57:97-109, 1970. URL https: /api. semanticscholas: wwwp:ecch..a.......oooooooooooet /htp///orpusii :2110144:::2204445 21204149.
Lecun, Y., Chopra, S., and Hadsell, R. A tutorial on energy- based learning. 01 2006.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion probabilistic models. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 6840-6851. Curran Associates, Inc., 2020. URL https://proceeddngg new..eeredddinnn..ni............ oc /c//ppeerfflle/ppppp///0////// RcbbcfeceBBaa0000eTraaa11110111. pdf.
Li, Y., Guo, J., Wang, R., and Yan, J. From distribution learn- ing in training to gradient search in testing for combinato- rial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: / /oppnreview..o net
Li, Y., Guo, J., Wang, R., Zha, H., and Yan, J. Fast 12t: Optimization consistency speeds up diffusion-based training-to-testinng solving for combinatorial optimiza- tion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: / openreview net/ forum? dimmmddzdddDxxecccccmmm
IBA, Y. Extended ensemble monte carlo. Interna- tional Journal of Modern Physics C, 12(05))6636656
June 2001. ISSN 1793-6586.
doi: 10.1 $0129183101001112. URL http://dt>/ doi.org/ 10. 00.1122/80121111000011
Li, Z., Chen, Q., and Koltun, V. Combinatorial opti- mization with graph convolutional networks and guided tree search. In Neural Information Processing Systems, 2018a. URL https: // //api. semant cscholar. org/ /ts//CoouSID::3027777
Johnson, D. S., Aragon, C. R., McGeoch, L. A., and Schevon, C. Optimization by simulated annealing: An experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, 39(3):378- 406, 1991. ISSN 0030364X, 15265463. URL http: h/wwww
Li, Z., Chen, Q. and Koltun, V. Combinatorial op- timization with graph convolutional networks and guided tree search. In Bengio, S., Wallach, H. Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018b. URL https: / /pwpceedddiicce/ooooooooooooco.c ngs. neurips.
Karalias, N. and Loukas, A. Erdos goes neural: an unsupervised learning framework for combinato- rial optimization on graphs. ArXiv, abs/2006. 2020. URL https:/ http:/pp..smaanicccccceeeooooeoe orr/CoorpuSDD:21979225

---

Regularized Langevin Dynamics for Combinatorial Optimization
cc//apper_flleesppperr/////////1 @dbbbea722bbeccc5555552222223333 pdf.
Seçkiner, S. U. and Kurt, M. A simulated an- nealing approach to the solution of job rotation scheduling problems. Applied Mathematics and Computation, 188(1):31-45, 2007. ISSN 0096- 3003. doi: http://daiiogg//11lldjjjaaee222e
Lobo, M. S., Fazel, M., and Boyd, Portfolio optimiza- tion with linear and fixed transaction costs. Annals of Operations Research, 152:341-3655 2007.
082. URL httpps//ww..ccieneeiieeetttt com/ wwteen///rrrcccee///////00000000
Lucas, A. Ising formulations of many np problems.
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Ma- chine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2256-2265, Lille, France, 07- 09 Jul 2015. PMLR. URL http:::ttt:pppt httpttps///oooeeengggs.... mir, prwss/v377 sowl--iccsteeilss. html.
Frontiers Physics, 2, 2014. ISSN 2296-424X.
doi: 10.3389ffphyy2011400005. www. wwwroniiersii.org/oooooo httpprnnnsappsssss//ssss Striccees/1..3:00
URL https://
2014..0005
Metropolis, N. C., Rosenbluth, W., Rosenbluth, M. N., and Teller, A. H. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087-1092, 1953. URL https: //apii./ppppppp/////// semant cwcholar......oo......cc..caaaae org/ www.olarror//ooouuSSSSS/ 65777
Song, J., Meng. C., and Ermon, S. Denoising diffusion implicit models. In International Conference Learning Representations, 2020.
Neal, M. Sampling from multimodal distribu- tions using tempered transitions. Statistics and Com- puting, 6:353-366, 1996. URL https://api. semant cscchllcrrr.... aachollr.oo. wttp:/oorrr/oooosi1111111111111
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. In Advances Neural Information Processing Systems, pp. 11895-11900 2019.
Papadimitriou, C. and Steiglitz, Combinatorial Opti- mization: Algorithms and Complexity, volume 32. 01 1982. ISBN 0-13-152462-3. doi: N0.1109/TASSPP.1984 1164450.
Sun, H., Dai, H., Xia, W., and Ramamurthy, A. Path auxiliary proposal for MCMC in discrete space. In International Conference on Learning Representations, 2022. URL https: /pw./eveeeweeeeeeeee/eeeeeroeeee net net/ forum?
Papadimitriou, C. H. and Steiglitz, K. Combinatorial opti- mization: algorithms and complexity. Courier Corpora- tion, 1998.
Sun, H., Goshvadi, K., Nova, A., Schuurmans, D., and Dai, H. Revisiting sampling for combinatorial opti- mization. In Krause, A., Brunskill, E., Cho, K., En- gelhardt, B., Sabato, S., and Scarlett, J. (eds.), Pro- ceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 92859-32877 PMLR, 23-29 Jul httpthssss//pcceeeiiiiieee v202 sun23c. html.
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, F.,, DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. Automatic differentiation in pytorch. 2017.
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driven exploration by self-supervised predic- tion. In International Conference on Machine Learning (ICML), 2017.
2023, URL https: httpsuuttttttssppppooeeeeee http///ppoceeen..eeeee/e mlr press/
Sun, Z. and Yang. Y. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Thirty-seventt Conference Neural Information Processing Systems, 2023. URL https: opwnrevieweeeeeeeeeeeeeeeeroeeee net forum? id=Jv8Ffo1gW..
Qiu, R., Sun, Z., and Yang. Y. DIMES: A differentiable meta solver for combinatorial optimization problems. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, htttps://operrewee http///pppeeeeeeeeeeeeeeeee net/forunt
2022. URL httpt:t/t///t.ttc.tt id= id=9u05zr0mhx.
Tavakkoli-Mohhadaam, R., Safaei, N., Kah, M., and Rabbani, M. A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing. Journal of the Franklin Institule, doi: 344(5):406-455, 2007. ISSN 0016-0032. URL cclenne/arrt.cee//////o0002333 science/arie Modeling, Simulation and Applied Optimization Part II.
Rubinstein, M. Markowitz's" portfolio selection": A fifty- year retrospective. The Journal of finance, 57(3):1011- 1045, 2002.
Sanokowski, S., Hochreiter, S., and Lehner, S. A diffu- sion model framework for unsupervised neural combi- natorial optimization. In JCML, 2024. URL https: //openreview. wtt.iiieeweee/.ommmeeee dd=A
12

---

Regularized Langevin Dynamics for Combinatorial Optimization
WANG, C., HYMAN, D., PERCUS, A., and CAFLISCH, R. Parallel tempering for the travel- ing salesman problem. International Journal of Mod- em Physics C. 20(04):539-555 -56,,,,555,,6- 2009. doi: 10.1142)
Zheng, L., Li, Z.,, Zhang, H., Zhuang, Y., Chen, Z., Huang. Y., Wang, Y., Xu, Y., Zhuo, D., Xing, E. P., et al. Alpa: Automating inter-and {Intra-Operator) parallelism for distributed deep learning. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI
S0129183109011889, URL htt.tttt.///...... //de://dooooo ///o/ioor///....// 1142//0022113100013333
22), pp. 559-578, 2022.
Wang, H. P. and Li, P. Unsupervised learning for combina- torial optimization needs meta learning. In The Eleventh International Conference on Learning Representations, 2023. URL https::t/////....t. http:///peeeeeeeeeeeeeeeeeeeeeee forum? id= ENYHCE823p.
Wang, H. P., Wu, N., Yang, H., Hao, C., and Li, P. Un- supervised learning for combinatorial optimization with principled objective relaxation. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: //openreview net forum? J
Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML' 11, pp. 681-688, Madison, WI, USA, 2011. Omnipress. ISBN 9781 450306195.
Xu, K. and Li, W. Exact phase transitions in random constraint satisfaction problems. ArXiv, cs.A000040 2000. URL https: http://:///ppp..aaa.sseeeeee semanticscholar. org/CorrpusD::207744
Yau, M., Karalias, N., Lu, E., Xu, J., and Jegelka, S. Are graph neural networks optimal approximation algorithms? Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 73124-73181. Curran Associates, Inc.,
2024. URL https: http::///pppoeeenggg...oeo.. neurips. ca/
95sb22cco0kcee000ffhddeee....... pdf.
Paper-Conferenee
Zanella, G. Informed proposals for local meme in dis- crete spaces. Journal of the American Statistical Asso- ciation, 115:852 865, 2017. URL https://api. semant wrsranntcccchoar.... wowppoorr/I :85.1147588
Zhang, D., Dai, H., Malkin, N., Courville, A., Bengio, Y., and Pan, L. Let the flows tell: Solving graph combi- natorial problems with GFlownets. In seveth- Conference on Neural Information Processing Systems, 2023. URL https: www.revee.eeeeeeeeeeeeeee. httptt/////ppeereiieen id= JH=
net forum?
Zhang, R., Liu, X., and Liu, Q. A langevin-like sampler for discrete distributions. International Conference on Machine Learning, 2022.
13

---

Regularized Langevin Dynamics for Combinatorial Optimization
A. Additional Experiment Details
A.I. Overview of Hyperparameters
Tables and summarize the hyperparameters for RLSA and RLNN, respectively. We use random search to determine the initial temperature To within [0.001, 10] and the regularized step size d within [2, 100). Since larger values of K and T generally yield better performance, chose K and T for RLSA that its runtime matches that of the fastest baseline each dataset. For RLNN, allow larger time budget by selecting K and 7 such that its runtime is comparable most baselines. The inference is performed using the float16 data type to accelerate tensor operations.
Table 4. Hyperparameters used by RLSA on all datasets.
Problem
Dataset
T0
K
T
RB-[200-300]
0.01
5
200
300
1.02
RB-[800-1200]
0.01
5
200
500
1.02
MIS
ER-[700-800]
0.01
20
200
500
1.001
ER-[9000-1100]
0.01
20
200
5000
1.001
RB-[200-300]
4
2
200
100
1.02
MCI
RB-[800-1200]
4
2
200
500
1.02
BA-[200-300]
5
20
200
200
1.02
MCut
BA-[800-1200]
5
20
200
500
1.02
Table 5. Hyperparameters used by RLNN all datasets.
Problem
Dataset
K
T
K'
T
À
RB-[200-300]
1
5
20
100
1.02
10
50
0.5
RB-[800-1200)
1
5
20
200
1.02
10
300
0.5
MIS
ER-[700-800]
20
20
200
1.001
10
500
0.5
ER-[9000) [R-[9900-1100]
20
20
800
1.001
RB-[200-300]
1
2
20
100
1.02
10
100
0.5
MCI
RB-1800-1200]
1
2
20
200
1.02
10
300
0.5
BA-[200-300]
20
20
100
1.02
50
0.5
MCut
BA-[800-1200]
20
20
200
1.02
10
300
0.5
A.2. Implementation of RLNN
RLNN is parameterized by five-layer GCN (Kipf & Welling, 2017) with 128 hidden dimensions. A linear layer first used to project the input x to a 128-dim embedding H Each layer GCN performs the following update:
H H+ ReLLUUUHH' + V'D 1/2 AD 1/2H') H''
(28)
where U and v are the model parameters (-th layer, À A INx the adjacency matrix with the self loop, D is diagonal degree matrix with D. Σド A.j. The output hidden representation is projected to a scalar via a linear layer, and then a sigmoid activation yields the flipping probability qo (x:
xx for each node.
We train RLNN with 50 epochs all datasets, except RB-[700 [700-800] for MCI, where does not converge in 50 epochs. On each graph, we sample K' trajectories of length 7', yielding K'T" training samples. The batch size is set to 32 per GPU, and we optimize with Adam at learning rate of 0.0001.
80 epochs because the model
In terms of training time, our model completes training on small-scale graphs (except ER-[700-800 800)) in under half an hour using eight RTX A6000 GPUs, and the larger instances finish within one hour; on a server with ten RTX 2080 Ti GPUs, runtimes are slightly longer, but the longest experiment still finishes within three hours. By comparison, baseline methods
14

---

Regularized Langevin Dynamics for Combinatorial Optimization
such DiffUCO (Sanokowski et al., 2024) require days train single model on RB-1200-300). We attribute this efficiency advantage the local training objective of RINN, which avoids estimating long-term high-variance reward signals with standard reinforcement learning methods, employed by DiffUCO.
Note that the 32oat32 data type is used during RLNN training, which is switched to floatóó at the inference time.
A.3. Postprocessing
We postprocess the lowest-energy solutions to enforce feasibility, though in practice our methods almost always produce valid solutions, so we use simple greedy decoder.
Specifically, we calculate the gradient of the current solution x: max A O, then the solution has already reached a local optimum and the feasibility is guaranteed; otherwise, we flip the coordinate corresponding to arg max A. This process iterated until the convergence.
B. Comparison under Longer Runtime
To assess whether RLSA retains its advantage when given longer runtime, we run both RLSA and iSCO for ten times more iterations than those specified in Table 4. The results Tables and show that, although iSCO matches RLSA on some small-scale instances, RLSA still outperforms on large-scale datasets while requiring substantially less computation time.
Furthermore, the results demonstrate that RLSA achieves performance comparable exact solvers across multiple benchmarks senchmarks-especially large-scale problem instances underscorng its effectiveness in CO.
Table 6. Comparative results between iSCO and RLSA with times steps MIS. The best one is bolded.
MIS
RB-[200-300]
RB-[800-1200]
ER-[700-S0)
ER-19000-11000)
METHOD
TYPE
SIZE
TIME
SIZE f
TIME 4
SIZE
TIME
SIZE 1
TIME
iSCO (10x)
I
20.01
26.25m
40.47
1.87h
44.41
7.2lm
378.56 379.19
11.03h
RLSA (10x)
20.10
6.98m
41.83
10.65m
45.05
2.92m
17.63m
Table Comparative results between iSCO and RLSA with ten times more steps on MCI and MCut. The one bolded.
MCI
RB-[200
(0000300]
RB-[800 1200]
MCut
BA-[200 300]
BA-[800 1200]
METHOD
TYPE
SIZE
TIME 4
SIZE f
TIME
METHOD
TYPE
SIZE f
TIME L
SIZE t
TIME
iSCO (10x)
H
18.97
8.81m
40.41
1.83h
iSCO (10x)
734.62
1.20h
2960.23 2968.59
43.98m
RLSA (10x)
II
18.97
3.14m
40.63
8.67m
RLSA (10x)
I
734.62
4.07m
10.25m
C. Example Code for RLSA
The following Python code outlines our implementation of RLSA. The energy function corresponds to the formulas in Section 4.2 and the input parameters summarized in Section A. In experiments, the time measurement corresponds to the runtime of the entire RLSA function below.
def energy_fune (A, b, x, penaity.ccett=1.02)
The energy function is: b'T0ppnaltyyooefffxxx. Return the energy and the gradient
A0x
energy torch, sum (x* (penaltyy_cofffs-tt)) dim=0) grad = 2-penalty_cooff-t44
9
return energy, grad
13
def RLSA (graph, tav0, step_size, num_runs, num_steps, penalty_coeff)
15

---

Regularized Langevin Dynamics for Combinatorial Optimization
15
graph: the graph object in torch_geometric
16
num_runs: the number of parallel SA processes
num stepst the number of SA steps
tau0: the initial temperature u**
19
20
21
initialization nodes graph.num
23
24
torch torch-spartte sparse_coo_teete
25
traph.edge_inder
wraph.edge_wigg
torch.Size (num (num_nodes, nodes]
28
29
x = ftrrhh.randin 20,2, ncdes, num [uns]
energy, grad energy_func (A, graph.b, penalty_coeff) best_energy energy
best_sol x. ()
34
SA
for epoch in range (num_steps))
37
annealing
38
tau tau0 (1 (1-epoch/num_stepss
sampling
delta grad+ (2+x-1) /2 term2 -torch, kthvall
42
43
delta,
step step_size,
dim=0,
46
keepdin=True
47
) vaaluss
48
flip_preb torch. sirch.sigmoid (delta-term)) (dee /tau)
torch. rand_ like data)
51
x torch. where (rrstlip 1-x, x)
52
update loss energy, grad energy_func (A, graph.b, penalty_coeff) to_update energy<best_energy
36
best_scl [ to_update] x x[;, to_update)
57
best_energy [to_update] energy (to [to_ [to_update]
best_energy, best_sol
16


Reviews:
[{"review_id": "ddl9mAfzrg", "reviewer": "Reviewer_ZFeK", "summary": "This paper proposes improvements to existing diffusion-based amortized neural samplers and discrete Langevin dynamics samplers for combinatorial optimization, introducing simple regularization techniques aimed at mitigating issues with local minima in discrete spaces. The key claim is that avoiding local minima in discrete optimization is inherently more challenging than in continuous optimization, necessitating additional regularization methods. While the idea is intuitive and the proposed methods (Regularized Langevin Simulated Annealing and Regularized Langevin Neural Network) are straightforward and well-presented, the novelty appears somewhat incremental—essentially amounting to relatively simple adjustments to existing techniques. Empirical evaluations on standard combinatorial optimization benchmarks do demonstrate improved performance and computational efficiency; however, the overall methodological innovation is limited, as it mainly builds upon existing discrete Langevin dynamics frameworks with slight modifications.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thoughtful comments and constructive suggestions.\n\n> the novelty appears somewhat incremental—essentially amounting to relatively simple adjustments to existing techniques\n\n\n\nWe see your point but would like to highlight that our approach addresses a fundamental limitation of the previous method (discrete Langevin-like sampling in Zhang et al., 2022, and iSCO in Sun et al. 2023) in solving CO problems, with SOTA performance on benchmarks and significantly reduced computational costs.  Which should be informative for the research community, we hope.\n\n\n> However, the theoretical justification for why their specific form of regularization effectively escapes local minima remains somewhat intuitive rather than rigorously proven.\n\nThank you for your insightful question. Given the short time period, here we simply outline some perspective for the theoretical analysis.\n\n\nWhen not at the local optimum, RLD could accelerate the convergence. The main assumption here is that the graph is sparse, so it is unlikely for d variables to be adjacent to each other and the gradient remains accurate after the change.\n\nIn terms of the ability to escape optimum, we would like to point out the connection between RLD and path-auxiliary proposal [1], whose first-order version, PAFS, is also the fundamental algorithm behind iSCO. RLD could be treated as a generalized version of PAFS in terms of updating in expectation $d$ coordinates at each step, so it also satisfies Theorem 3 in that paper. Based on this generalization form, we propose a more efficient (parallel) sampling strategy to avoid the sequential sampling in PAFS, thus accelerating the search and significantly outperforming iSCO. \n\n\n\n[1] Sun, et al. Path Auxiliary Proposal for MCMC in Discrete Space. ICLR 2022.\n\n> Have you evaluated its performance on larger-scale problems (e.g., tens of thousands of nodes)?\n\nPlease notice our results on ER-[9000-11000] in Table 1: RLSA outperforms iSCO using only 2.5% running time. Also, RLNN takes a similar amount of time as DIMES but delivers significantly better results. All these results provide strong evidence for the advantage of our approach on larger-scale problems.  \n\n\n> However, previous diffusion-based sampling methods have also demonstrated applicability to problems with global constraints, such as vehicle routing or scheduling tasks.\n> Considering that your evaluations mainly focus on combinatorial problems with relatively simple (local) constraints, have you investigated how well your method performs on problems with stronger global constraints, such as the Traveling Salesman Problem (TSP)?\n\nThis is an insightful question but we would like to clarify that tackling global constraints typically need strong inductive biases and this is a common challenge for all energy-based models (EBMs). Here we refer to some recent EBM-based CO solvers that also face this dilemma and exclude the evaluation on TSP. \n\n[1] Haoran Sun et al., ‘Revisiting Sampling for Combinatorial Optimization’, ICML 2023.\n\n[2] Dinghuai Zhang et al., \"Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets\", NeurIPS 2023 spotlight.\n\n[3] Sebastian Sanokowski et al., A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.\n\nThe reason behind is because global constraints are highly structured, while EBMs are general solvers, whose formulation itself prevents a better performance than heuristics with a strong inductive bias such as k-OPT. \n\nBesides, we would like to mention that diffusion models themselves cannot handle global constraints, whose success heavily relies on (i) the supervision, which smooths the landscape (ii) decoding heuristics (2-OPT, MCTS or permutation), which is the key to handle the global constraint.", "claims_and_evidence": "The main claim of the paper—that avoiding local minima in discrete optimization is inherently more challenging compared to continuous optimization and thus necessitates more sophisticated regularization techniques—is reasonable and well-motivated. The authors provide clear empirical evidence demonstrating that their proposed regularization approach significantly improves performance compared to standard discrete Langevin dynamics. Specifically, their experiments convincingly show faster convergence and better-quality solutions on multiple combinatorial optimization benchmarks. However, the theoretical justification for why their specific form of regularization effectively escapes local minima remains somewhat intuitive rather than rigorously proven. Although the experimental results support their main claims, further theoretical analysis would strengthen their argument regarding the superiority of the proposed regularization method over existing approaches.", "methods_and_evaluation_criteria": "The authors' choice of benchmarks is reasonable and aligns well with common evaluation practices in combinatorial optimization. They use standard problems (e.g., maximum independent set, max clique, and max cut), which primarily involve local constraints. However, previous diffusion-based sampling methods have also demonstrated applicability to problems with global constraints, such as vehicle routing or scheduling tasks. Given that these tasks require satisfying complex global constraints—significantly more challenging than local constraints like those present in the current benchmarks—it remains an open question whether the proposed regularization method would generalize well to such problems. Specifically, it would be insightful to see whether the method can effectively handle combinatorial optimization tasks involving intricate global constraint matching, which is known to pose substantial difficulties for sampling-based methods. Exploring applications such as vehicle routing or scheduling would further clarify the strengths and limitations of the proposed framework.", "theoretical_claims": "No theory here.", "experimental_designs_or_analyses": "Already noted in Methods And Evaluation Criteria.", "relation_to_broader_scientific_literature": "This discrete sampling method can potentially applied to impactful combinatorial tasks such as LLM reasoning (EBM style) and molecular dynamics simulation.", "essential_references_not_discussed": "They have to includes some diffusion sampler works, amortized inference works and RL for vehicle routing works. \n\nMissed critical paper:\n\n[1] Dinghuai Zhang et al., \"Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets\", NeurIPS 2023 spotlight.", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. The proposed sampler demonstrates good performance on medium-scale combinatorial optimization benchmarks. Have you evaluated its performance on larger-scale problems (e.g., tens of thousands of nodes)? If so, how does scalability and performance stability compare to baseline methods at those larger scales?\n\n2. Considering that your evaluations mainly focus on combinatorial problems with relatively simple (local) constraints, have you investigated how well your method performs on problems with stronger global constraints, such as the Traveling Salesman Problem (TSP)? I'm particularly curious whether your regularization approach can effectively handle the global constraints inherent to routing or scheduling problems.", "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": "", "extra_scores": {}}, {"review_id": "G8O0zWefpp", "reviewer": "Reviewer_pJpR", "summary": "This paper introduces Regularized Langevin Dynamics (RLD), an approach inspired by normalized gradient descent to enhance combinatorial optimization (CO) methods. The authors develop two specific algorithms: Regularized Langevin Simulated Annealing (RLSA), which incorporates simulated annealing, and Regularized Langevin Neural Network (RLNN), which integrates neural networks. Through empirical evaluations on Maximum Independent Set (MIS), Maximum Clique (MCl), and Max Cut (MCut) problems, the authors demonstrate that their regularization technique improves performance over unregularized counterparts. While RLNN provides moderate improvements over certain learning-based methods, RLSA achieves performance comparable to the current state-of-the-art heuristic, iSCO, in CO problems. The authors further conduct ablation studies to validate the efficacy of the regularization.\n\n## update after rebuttal\nI increase my score to 3, but the writing should be further improved.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There are concerns regarding experimental fairness, particularly in the comparison of iSCO and RLSA… The experimental section in the iSCO paper reports DIMES achieving a size of 42.06 on ER-[700–800] in 12.01 minutes and 332.80 on ER-[9000–11000] in 12.51 minutes, which aligns with previously reported results. However, the iSCO results in this paper do not consistently reflect this… \n\nWe  sincerely appreciate  your question and want to offer an important clarification on a confounding issue. That is, in the  iSCO paper (Sun et al. 2023), they reported the **average running time** per instance for iSCO, while they reported the **total running time** for all other methods (DIMES included). This mis-alignment in time measurements makes iSCO look 16 or 128 times better than the reality (given the test-set size is 16 and 100 for ER graphs).   We have contacted the authors of that paper, and they confirmed that it was indeed an error on their behalf. (if needed and possible, we could attach their relevant material)\n\nTo fix such a confounding issue, we reported the **total running time** for all the methods in our results tables.  This is why our numbers look inconsistent to that in the iSCO paper, but for a good reason. We will revise related sentences about those tables, to make the point more transparent.\n\nWe fully understand that the mistake in Sun et al. 2023 caused the confusion in your review.  If the above clarification sufficiently addressed this issue, would you kindly adjust your score accordingly?\n\n> Since RLSA consistently outperforms RLNN across test cases, the contribution of the neural network method appears to be limited.\n\nRecall that our RLNN is designed to address a limitation of RLSA, i.e., its reliance on closed-form formulation of the gradient (as mentioned in the first sentence of Section 3.3).  In other words, RLSA requires additional knowledge for making it works; when such knowledge is not available, RLNN is a better alternative. And it should not be surprising that RLSA performs better since it has more prior knowledge.\n\n\n\n> RLNN is weaker than DiffUCO\n\nIn fact, RLNN has comparable performance to DiffUCO, based on the results in Tables 1 and 2 (RLNN outperforms DiffUCO in 4 out of 6 datasets). More importantly, the training of RLNN is much more efficient than that of DiffUCO because RLNN only needs to be trained locally while DiffUCO relies on a sequential training loss.  For example, the training time is 1 hour for RLNN and 2 days plus 2 hours  for DiffUCO (reported in section C.6, Sanokowski, et al. 2024)  on RB-200.\n\n> typos & metrics\n\nWe want to apologize for the presentation issues, and we would fix them in our future version.", "claims_and_evidence": "While the paper presents strong empirical evidence to support its claims, concerns remain regarding the fairness of experimental comparisons. Specifically, the evaluation methodology for iSCO may not be entirely consistent, as discussed in the weaknesses section.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are generally appropriate for CO problems. However, the choice of evaluation metrics for MIS could be improved. Metrics such as average performance drop (Drop) or approximation ratio (ApR), as used in prior works (e.g., Qiu et al., 2022; Ichikawa & Arai, 2024), might provide a more comprehensive assessment of performance.\n\n**Reference**\n\nQiu R, Sun Z, Yang Y. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. NeurIPS, 2022.\n\nIchikawa Y, Arai Y. Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling. arXiv preprint arXiv:2409.02135, 2024.", "theoretical_claims": "The theoretical claims appear correct, and I did not find any issues in the proofs presented. The mathematical formulations align with previous works on Langevin dynamics and simulated annealing.", "experimental_designs_or_analyses": "There are concerns regarding experimental fairness, particularly in the comparison of iSCO and RLSA, as discussed in the weaknesses section. A more rigorous comparison based on computational time rather than fixed iterations would be preferable. Additionally, the omission of Parallel Quasi-Quantum Annealing (PQQA) as a baseline is a notable limitation.\n\n**Reference**\n\nIchikawa Y, Arai Y. Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling. arXiv preprint arXiv:2409.02135, 2024.", "relation_to_broader_scientific_literature": "The paper is related to gradient-based sampling and combinatorial optimization.", "essential_references_not_discussed": "There are no critical omissions in terms of references.", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. The concept of regularization in Langevin dynamics is well-motivated and empirically validated.\n\n2. The implementation is simple yet effective, making it accessible for further research and applications.\n\n**Weaknesses:**\n\n1. **Experimental Fairness**: The experimental section in the iSCO paper reports DIMES achieving a size of 42.06 on ER-[700–800] in 12.01 minutes and 332.80 on ER-[9000–11000] in 12.51 minutes, which aligns with previously reported results. However, the iSCO results in this paper do not consistently reflect this. Additionally, the claim that “For a fair comparison, we run iSCO with the same number of steps and trials as we did for RLSA” is questionable. A more appropriate fairness criterion would be to impose the same computational time limit. For instance, iSCO (using fewer steps) reaches a size of 44.77 in 1.38 minutes, whereas RLNN takes 1.37 minutes to reach a size of 43.34. A time-based comparison would be fairer.\n\n2. **Experimental Performance**: In heuristic methods, iSCO outperforms RLSA in both the fewer-step scenario (size = 44.77) and the more-steps scenario (size = 45.15) compared to RLSA’s result (size = 44.10). In neural network approaches, DiffUCO achieves a size of 38.87 in 4.95 minutes on RB-[800–1200], whereas RLNN takes 6.24 minutes to reach a size of 38.46, indicating that RLNN is weaker than DiffUCO. Also, there are too many missing values (“-”) in the experimental tables, making cross-comparison difficult.\n\n3. **Significance of the Neural Network Approach**: Since RLSA consistently outperforms RLNN across test cases, the contribution of the neural network method appears to be limited.\n\n4. **Presentation Issues**: The presentation needs to be improved, and the paper contains an excessive number of typographical errors. \n\n \n**Reference**\n\nSun H, Goshvadi K, Nova A, et al. Revisiting Sampling for Combinatorial Optimization. ICML, 2023.", "other_comments_or_suggestions": "Below is a refined list of typos and minor textual issues:\n\n1. Line 82 (Left Column): Change \"thes\" to \"the.\"\n\n2. Line 150 (Left Column): Change \"an\" to \"a.\"\n\n3. Line 178 (Right Column): Change \"coefficiednt\" to \"coefficient.\"\n\n4. Line 219 (Left Column): Change \"mean-filed\" to \"mean-field.\"\n\n5. Line 227 (Right Column): Change \"Barabasi-Albert\" to \"Barabási-Albert.\"\n\n6. Line 263 (Right Column): Change \"mean-filed\" to \"mean-field.\"\n\n7. Line 724: Capitalize \"On.\"\n\n8. Equation (13): Replace \"$-c^{T}x_{i}$\" with \"$-c^{T}x$\" for consistency.\n\n9. Line 703: Correct the summation notation: \"$D_{ii} = \\sum j=1^N \\hat{A}{i,j}$\" should be \"$D{ii} = \\sum_{j=1}^N \\hat{A}_{i,j}$\".", "questions_for_authors": "1. **Evaluation Criteria Consistency**: Shouldn’t the evaluation criteria be aligned across all experiments to ensure fairness, given that Sun et al. (2023) reports consistent DIMES results when comparing with iSCO?\n\n2. **Iteration Step Size Justification**: Wouldn’t comparing performance at multiple time budgets rather than fixing iteration steps arbitrarily be a more rigorous approach, given that iSCO can reach better solutions within shorter execution times?", "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": "", "extra_scores": {}}, {"review_id": "BFqtwOGQJ5", "reviewer": "Reviewer_aSe5", "summary": "*Regularized Langevin Dynamics for Combinatorial Optimization* proposes Regularized Langevin Dynamics (RLD), a sampling framework for combinatorial optimization (CO). The authors note that discrete Langevin dynamics (LD) has limitations in exploration when applied to CO. RLD addresses this by enforcing an expected distance between sampled and current solutions, avoiding local minima.\n\nTwo CO solvers are developed based on RLD: Regularized Langevin Simulated Annealing (RLSA) and Regularized Langevin Neural Network (RLNN). RLSA is a simple yet effective algorithm that often outperforms previous state - of - the - art (SOTA) SA methods. For example, it reduces the running time of the previous SOTA SA method by up to 80% while achieving equal or better performance. RLNN, partially based on reinforcement learning, can be trained efficiently with a local objective.\n\nEmpirical results on three classical CO problems (Maximum Independent Set, Maximum Clique, and Max Cut) show that both RLSA and RLNN can achieve comparable or better performance than previous SOTA SA and NN - based solvers. Ablation studies verify the effectiveness of the regularization in RLD. Overall, RLD offers a promising framework for enhancing traditional heuristics and NN models to solve CO problems, though its effectiveness on non - binary data and theoretical understanding remain areas for future research.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your positive feedback, here are the response to your concerns.\n\n>Is there any advantage of RLNN compared to RLSA? It seems it falls behind of RLSA on both decision quality and inference time.\n\nRecall that our RLNN is designed to address a limitation of RLSA, i.e., its reliance on closed-form formulation of the gradient (as mentioned in the first sentence of Section 3.3).  In other words, RLSA requires additional knowledge for making it works; when such knowledge is not available, RLNN is a better alternative. And it should not be surprising that RLSA performs better since it has more prior knowledge.\n\n\n> It would be better if the paper could give a theoretical analysis of the proposed regularization.\n\nThank you for your suggestion. Given the short time period, here we simply outline some perspective for the theoretical analysis.\n\n\nWhen not at the local optimum, RLD could accelerate the convergence. The main assumption here is that the graph is sparse, so it is unlikely for $d$ variables to be adjacent to each other and the gradient remains accurate after the change.\n\nIn terms of the ability to escape optimum, we would like to point out the connection between RLD and path-auxiliary proposal [1], whose first-order version, PAFS, is also the fundamental algorithm behind iSCO. RLD could be treated as a generalized version of PAFS in terms of updating in expectation $d$ coordinates at each step, so it also satisfies Theorem 3 in that paper. Based on this generalization form, we propose a more efficient (parallel) sampling strategy to avoid the sequential sampling in PAFS, thus accelerating the search and significantly outperforming iSCO. \n\n[1] Sun, et al. Path Auxiliary Proposal for MCMC in Discrete Space. ICLR 2022.", "claims_and_evidence": "The paper claims that regularization could mitigate the local optima during the optimization process. It then explains this claim using an MIS problem as an example as well as experiments. It could be better if  provide more theoretical analysis.", "methods_and_evaluation_criteria": "The method and evaluation make sense in general.", "theoretical_claims": "The paper does not give theoretical claims.", "experimental_designs_or_analyses": "I checked the experimental results, the ablation study and the curve of primal gap, which gives convincing results to back up the proposed method.", "relation_to_broader_scientific_literature": "The paper is related to combinatorial optimization and gradient-guided generative algorithms.", "essential_references_not_discussed": "The paper does not contain missed references as far as I know.", "other_strengths_and_weaknesses": "Advantage:\n- The proposed RLSA and RLNN achives better decision quality with lower inference time. The ablation study validates the effectiveness of proposed regularization.\n- The proposed regularization contributions to the discrete sampling algorithm for addressing the local optimal problem during optimization.\n\nDisadvantage:\n- It would be better if the paper could give a theoretical analysis of the proposed regularization.", "other_comments_or_suggestions": "None", "questions_for_authors": "Questions:\n- Is there any advantage of RLNN compared to RLSA? It seems it falls behind of RLSA on both decision quatlity and inference time.", "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": "", "extra_scores": {}}, {"review_id": "nLi3y1ouDl", "reviewer": "Reviewer_B24V", "summary": "The paper introduces Regularized Langevin Dynamics, a novel sampling-based method for improving solutions to CO problems through LD. RLD incorporates regularization to control the distance of solution updates, enhancing traditional heuristics and neural network models by mitigating the issue of local optima. This approach outperforms SOTA baselines in solving large-scale graph-based CO problems, showing improved efficiency and adaptability across various settings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> However, it seems to lack theoretical evidence\n\n>Is it possible to apply regularization to the solution updates only when detecting local optima?\n\nThank you for your insightful question. Given the short time period, here we simply outline some perspective for the theoretical analysis.\n\n\nWhen not at the local optimum, RLD could accelerate the convergence. The main assumption here is that the graph is sparse (which is very common in CO), so it is unlikely for $d$ variables to be adjacent to each other and the gradient remains accurate after the change.\n\nIn terms of the ability to escape optimum, we would like to point out the connection between RLD and path-auxiliary proposal [1], whose first-order version, PAFS, is also the fundamental algorithm behind iSCO. RLD could be treated as a generalized version of PAFS in terms of updating in expectation $d$ coordinates at each step, so it also satisfies Theorem 3 in that paper. Based on this generalization form, we propose a more efficient (parallel) sampling strategy to avoid the sequential sampling in PAFS, thus accelerating the search and significantly outperforming iSCO. \n\n[1] Sun, et al. Path Auxiliary Proposal for MCMC in Discrete Space. ICLR 2022.\n\n> How do you initialize the solutions?\n\nThe initialization is a Bernoulli distribution of probability 0.5 for each variable.\n\n> the hyperparameters are extensively tuned across problems and problem scales\n\nWe would like to clarify that all our hyperparameters are tuned via **random search** (see section A.1) rather than **grid search**. The hyperparameters in Tables 4 and 5 reflect this randomness rather than an extensive tuning process. \n\nMoreover, only the initial temperature $\\tau_0$​ and the regularization target $d$ would impact performance and were carefully tuned in our experiments. We believe that tuning just two parameters is far from overfitting the dataset. \n\n> How do you ensure a fair comparison with the baseline methods, especially the ablation baseline (e.g., vanilla SA)\n\nFor our ablation baseline, $K$, $T$, $\\beta$ and $\\tau_0$ are kept the same as the ones used in our method. Another parameter $\\alpha$ is searched over {0.001,0.01,0.1}$ as presented in Figure 1. \n\n> Methods such as DIMES and DIFUSCO learn to initialize the solutions … Could you please elaborate on the rationale behind the choice of baselines?\n\nWe would like to clarify that our method also initializes the solution since it does not guarantee the feasibility. We use the greedy decoding to transform the searched initialization to a feasible solution. For DIMES and DIFUSCO, they also have the greedy decoding variant. But given their poor performance, we only report the best variant with a sampling-based decoding.\n\n> Is the high efficiency of your method due to the ability to use a very large batch size … Comparing per-instance solution duration …\n\nWe test all instances sequentially in our experiment, so the per-instance solution duration is simply total_time/(# instances). RLSA only needs <0.2s per instance except on ER-[9000-11000] (around 6s per instance).\n\n>  it appears to be much less effective for a prominent and extensive subset of CO problems involving global constraints\n\nThis is an insightful question but we want like to mention that tackling global constraints typically need strong inductive biases and this is a common challenge for all energy-based models (EBMs). Here we refer to some recent EBM-based CO solvers that also face this dilemma and exclude the evaluation on the problems with global constraints such as TSP.\n\n[1] Haoran Sun et al., ‘Revisiting Sampling for Combinatorial Optimization’, ICML 2023.\n\n[2] Dinghuai Zhang et al., \"Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets\", NeurIPS 2023 spotlight.\n\n[3] Sebastian Sanokowski et al., A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.\n\nThe reason behind is because the global constraints are highly structured, while EBMs are general solvers, whose formulation itself prevents a better performance than heuristics with a strong inductive bias such as k-OPT.\n\n> It seems reasonable to compare your method against other approaches designed to escape local optima during solution improvements. Are there any feasible alternatives you considered for comparison?\n\nNote that SA itself is a strategy to escape the local optimum and we have already included the SOTA baseline iSCO. We have also experimented with the restarting strategy on top of our ablation baseline but find no clear advantage.\n\nAnother method is semidefinite programming, as we included in Table 2. However, this method is in general very slow compared to SA methods.\n\n\n\n\n>Is it possible to adaptively regularize the solution updates?\n\nWe have tried but found no clear gain. Note that RLD itself should be counted as an adaptive strategy on the MCMC proposal (with an adaptive $\\alpha$ in Equation 8).", "claims_and_evidence": "- One fundamental motivation behind this paper is 'the difference in local optima between continuous optimization and combinatorial optimization.' However, it seems to lack theoretical evidence, and it remains unclear whether this difference is specific to certain function landscapes or applies to continuous/combinatorial optimization problems in general.\n\n- Although QUBO is a fairly general formulation for CO problems, it appears to be much less effective for a prominent and extensive subset of CO problems involving global constraints, such as the TSP. The authors are encouraged to thoroughly discuss the method's limitations and scope.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "I have some concerns regarding the experimental designs:\n\n- How do you initialize the solutions?\n- The authors seem to address a fundamental problem in optimization, i.e., the trade-off between exploration and exploitation. Regularizing the update distance to a fixed scalar seems overly simplified to serve as a generic solution to this issue. I noticed that, in Tables 4 and 5, the hyperparameters are extensively tuned across problems and problem scales. Is it possible that your methods, under certain sets of hyperparameters, overfit the benchmark datasets? How do you ensure a fair comparison with the baseline methods, especially the ablation baseline (e.g., vanilla SA)? Did you also search the hyperparameters within the same ranges?\n- It seems that some baselines are not directly competitive with your methods. Methods such as DIMES and DIFUSCO learn to initialize the solutions, while your sampling-based method learns to update them. Could you please elaborate on the rationale behind the choice of baselines? Is it possible to leverage the best of both worlds?\n- It seems reasonable to compare your method against other approaches designed to escape local optima during solution improvements. Are there any feasible alternatives you considered for comparison?\n- Is the high efficiency of your method due to the ability to use a very large batch size, given that your method is lightweight in terms of computation and memory consumption? Comparing per-instance solution duration, as discussed in many benchmarking and criticism papers, seems reasonable.", "relation_to_broader_scientific_literature": "This paper contributes to two threads of literature, as discussed in the Related Work section.", "essential_references_not_discussed": "Section 5.1 lacks an adequate discussion of recent RL-based methods [1]; the most recent work cited was published in 2022.\n\n[1] RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark.", "other_strengths_and_weaknesses": "I enjoyed reading this paper. This paper is very well-written and introduces a simple and effective method. I encourage the authors to address my concerns raised above.", "other_comments_or_suggestions": "Typos:\n- \"thes\"; line 82\n- \"difference in local optimal between continuous optimization and continuous optimization\", line 415", "questions_for_authors": "- Although you annotate both DIMES and RLNN as RL-type methods, can I consider them distinct types of approaches? DIMES appears to learn how to generate a solution in one step, whereas your RLNN learns to iteratively update the solution based on RLD. Furthermore, can I consider them not necessarily competitive or mutually exclusive, since you could initialize your solution with DIMES or DIFUSCO and then refine it using RLNN?\n- Is it possible to adaptively regularize the solution updates?\n- Is it possible to apply regularization to the solution updates only when detecting local optima?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers praise the idea of regularizing Langevin dynamics and applaud the simplicity of the approach as well as the effectiveness. Some reviewers argue that the novelty is too low, but I think simplicity is sometimes confused with low novelty and thus propose ignoring these comments entirely, as simplicity is good. I have also assessed the experiments due to some questions from the reviewers, but believe them to be adequate for showing the performance of the method. The baselines presented are also up to date. The final negative remark is regarding the clarity of the paper. I encourage the authors to clean up their descriptions according to the reviewer's comments and I believe the paper will be in an adequate state for publication.
Decision: Accept (poster)