Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling
Authors: Yuma Ichikawa
Yamato Arai
Venue: ICLR 2025 Poster (2025)
Keywords: Combinatorial Optimization
Discrete Optimization
Learning for Combinatorial Optimization
Unsupervised Learning for Combinatorial Optimization
Learning for Combinatorial Optimization
Primary area: optimization
TL;DR: A scalable combinatorial optimization solver integrating gradient-based updates with quasi-quantum annealing

Abstract: Learning-based methods have gained attention as general-purpose solvers due to their ability to automatically learn problem-specific heuristics, reducing the need for manually crafted heuristics. However, these methods often face scalability challenges. To address these issues, the improved Sampling algorithm for Combinatorial Optimization (iSCO), using discrete Langevin dynamics, has been proposed, demonstrating better performance than several learning-based solvers. This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA). QQA smoothly transitions the objective function, starting from a simple convex function, minimized at half-integral values, to the original objective function, where the relaxed variables are minimized only in the discrete space. Furthermore, we incorporate parallel run communication leveraging GPUs to enhance exploration capabilities and accelerate convergence. Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers across various benchmark problems. Notably, our method exhibits superior speed-quality trade-offs for large-scale instances compared to iSCO, learning-based solvers, commercial solvers, and specialized algorithms.

Published as a conference paper at ICLR 2025
OPTIMIZATION BY PARALLEL NEALING WITH GRADIENT-BASED SAMPLING
AN-
Yuma Ichikawa
Yamato Arai
Fujitsu Limited,
Fujitsu Limited,
Department of Basic Science
Department of Basic Science University of Tokyo
University of Tokyo
ABSTRACT
Learning-basee based methods have gained attention as purposs solvers due to their ability to automatically learn problem-specific heuristics, reducing the need for manually crafted heuristics. However, these methods often face scala- bility challenges. To address these issues, the improved Sampling algorithm for Combinatorial Optimization (iSCO), using discrete Langevin dynamics, has been proposed, demonstrating better performance than several tearning-basee solvers. This study proposes different approach that integrates gradient- based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA). QQA smoothly transitions the objective function, starting from simple convex function, minimized at half-integral values, to the original objective function, where the relaxed variables are minimized only in the discrete space. Furthermore, we incorporate parallel run communication leveraging GPUs to enhance exploration ca- pabilities and accelerate convergence. Numerical experiments demonstrate that our method is competitive general-pure purpose solver, achieving performance comparable to iSCO and learning-based solvers across various benchmark problems. Notably, our method exhibits superior speed-quality trade-offs for large-scale instances compared to iSCO, learning-based solvers, commercial solvers, and specialized algorithms.
INTRODUCTION
Combinatorial optimization (CO) problems aim to find the optimal solution within discrete space. a fundamental challenge in many real-world applications (Papadimitriou & Steiglitz 1998 Crama 1997). Most CO problems are NP-hard, making it challenging to solve large-scale problems within feasible computational time. As result, significant effort has been devoted to developing algorithms that efficiently produce high-quality approximate solutions. Heuristic methods have been widely used to obtain approximate solutions, but they often require problem-specific knowledge. Accordingly, increasing efforts have been directed toward developing general-purpont solvers that can be applied to broad range of problems to reduce the need for crofcei--peccfic insights.
Sampling-based approaches have been proposed, which treat CO problems as sampling problems. Simulated annealing (SA) (Kirkpatrick et al. 1983), a widely known technique, leverages local thermal fluctuations and updates (Metropolis et al.] 1953) Hastings 1970). Additionally, techniques such as tempered transitions (Neal) 1996) and exchange Monte Carlo algorithms (Hukushima & Nemoto 1996) have shown strong performance in practical CO problems (Johnson et al. 1989 1991
Earl & Deem 2005). However, these methods depend on local updates, where only one dimension is updated at time, and the update process across dimensions typically cannot be parallelized. As result, these methods become computationally infeasible for large-scale CO problems.
Learning- methods have recently gained recognition as general-purpose solvers for their ability to learn problem-specine heuristics automatically. This reduces the need for manually designed heuristics and leverages modern accelerators like GPUs and TPUs. Some learning-basee methods
rely supervised data, which is often difficult to obtain (Li et al. 2018 Gasse al. 2019 Gupta
ct al. 2020). Reinforcement learning (Khalil et al.) 2017 Kool et al. [2018] Chen & Tian 2019)
and unsupervised learning approaches (Karalias & Loukas 2020 Wang al. 2022 Wang & Li

---

Published as a conference paper at ICLR 2025
2023) have broadened their scope of applications. However, these approaches encounter challenges when applied to -ftt----isttiuttion instances, limiting their flexibility in addressing a wide range of problem distributions. In response, unsupervised dearning-based solvers that do not depend on training data have emerged, leveraging the ability of machine learning models to learn meaningful representations (Schuetz et al. [022a b Ichikawa
2023). These methods address CO problems by optimizing the weight parameters of machine learning models, but model selection is critical in determining solution quality |Schuetz et al. (2023). Furthermore, additional computational costs arise because the number of learnable parameters exceeds the number of decision variables. Moreover, the performance of these methods compared to sampling- baaedd solvers remains unclear.
On the other hand, the improved Sampling algorithm for CO (iSCO) (Sun et al. 2023b) was proposed, motivated by advances in Markov Chain Monte Carlo methods for discrete space. This method integrates discrete Langevin dynamics (Sun et al.) 2023a) with traditional annealing techniques, demonstrating results comparable to or better than learning- solvers by using gradient informa- tion from the objective function. This study proposes different method that combines gradient- based updates through continuous relaxation with Quasi Quantum Annealing (QQA), technique inspired by quantum annealing (Kadowaki & Nishimori 1998). QQA progressively transitions the objective function, beginning with a simple convex function minimized at half-integral values-similar to the state where the transverse field dominates in quantum annealing. In the end, this process converges to the original objective function, where the relaxed variables are minimized only within the discrete apace-analogous
the classical state without the transverse field in quantum annealing. Unlike iSCO, this study introduces an extended Boltzmann distribution with a communication term between parallel runs. This distribution efficiently leverages GPUs, enabling broader exploration with minimal overhead and also accelerating convergence.
Numerical experiments on the same benchmark used as iSCO (Sun et al. 2023b), along with several additional benchmarks, demonstrate that our method is competitive general purposs solver, achieving performance comparable to iSCO and learning- based solvers across all benchmarks. For larger problems, our method provides better speed-quality trade-offs than iSCO, learning-hased solvers, commercial solvers, and specialized algorithms.
BACKGROUND
Combinatorial Optimization.
The goal of this study is to solve CO problems formulated as
min f(x; X(C) { x E (0, 13 .EX(C)
(x; C) < 0, hy(2; C) = Vj ej }
vi 1
where C' C C denotes instance-specific parameters, such as graph G (V, E), and C represents set of all possible instances. The vector æ = (I;)) E {0. 1] represents the discrete decision variables, and (C) denotes the feasible solution space. f X' x C + RR is the cost function, while X' x C + IR and hy X' x C + R represent inequality and equality constraints, respectively. We also the shorthand notation [N] = (1, N). with N E N.
To transform the constrained CO problem into a sampling problem, we reformulate it as an uncon- strained CO problem using the penalty method:
I+J
min 1(x; C, ((=; f(x; a(c Σ Xeylaa C), (0
where u; ;; (00, 1J xC - RR Vi E []+ represents penalty terms, which increase as the constraints violated. For example, these penalty terms can be defined
Vi [7] (x C)= max(0, (m; C)), Vj E [J], My uy( C) (m; 2
A = (A:) TRJ denotes the penalty parameters that control the balance between constraint satisfaction and cost function minimization.
Energy Based Model. Boltzmann distribution:
For the penalized objective function 1(2; C, A), we define the following
P(x:T) Z(T)
Alla;CA)), Z(T)= Σ e (((;;CA))
2

---

Published as a conference paper at ICLR 2025
where Ex represents the over all possible values of æ, and T R2o is parameter called temperature, which controls the smoothness the distribution. As the temperature approaches infinity, the Boltzmann distribution P(x; I') converges to uniform distribution over {0. 1 When the temperature = 0, the Boltzmann distribution becomes a uniform distribution over the optimal solutions of Eq. 2 The CO problem can be transformed into sampling problem of P(æ: 7 0).
Algorithm (Metropolis et al. 1953 Hastings 1970) is general method for sampling from high-dimensional distributions. This algorithm uses distribution Q which satisfy the ergodicity condition. A Markov chain (az²)) 1/=o is constructed have P(æ; T) as its stationary distribution by following steps: starting from x (0) p(O), where p(o) is the initial distribution, at each step propose x' Q(x' (zx))), and with probability
Metropolis- Micropooli-HHastings Algorithm. The Metropolis-
A(æ' (0)) = min (1, P(z'; P(x':T)((2
P(x(1) (TQ (x(())
accept æ' as the next state x (1+1) x', or with probability - A(a') reject x' and retain the previous state (++1)) (*) The proposal distribution is typically a local proposal, such as a flipping single bit. Gibbs sampling (Geman & Geman 1984) is a local update method where the proposal
distribution the conditional distribution, Q (+) [xx' Pa [==;; with æ-; \ {x;). In
this case, the acceptance rate A(x' ((()) always The effectiveness of the algorithm is highly influenced by the choice of the proposal distribution (ax(1//zz))
Simulated Annealing (SA). SA was introduced by Kirkpatrick et al. 1983 : Cerný (1985). While
the original CO problem can be solved by sampling from the distribution limy--s P(æ; T), directly sampling from the distribution is difficullt due to its highly nonsmooth nature at low temperatures. To overcome, SA performs Metropolis-Hasting updates while gradually lowering the temperature T to zero through temperature path, T = (To: Ti..... TM) where the path To > 77 > ... > TM - 0. This approach enables the system reach state with lower energy over time.
METHOD
We begin by explaining the continuous relaxation approach Section 3.1 Section 3.2 introduces
an extended Boltzmann distribution and QQA. Section 3.3 proposes the communication between parallel runs, and Section 3.4///mmariiiz optimization-speciff techniques. This overall approach is termed Parallel cuasi-Quantum Annealing (PQQA).
3.1 CONTINUOUS RELAXATION STRATEGY
The continuous relaxation strategy reformulates a CO problem into a continuous one by converting discrete variables into continuous ones as follows:
I+J
min Kp: C,A,, ((: A(P:C) + Σ Aa,p::C, pE(O.]]N
where p = (pi) E [o, 1j denotes the relaxed continuous variables, where each binary variable t; E [0, is relaxed to a continuous value p: E [0, 1]. f [0, x C - R represents the relaxation of f, satisfying f(æ; C) f C) for æ E {0, 1 Similarly, for all i E [T JJ. à; denotes the relaxation Ug with (x; (z C*) for x E (0, The landscape of relaxed objective function i(p; C, A) remains complex even after continuous relaxation, posing challenges for optimization. Moreover, continuous relaxation encounters rounding issues, where artificial rounding is needed to map the continuous back to the discrete solution, undermining the robustness.
3.2 QUASI-QUANTUM ANNEALING
We represent the relaxed variable p E [0, 1 as a real-valued parameter w E R and nonlinear mapping to evaluate gradients and introduce following entropy term to control the balance between
3

---

Published as a conference paper at ICLR 2025
continuity and discreteness of relaxed variables:
F(o(w); - =((o()); +)(((()))))
where a IN + [0, 1 denotes element-wiss mapping, such as the sigmoid function and y E R denotes a penalty parameter. The relaxed variables are represented as ( = (a(w) sigN E [0, 1] The entropy term s(a(w)) is a convex function, which attains minimum value of 0 when
(w)) E {0, 13 and its maximum when (ww) = 1w/2. This study employs the following entropy:
s(a(w)) Σ [1 (2o(w;; - 1) E {2m E N),
which was introduced by Ichikawa 2023) and is referred to as o-entropy. Furthermore, we extend the entropy term to general discrete optimization problems. Details of this generalization are provided in Appendix B The effectiveness is demonstrated through numerical experiments on two benchmarks: the balanced graph partitioning Section 5.4 and the graph coloring problem in Section 5.5
Subsequently, the Boltzmann distribution in Eq. is extended to the continuous space [o, 1 using Eq. (3.2) as follows:
P(o(w)),,T) Z(T,T)
- (M((W) Z(7,T) JRy
dwe +(((W))CAM)
When y is negative, i.e., < O, the relaxed variables tend to favor the half-integral value (ww) = 1x/2. smoothing the non-convexity of the objective function i(p: C, X) due to the convexity of the entropy term s()). This state can be interpreted as a quasi-quantum state, where the values are uncertain between 0 and 1. Conversely, when is positive, i.e., O, the relaxed variables favor discrete values. This state can interpreted as a classical state, where the values are deterninistically determined as either 0 or 1. Formally, the following theorem holds.
Theorem 3.1. Under the assumption that the objective function î(p; C) is bounded within the domain [0, 1],, the Boltzmann distribution lim limy-p P(o(w): converges to a uniform distribution over the optimal solutions of Eq. (2), ie., x" argmin, (x: C, A). Additionally,
lim 1i (ar) T) converges to a single-peatee distribution I 8(0(w:) 1/2).
The detailed proof can be found in Appendix A.I
The following gradient- based update can be used for any 7, provided that r(w) is differentiable:
w ++1 = w' - "DVrr(a(w') C, + 2
where 1) is the time step size, and & NOx,,, IN) ) is Gaussian noise with IN E RNNN denoting an identity matrix and O representing the zero vector (0.... .o....... 0) E R.N. This update rule generates a Markov chain whose stationary distribution is given by Eq. (.2) when 7) is sufficiently small. Unlike the local updates in conventional SA for discrete problems, this method simultancously updates multiple variables in single step via the gradient, allowing for high scalability.
Following Ichikawa (2023), the annealing strategy conducted on y from a negative to a positive value while updating the parameter w. Initially, negative is set to enable extensive exploration by smoothing the non-convexity of (()( C, A), where the quasi-quantuon state a(w) 1x/2 dominates. Subsequently, the penalty parameter 7 is gradually increased to positive value until the entropy term approaches zero, i.e., s(o(w))
to automatically round the relaxed variables by smoothing out continuous suboptimal solutions oscillating between I and 0. This annealing is similar to quantum annealing, where the system transitions from state dominated by a superposition state of 0, 1, induced by the transverse field, to the ground state of the target optimization problem. Therefore, we refer to this annealing as Quasi muasi-Quantuni Annealing (QQA).
3.3 COMMUNICATION IN PARALLEL RUNS
Gradient-basee updates in QQA enable efficient batch parallel computation for multiple initial values and instances | using GPU or TPU resources, similar to those used in machine learning tasks. We propose communication between these parallel runs to conduct exhaustive search
4

---

Published as a conference paper at ICLR 2025
and obtain diverse solutions. Specifically, we define the extended Boltzmann distribution over all S parallel runs (a(w(())) 1==1 as follows:
P (1 xe - 13
R
=E (o(((ol))) Sa Σ STD ( i=1
where STDRay { k- denotes the empirical standard deviation (E k= (a -E
-k'=1 ay /g/K)²/KK /
and a E [0, 1] is a parameter controlling the diversity of the problem. A larger value a enhances the exploration ability during the parallel run. The second term is natural continuous relaxation
of the Sum- Hamming distance (Ichikawa & Iwashita 2024). As in Eq.
(..) we perform Langevin
updates on )=
whose stationary distribution given by Eq.
3.3
3.4 OPTIMIZATION SPPECIC ACCELERATIONS
We focus optimization, rather than generating sample sequence that strictly follows the probability distribution Eq. (3.2). This section introduce several optimization-specif enhancements to the Langevin dynamies in Eq. (3.2) that specifically designed to improve efficiency in optimization.
Sensitive Transitions. The update of w is linked with the objective function through the element- wise mapping (.), which can reduce sensitivity with respect w. To address this issue, we propose replacing the update in Eq. (3.2) with the following two-steps. In the first step, rather than updating w directly, we update the relaxation variables p E RN as follows:
+ 22nTE.
where F RN,, C + R is the relaxed form of f, satisfying F(p: C) F(p; C.) for any p [0, 1| This update leads to a more sensitive transition than updating w. as it bypasses (-).. However, p' may fall outside the range [0, 1j after the update Eq. (3.4). In the second step, we update p' by setting p* (p'). ),p) which ensures that pt always lies within the range [0, 1|
Furthermore, the gradient-based update in Eq. (3.4) is replaced with more sophisticated optimizers to improve exploration efficiency, In this paper. we employ AdamW (Loshchilov & Hutter 2017). Note that the stationary distribution of this optimization-sppe -specffic update does not correspond the Boltzmann distribution in Eq. 3.2)).
4 RELATED WORK
Sampling- methods (Metropolis et al. 1953 Hastings 1970 Neal 9966 Hukushima & Nemoto
1996 have been widely applied to various CO problems, including MIS (Angelini & Ricei-Tersengl! Tersenghi
2019 TSP (Kirkpatrick et al.
1983 Cerny 1985 Wang et al. 2009). planning Chen & Ke 2004
Jwo et al. 1995). scheduling (Seçkiner & Kurt |007] Thompson & Dowsland 1998). and routing
Mooukkool-MMohhadaal et al. 2007; Van Breedam 1995). However, these methods generally depend
on local updates, such as Gibbs sampling or single-bit flip Metropolis updates, which can restrict their scalability. To address this limitations, methods leveraging gradient information from the objective function have been proposed. Continuous relaxation techniques, conceptually related to our approach, have also been introduced (Zhang al., 2012). However, these methods often struggle capture the topological properties of discrete structures Pakman & Paninski, 2013 Mohasel Afshar & Domke 2015) Dinh et al. 2017] Nishimura al.) 2020). In contrast, our method gradually recovers the discrete nature of the original problem through QQA. Sun et al. (2023b) proposed iSCO, a sampling- based solver using discrete Langevin dynamics (Sun et 2023a Zhang et al. 2022 Sun et al. [0021] Grathwohl et al. 2021), which accelerates traditional Gibbs sampling and improves performance. While iSCO approximates the acceptance rate of candidate transitions in discrete Langevin dynamics using first-order Taylor expansion, its effectiveness for general discrete optimization problems remains uncertain. In addition to adjusting the temperature path, hyperparameter tuning is required for the path auxiliary sampler (Sun al. (021)) Furthermore, communication between parallel chains in PQQA has not been implemented, preventing iSCO from fully utilizing the benefits of parallel execution GPUs.
5

---

Published as a conference paper at ICLR 2025
5 EXPERIMENT
In this section, the performance of PQQA is evaluated across five CO problems: maximum inde- pendent set (MIS), maximum clique, max cut, balanced graph partition, and graph coloring. For each problem, experiments are performed on synthetic and real-world benchmark datasets, including instances used in iSCO (Sun et al. 2023b), all benchmarks recently proposed (Sun et al., 2023a). and instances commonly used in learning- based solvers. Detailed formulations and instances of these problems are presented in Appendix D. ladd D.2] PQQA is compared with various baselines, includ- ing sampling-basee methods, learning-basd based methods, heuristics, and both general and specialized optimization solvers. Notably, iSCO (Sun et al.) 2023b) is employed as our direct baselines.
Implementation. We use the a-entropy with a = across all experiments. The parameter y is increased linearly from Ymin 22 "imax 0.1 with each gradient update. After annealing, the relaxed variables are converted into discrete ones using the projection method: for all i E [N]. we map as x; (pp - 1/2), where θ is the step function. Notably, even with 7max 0.1, the solution became almost binary, indicating robustness in the rounding process. We set ((w) = Clamp w), where Clamp(w) (w) constrains the values within the range [o, 1 1| Specifically, for each E [NV]. if w; is less than 0, it is set to 0; if w, exceeds 1, it is set to 1. For further discussion on why the sigmoid function is not applied for (w)) see Appendix C.I The AdamW optimizer (Loshchilov & Hutter 2017) is used. The parallel number S is set to 100 or 1,000. We report the runtime of PQQA single V100 GPU. The runtime can be further improved with more powerful GPUs or additional GPUs. Section 5.6 provide
ablation study that examines the effect of different hyper-parametto Refer to Appendix for further implementation details. For all benchmark CO problems, the soft solution at the end of the training process became 0 or 1 within the 32-bit Floating Point range in PyTorch GPU. Additionally, no violations of the constraints were observed in our numerical experiments. Thus, following results presented in are feasible solutions.
Evaluation Metric. This experiment primarily evaluates solution quality using the approximation ratio (ApR), the ratio between the obtained and optimal solutions. For maximization problems, ApR 1. and the solution is considered optimal when ApR = 1. In cases where an optimal solution is not guaranteed due to problem complexity, we directly compare objective functions or report the ratio relative the solution found by a commercial solver with the best effort or asymptotic theoretical results. The specific definition of ApR used in each section is provided accordingly.
5.1 MAX INDEPENDENT SET
SATLIB and Erdós-Rényí Graphs. We evaluate PQQA using the MIS benchmarks from recent studies (Goshvadi et al. 2023: Qiu et al. 2022). which includes graphs from SATLIB (Hoos & Stützle 2000) and Erdós Rényi graphs (ERGs) of various sizes. Following Sun et al. 2023b), the instances consist of 500 SATLIB graphs, each containing with 403 to 449 clauses, corresponding at most 1,347 nodes and 5.978 edges, 128 ERGs with 700 to 800 nodes each, and 16 ERGs with 9,000 to 11,000 nodes each. PQQA is performed under four settings: a number of parallel runs with S 5= 100 or S = 1000 and fewer steps (3000 steps) more steps (30000 steps), similar to the experiment in iScO (Sun et al. 2023b). Table [ shows the solution quality and runtime. The results indicate that PQQA achieves better speed-quality trade-offs than learning-base based methods. In particular. PQQA outperforms both iScO (Sun et al. 2023b) and KaMIS (Lamm et al. [016)] Hespe et al. 2019), the winner of PACE 2019 and a leading MIS solver, especially on both ERGs with shorter runtimes. Notably, for larger ERGs, PQQA finds much better solutions in a shorter time than iSCO and KaMIS.
Regular Random Graphs. We focus on MIS problems on regular random graphs (RRGs) with a degree greater than 16, which are known to be particularly difficult (Barbier et al. 2013). Previous studies have pointed out the difficulties in solving these instances with learning- based solvers (Angelini & Ricci- Tersengh 2023 Wang & Li. 2023). Building on the observations of Angelini & Ricci-Tersenghi (2023). we employ MIS problems on RRGs with d = 100 and d 20 with
sizes ranging from 10s to 10 variables. Additionally, we evaluate the ApR against the asymptotic theoretical values in the limit of infinite number of variables (Barbier et al.) 2013). If solvers
cannot run even on V100 GPU, the result is reported as N/A. We employed QQA (S = 1) using
two different step sizes: fewer steps (3,000 steps) and more steps (30,000 steps). Table shows

---

Published as a conference paper at ICLR 2025
Table I:
ApR and runtime evaluated three benchmarks provided by DIMES QQu et al. 2022).
The ApRs are evaluated against the results obtained by KaMIS. Runtime is reported as the total clock time per instance in seconds (s/g) or minutes (m/g). The runtime and ApR are sourced from Sun et al. 2023b). Baselines include the OR solvers, learning- sorning-basedd methods using Reinforcement Learning (RL) and Supervised Learning (SL) combined with Tree Search (TS), Greedy decoding (G)
or Sampling (S), and iSCO. Methods that fail produce results within 10 times the time limit of
DIMES are marked as N/A.
SATLIB
ER-[700-800)
ER-[9000-1
Method
Type
ApRt
Time
ApRt
Timel
ApRt
Time.
KaMIS
OR
1,000
4.50s/g
1.000
24.44s/g
1.000
28.5m//
Gurobi
OR
1.000
3.12s/g
0.922
23.44s/g
N/A
N/A
SL+TS
N/A
N/A
0.865
9.38s/g
N/A
N/A
Intel
SL+G
0.988
2.78s/g
0.777
2.84s/g
0.746
18.83s/g
DGL
SL+TS
N/A
N/A
0.830
10.65s/g
N/A
N/A
LwD
RL+S
0.991
2.26s/g
0.918
2.97s/g
0,907
28.35s/g
RL+G
0.989
2.90s/g
0.852
2,87s/g
0.841
19.54s/g
DIMES
RL+S
0.994
2.43s/g
0.937
5.63s/g
0.873
46,91s/g
fewer steps
0.995
0.70s/g
0.998
0.65s/g
0.990
35.18s/g
iSco
more steps
0.996
1.83//g
1.006
2.61s/g
1.008
4.69m/g
fewer (S 100)
0.993
0.88s/g
1.004
0.35s/g
1.027
21.86s/g
more (S 100)
0.994
8.71s/g
1.005
3.33s/g
1.039
3.66m/g
PQQA
fewer (S =1,000)
0.996
9.00s/g
1.007
3.20s/g
1.033
2.58m/g
more (S -1,000)
0.996
1.50m/g
1.009
32.06s/g
1.043
25.50m/g
Table 2: ApR and runtime are evaluated using five different seeds. ApR is measured relative to the asymptotic theoretical result (Barbier et al. 2013). Runtime is reported as the total clock time per instance in seconds (s/g) or minutes (m/g). The baselines include solvers such as the random greedy algorithm (GREEDY) (Angelini & Ricci- Tersenghi, (019)), CRA-GNN (Ichikawa 2023). SA.
Methods that failed produce results on VI00 GPU are marked N/A.
Method
RRG (d 20)
RRG (d 100)
# nodes
104
10a
106
104
10.
105
0.715
0.717
0.717
0.666
0.667
0.664
GREEDY
(0.06s/g)
(9.76s/g)
(18.96m/g)
(0.02s/g)
(3.51s/g)
(5.16m/g)
0.922
0.911
CRA-GNN
N/A
N/A
N/A
N/A
(3.483m/g)
(4.26m/g)
0.949
0.840
0.296
0.894
0.719
0.190
SA
fewer
(3.00m/g)
(3.00m/g)
(3.00m/g)
(3.00m/g)
(3.00m/g)
(3.00m/g)
0.971
0.943
0.695
0.926
0.887
0.194
more
(30.00m/g)
(30.00m/g)
(30.00m/g)
(30.00m/g)
(30.00m/g)
(30.00m/g)
0.874
0.820
0.709
0.841
0.781
0.660
iSCO
fewer
(2.06s/g)
(3.75s/g)
(39.06s/g)
(2.04s/g)
(10.62s/g)
(1.36m/g)
0.956
0.923
0.895
0.916
0.884
0.850
more
(11.11s/g)
(25.73s/g)
(6.27m/g)
(11.52s/g)
(1.60m/g)
(13.99m/g)
0.967
0.971
0.971
0,946
0.955
0.956
fewer
POQA
(1.32s/g)
(1.35s/g)
(5.59s/g)
(1.34s/g)
(2.36s/g)
(18.47s/g)
0.976
0.980
0.980
0.957
0.966
0.966
(3.77s/g)
(5.82s/g)
(47.99s/g)
(3.70s/g)
(15.69s/g)
(2.94m/g)
the solution quality and runtime results across five different graphs generated with different random seeds. The results indicate that QQA performs well in these complex and large-scale instances. Notably, the instance size increases, the performance gap between QQA and other methods grows, emphasizing the superior scalability for large-scale problems, which is a primary focus of heuristic approaches.
7

---

Published as a conference paper at ICLR 2025
Table 3: ApR and runtime are evaluated benchmarks. Runtime is reported as the total clock time per instance in seconds (s/g) or minutes (m/g).
Method
Twitter
RBttst
EPM (Karalias & Loukas
2020)
0.924 0.133 (0.17s/g)
0.788 0.065 (0.23s/g)
AFF Wang al. 2022)
0.926 + 0.113 (0.17s/g)
0.787 + 0.065 (0.33s/g)
RUN-CSP [Toenshoff et al. 2021
0,987 + 0.063 (0.39s/g)
0.789 + 0.053 (0,47s/g)
iScO
(Sun et 20236
1.000
0.000 (1.67s/g)
0.857 0.062 (1.67s/g)
PQQA (Ours)
1.000 + 0.000 (0.53s//)
0.868 + 0.061 (1.51s/g)
Approximation ratio
1.02
POGA
Approximation ratio
1.02
1500
LAG_U
LAG_U
1.00
64.75 128-150 256.300 512-6001024-1100
16:20
32:40
64:75
128-150 612-60010244110
nodes in trainnttett graphs
# nodes in trainytest graphs
Figure Approximation ratio comparison across different node sizes train/test graphs.
5.2
MAX CLIQUE
Following Sun et al. (2023b), we present results on max clique benchmarks. We use the same instances from Karalias & Loukas (020) and Wang & Li (023), reporting the ApRs on synthetic graphs generated using the RB model (Xu et al. (007) and a real-world Twitter graph (Jure 2014). Table shows the results of PQQA, which was run with 3,0000 steps and 1,000 parallel runs each instance, compared to other learning- baased methods trained on graphs from the same distribution. PQQA achieves significantly better solution quality while requiring only minimal increase in runtime, considering that PQQA is executed without any prior training. Moreover, PQQA demonstrates better speed-quale pueed-qullity tradeoffs than iSCO.
5.3
MAX CUT
We conduct max cut experiments following the same setup in Sun ct al. (2023b); Dai et al. (202T). where the benchmarks include ran- dom graphs and corresponding solutions obtained by running Gurobi for hour. Specifically, the benchmarks includes both ERGs and Barabási-Albert (BA) graphs, with sizes ranging from 16 1,100 nodes and up to 91, 1,299 edges. PQQA was run with 1,000 parallel pro- cesses and 30,000 steps for each instance. We report ApRs against the solutions provided by Gurobi and compare against the LAG (Dai et al. 202T) with either supervised learning-bast -ased approach (Li al. 2018) denoted as LAG or unsupervised learning-based approach (Karalias
Table 4: Maxcut results on Optsicom.
Method
ApR1
SDP
0.526
Approx
0.780
S2V-DQN
0.978
iSCO
1.000
PQQA
1.000
& Loukas 2020) denoted as LAG-U, and classical approach like semidefinite programming and approximated heuristics. Figure shows that PQQA achieves optimal solutions in most cases and significantly outperforms Gurobi on large instances. PQQA performs comparably to iSCO. We also test PQQA on realistic instances (Khalil al. 2017) which includes 10 graphs from the Optsicom project where edge weights are in 11 Table 4 shows the results show that PQQA can achieve the optimal solution in 1,000 steps, with runtime of less than 5 second.
5.4 BALANCED GRAPH PARTITION
We next demonstrate the results of applying PQQA to general discrete variables, using the general- ization of entropy detailed in Appendix Following Sun et al. (2023b); Nazi et al. (2019). PQQA is evaluated balanced graph partition, including five different computation graphs from widely used deep neural networks. The largest graph, Inceptionv3 (Szegedy et al.) 2017). consists of 27,144 nodes and 40,875 edges. The results compared with iSCO, GAP Nazi et al. 2019), which is
8

---

Published as a conference paper at ICLR 2025
Table 5: Balanceness Graph partition evaluated 5 benchmarks.
Metric
Methods
VGG
MNIST-conv
ResNet
AlexNet
Inception-v3
hMETIS
0.05
0.05
0.04
0.05
0.04
GAP
0.04
0.05
0.04
0.04
0.04
Edge cut ratio..
iSCO
0.05
0.04
0.05
0.05
0.05
PQQA
0.04
0.04
0.03
0.04
0.03
MMETIS
0.99
0.99
0.99
0.99
0.99
GAP
0.99
0.99
0.99
0.99
0.99
Balanceness
iSCO
0.99
0.99
0.99
0.99
0.99
PQQA
0.99
0.99
0.99
0.99
0.99
Table 6: Numerical results for COLOR graphs [Trikk] 2002) are presented. For a specified number of
colors, report the cost, defined as the number of conflicts in the best coloring obtained by PQQA, PI-GCV, PI-SAGE (learning-base methods), and Tabucol (a tabu search-base method), sourced
from Schuetz et al. (2022b); Yang et al. (2021)
Graph
Colors
Tabucol
GNN
PI-GCN
PI-SAGE
PQQA
anna
11
1
0
jean
10
0
0
myciel5
6
0
0
0
0
myciel6
7
0
0
queen5-5
5
0
0
queen6-6
7
4
0
queen7-7
15
0
queen8-8
9
0
7
6
1
queen9-9
10
13
queen8-13 12
12
0
7
10
0
queen
11
20
33
17
queen13-13
13
35
40
61
26
14
specialized learning architecture for graph partitioning, and bMETIS (Karypis & Kumar 1999) widely used framework for this problem. We use the edge cut ratio and balanceness for evaluation metrics, where lower edge cut ratio indicates better performance, while higher balanceness is preferable. Further details on these metries and specific experimental conditions are provided in Appendix D.I. [S that PQQA achieves better results with near-perfect balanceness and lower cut ratio. Although PQQA required approximately 20 minutes for the largest graph, GAP, the fastest method, was completed in around minutes. However, PQQA consistently achieved lower edge cut ratio than GAP. Furthermore, with iSCO taking approximately 30 minutes to run, PQQA stands out the faster approach, while still achieving better edge cut ratio.
5.5 GRAPH COLORING
We evaluate PQQA the graph coloring problem. Fol- lowing the experimental setup of |Schuetz et al. (002b),
Size of Independent Set
350
report the results the publicly available COLOR dataset (Trick 2002), commonly used in graph-based benchmark studies. For more detail on the dataset prop- erties and specific experimental conditions, refer to Ap- pendix D.I The evaluation metric the cost, representing the number of conflicts in the best coloring solution. We compare PQQA against PI-GCV and PI-SAGE (Schuetz) et al. 2022b), both seneral-purpose unsupervised learn- ing based solvers, and Tabucol (Yang et al.) 2021), ) a tabu search-base based heuristic that performs local search within tabu list. As shown in Table shows that PQQA achive the best results.
230
200
Steps
Figure Comparison of SA and single- run QQA (S 1).

---

Published as a conference paper at ICLR 2025
400
Sepen Repre 1P
Size of indeparders Set
500
-10
Indeperndee
220
-1-
-10
15
Steps
Steps
Steps
Figure 3: Ablation study on (left) annealing schedule speed, (middle) initial 7, and (right) communi-
cation strength a. The shaded area denotes the standard deviation across five random seeds.
5.6 ABLATION STUDY
Detail Comparison with SA. We compare our method to classical SA with Gibbs sampling. Figure 2 shows the ApR curves for an MIS on the largest ERGs in Section 5.1 as function of the number of sampling steps. The results are reported the mean and standard deviation across five random seeds. This experiment excluded communication between parallel runs to isolate the impact of gradient-based transitions, i.e., 1. The results demonstrate that QQA achieves a speedup of over 10 times in the number of steps. Moreover, using gradient information improves the stability of the solution process.
Schedule Speed and Initial ?. We conduct an ablation study to evaluate the impact of different schedules and initial values, To. As SA, QQA with a smaller initial value To and slower annealing achieves better results. Thus, we examine how the solution quality varies across different parameter settings. For the MIS on the largest ER graph in Section 5.1 3 shows the independent set size across various annealing speeds, with the initial to fixed at 2. The annealing follows linear schedule determined by maximum number steps, where fewer steps correspond faster annealing. The results show no performance degradation, even with faster annealing. Indeed, QQA with 1 steps maintains an ApR around 1.00, outperforming other learning-bait based solvers. Figure/ (middle) shows the results for different % values under the annealing speed, indicating that skipping the annealing phase when < 0 results in poor outcomes. Furthermore, the results are consistent when " is set below- 22
important contribution of this study the introduction of commu- nication between parallel chains, which was not discussed in iSCO (Sun et al.) (023b). Here, we conduct an ablation study on the communication strength, a in Eq. (3.3). The number parallel chains is set to S 1,000, and the performance is evaluated on the MIS on small ERGs, as described in Section 5.1 across various a values. Figure shows the existence of the optimal a values, leading to the best ApR. Additionally, increasing enhances convergence speed while maintaining perfor- mance comparable to the case of a = O. This improvement arises from the effect of the STD term in Eq. (3.3). which implicitly drives the relaxed variables toward 0 or 1. Additional theoretical insights are detailed in Appendix A.2
Communication Strength.
6 CONCLUSION
PQQA, which integrates QQA, gradient-based based updates, and parallel run communication. demonstrates performance comparable to or superior to iSCO and learning- based solvers across various CO problems. Notably, for larger problems, PQQA achieves superior speed-quality trade-off. This suggests that future research on learning- based methods should carefully evaluate their efficiency compared GPU-based, general-pun perrpoe- approach. Future work includes extending PQQA to the mixed-integer optimization and sampling tasks.
Limitation. Both sampling-based solvers, such as PQQA, iSCO, and SA, and UL-based solvers employ the penalty method in Eq. (2) to transform constrained CO problems into unconstrained ones. However, when even finding single fcasible solution is challenging, the formulation in Eq. (2) may fail to produce one. To alleviate this limitation, PQQA leverages large-scale parallel processing on GPUs to solve multiple instances with varying À values simultaneously.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We would like to thank Kai Nakaishi for valuable discussions. We also appreciate constructive feedback from anonymous reviewers and meta-reviewers. This work was supported by Fujitsu Limited. Additionally, YI was supported by the WINGS- program at the University of Tokyo.
REFERENCES
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. In International conference on machine learning, pp. 134-144. PMLR, 2020.
Bahram Alidaee, Gary A Kochenberger, and Ahmad Ahmadian. 0-1 quadratic programming approach for optimum solutions two scheduling problems. International Journal of Systems Science, 25 (2):401-408, 1994.
Maria Chiara Angelini and Federico Ricci- Terrenhersn Monte carlo algorithms are very effective in finding the largest independent set in sparse random graphs. Physical Review E, 100(1):013302, 2019.
Maria Chiara Angelini and Federico Ricci-Tersenghi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29 2023.
Jean Barbier, Florent Krzakala, Lenka Zdeborová, and Pan Zhang. The hard-core model on ran- dom graphs revisited. In Journal of Physics: Conference Series, volume 473, pp. 012021. IOP Publishing, 2013.
Mohsen Bayati, David Gamarnik, and Prasad Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 105-114, 2010.
Maximilian Böther, Otto KiBig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning tree search for combinatorial optimization. arXiv preprint arXiv:2201. 104994 2022.
Vladimír Cemyy Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45:41-51, 1985.
Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
Yuan-Lin Chen and YL Ke. Multi-objective var planning for large-scale power systems using projection-based two-layer simulated annealing algorithms. IEE Proceedings-Gennrattin,, Trans- mission and Distribution, 151(4):555-55) 2004.
Amin Coja-Oghlan and Charilaos Efthymiou. On independent sets random graphs. Random Structures & Algorithms, 47(3):436 486, 2015.
Yves Crama. Combinatorial optimization models for production scheduling in automated manufac- turing systems. European Journal of Operational Research, 99(1):136-153, 1997.
Hanjun Dai, Xinshi Chen, Yu Li, Xin Gao, and Le Song. A framework for differentiable discovery of graph algorithms. 2021.
Michel Deza and Monique Laurent. Applications of cut polyhedra -i. Journal of Computational and Applied Mathematics, 55(2):217-247, 1994.
Vu Dinh, Arman Bilge. Cheng Zhang, and Frederick A Matsen IV. Probabilistic path hamiltonian monte carlo. In International Conference on Machine Learning, pp. 1009-1018. PMLR, 2017.
David Earl and Michael W Deem. Parallel tempering: Theory, applications, and new perspectives. Physical Chemistry Chemical Physics, 7(23):9100-3116, 2005.
11

---

Published as a conference paper at ICLR 2025
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6): 721-741, 1984.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Grathwohl, Dale Schuurmans, and Hanjun Dai. Discs: A benchmark for discrete sampling. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 79035-79066. Curran Associates, Inc., 2023. sttps://proceediiggee httpsr//pooeeiings.eeeiiss..s wttp:riip.ccccaaaaoaaaeaaeeoaaae http:/ppppprreeeaaaaaaaeeepepeee E9ad8 a Datat-ataatt-s and Benchmarks
URL
pdf
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris Maddison. Oops took gradient: Scalable sampling for discrete distributions. In International Conference Machine Learning, pp. 3831-3841. PMLR, 2021.
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neurul information processing systems, 33: 18087-18097, 2020.
W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. 1970.
Demian Hespe, Christian Schulz, and Darren Strash. Scalable kernelization for maximum independent sets. Journal of Experimental Algorithmics (JEA), 24:1-22, 2019.
Holger H Hoos and Thomas Stützle. Satlib: An online resource for research on sat. Sat, 2000: 283-292, 2000.
Koji Hukushima and Koji Nemoto. Exchange monte carlo method and application to spin glass simulations. Journal of the Physical Society of Japan, (5(6):1604411) 1996.
Yuma Ichikawa. Controlling continuous relaxation for combinatorial optimization. arXiv preprint arXiv:2309. 16965, 2023.
Yuma Ichikawa and Hiroaki Iwashita. Continuous tensor relaxation for finding diverse solutions in combinatorial optimization problems. arXiv preprint arXiv:2402.02/90 2024.
David S Johnson, Cecilia R Aragon, Lyle McGeoch, and Catherine Schevon. Optimization by simulated annealing: An experimental evaluation; part i, graph partitioning. Operations research, 37(6):865-89)) 1989.
David S Johnson, Cecilia R Aragon, Lyle McGeoch, and Catherine Schevon. Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations research, 39(3):378-445 1991.
Leskovec Jure. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from httt:://smap. stanford. edu/data, 2014.
W-S Jwo, C-W Liu, C-C Liu, and Y-T Hsiao. Hybrid expert system and simulated annealing approach to optimal reactive power planning. IEE Secreeding--Genertiiin Transmission and Distribution, 142(4):381-385, 1995.
Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58(5:5355 1998.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659 6679, 2020.
Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
12

---

Published as a conference paper at ICLR 2025
George Karypis and Vipin Kumar. Multilevel k-way hypergraph partitioning. In Proceedings the 36th annual ACM/IEEE design automation conference, pp. 343-348, 1999.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671 16600, 1983.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn to solve routing problems! arXiv preprint 1rXiv:1803.06:
2018.
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop algorithm engineering and experiments (ALENEX), pp. 138-150. SIAM, 2016.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances neural information processing systems, 31, 2018.
Iyy Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 1166):108711092, 1953.
Hadi Mohasel Afshar and Justin Domke. Reflection, refraction, and hamiltonian monte carlo. Advances in neural information processing systems, 28, 2015.
Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. arXiv preprint arXiv:1903.006 2019.
Radford M Neal. Sampling from multimodal distributions using tempered transitions. Statistics and computing, 6:353-366, 1996.
Hartmut Neven, Geordie Rose, and William G Macready. Image recognition with an adiabatic quantum computer mapping to quadratic unconstrained binary optimization. arXiv preprint arXiv:0804.4457, 2008.
Akihiko Nishimura, David B Dunson, and Jianfeng Lu. Discontinuous hamiltonian monte carlo for discrete parameters and discontinuous likelihoods. Biometrika, 107(2):365338) -3006, 2020.
Ari Pakman and Liam Paninski. Auxiliary-variable exact hamiltonian monte carlo samplers for binary distributions. Advances in neural information processing systems, 26, 2013.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and
complexity. Courier Corporation, 1998.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial
optimization problems. In Advances in Neural Information Processing Systems 35, 2022.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022a.
Martin JA Schuetz, J Kyle Brubaker, Zhihuai Zhu, and Helmut G Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4(4):043131, 2022b.
Martin JA Schuetz, Kyle Brubaker, and Helmut G Katzgraber. Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):22-34, 2023.
Serap Ulusam Seçkiner and Mustafa Kurt. A simulated annealing approach to the solution of job rotation scheduling problems. Applied Mathematics and Computation, 188(1):31-44 2007.
13

---

Published as a conference paper at ICLR 2025
Haoran Sun, Hanjun Dai, Wei Xia, and Arun Ramamurthy. Path auxiliary proposal for meme in discrete space. In International Conference on Learning Representations, 2021.
Haoran Sun, Etash K Guha, and Hanjun Dai. Annealed training for combinatorial optimization on graphs. arXiv preprint arXiv:2207.11542 2022.
Haoran Sun, Hanjun Dai, Dai, Haomin Zhou, and Dale Schuurmans. Discrete langevin samplers via wasserstein gradient flow. In International Conference on Artificial Intelligence and Statistics, pp. 1290-6313. PMLR, 2023a.
Haoran Sun, Katayoon Goshvadi, Azade Nova, Dale Schuurmans, and Hanjun Dai. Revisiting sampling for combinatorial optimization. In International Conference Machine Learning, pp- 038794 PMLR, 2023b.
Christian Szegedy, Sergey Ioffe. Vincent Vanhoucke, and Alexander Alemi. Inception-v4, inception- resnet and the impact of residual connections on learning. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Reza Tavakkoli-Moghaddaan Nima Safaei, MMO Kah, and Masoud Rabbani. A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing. Journal of the Franklin Institute, 344(5):406 404-54540-42552-2 2007.
Jonathan M Thompson and Kathryn A Dowsland. A robust simulated annealing based examination timetabling system. Computers & Operations Research, 25(7-8):637-6488 1998.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Graph neural networks for maximum constraint satisfaction. Frontiers artificial intelligence, 3:580607, 2021.
M. Trick. COLOR Dataset, 2002. URL https: /ttp:///aat.t.. http://atttttpppeeeee/e cmu www. Ac- cessed: 2024-09-27.
Alex Van Breedam. Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, 86(3):480-490, 1995.
Chiaming Wang, Jeffrey D Hyman, Allon Percus, and Russel Caflisch. Parallel tempering for the traveling salesman problem. International Journal of Modern Physics C, 20(04):539-556 2009.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta-learning. arXiv preprint arXiv:2301.03) 16, 2023.
Haoyu Peter Wang, Nan Wu, Hang Yang, Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. Advances in Neural Information 2022.
Processing Systems, 35:3
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial intelligence, (81(8))):514-533 2007.
Han Yang, Kaili Ma, and James Cheng. Rethinking graph regularization for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4573-4581, 2021.
Ruqi Zhang, Xingchao Liu, and Qiang Liu. A langevin-like sampler for discrete distributions. In International Conference Machine Learning, pp. 26375-26396. PMLR, 2022.
Yichuan Zhang. Zoubin Ghahramani, Amos J Storkey, and Charles Sutton. Continuous relaxations for discrete hamiltonian monte carlo. Advances in Neural Information Processing Systems, 25, 2012.
14

---

Published as a conference paper at ICLR 2025
A DERIVATION AND ADDITIONAL THEORETICAL RESULTS
A.1 DERIVATION OF THEOREM
In this section, we present the proof of Theorem 3.1
Theorem A.1. Under the assumption that the objective function i(: O) is bounded within the domain [0, 11 the Boltzmann distribution lim limm P(o(w):; 7, converges to uniform
distribution over the optimal solutions of Eq. (2). i.e, x² argmin ((x; C, A). Additionally,
lim, lim, lo ((a(w); T) converges to a single-peake distribution II ó(o(w:;) -/2).
Proof. We begin by recalling the definition of P(a(w))7,T)
e- Fr(o(w):CAn)) Z(7,T) /
P(o(w)) T) = Z(,,
II dw.e )
where f(a(w);; C, X, 7) is defined as
f(o(w); A, ((o(w); A) +
where v R and (w)) is convex function that takes its minimum value of 0 when (ww) {0, 1) and maximum value when (w)) 1w/2. The set of global minimizers of ((o(ww;; C, (,
is defined as:
2 argmin w 2)
The remainder of the state space is denoted by Ω = RN 2z In the limit as T + +0, the following holds:
c++(O(())GA))
lim P(o(w):n,T) T-40
/T du.e (Ro())))))))))
(
Jim
T-+0
JII dune (oteHtooooo))CCCnnnon
T-++0 ditee 8(w w²)
lim
(Hoolto)CCCA)--ooooonnA 8(w - w
+ lim
1 1-+0
lim dwss Ewreny 8(w - wx)
5(w - w
T-++
5(w w²),
12
where w² E 22; and á Pty Here, we applied the property that limm- e/r = when = 0, and limm-+40 e/r 0 when < 0. Therefore, in the limit as T' +0, the distribution P(a(w); 7, converges to uniform distribution over the set of global minimizers 22 of Eq. (A.I). Given that s(a(w)) ) is convex function with minimum value O when (ww) E 10, and maximum value 1/2, the limit as 7 > +00, the entropy term ((a(w)) becomes dominant. Consequently, the state space is constrained to the set (w) E {0, 1] where s(a(w)) = 0. Minimizing ((a (w);C, A) within this constrained space yields:
lim 2 argminaggo..) C)
7+000
Thus, in the limit as 7 -> co followed by T +0, P(a T) converges to uniform distribution over the set of global minimizers of the discrete objective function 1(x; C, A). Conversely, as 7 - -0, the entropy s(a(w)) reaches its maximum value when aww) 1w/2, leading to the minimization of f(w; C, X, 7) at Oi, [Lw/2]. Hence, we have:
N
lim lim P(a(w)),, T
II 8(o(ws) - 1/2).
This concludes the proof.
15

---

Published as a conference paper at ICLR 2025
A.2 ADDITIONAL THEORETICAL RESULTS
The following proposition holds for the communication term in Eq. (3.3)
Proposition A.2. The function Σ STD [{o ) is maximized when, for any E [N], the set {a ) ) consists of $/2 zeros and $/2 ones.
Proof. Consider the expression () which can be expanded as:
N
e (ww
2
STD((o(u!
Σ
Σ
1 S ==1
Σ ou)
:=1
Thus, it suffices to solve the following maximization problem for any i E [NT:
((w(())
8 (w)) (1))
2
max Σ
- Σ
o
This problem can be addressed using the method of Lagrange multipliers. Given that (w) [0, 1I we define the Lagrangian as:
(((o(w))),, Aoy vo Ae vo)
Σ ((w()))
1
Σ
8
aw!
s'=1
x + vs vv (1)()_(wu)))
where A₂ and Us are the Lagrange multipliers corresponding to the constraints S )w)(")) < The stationarity condition gives:
@C(1a(w;)) ( Xa; vol = (((((())
Σ
(w:
(1-5) 5
oo(w!)))
5 s'=1
Σ
a(w(")
Σ
a(w(()))
X +
S
5
tts
s'=1
= a(w(())
Σ almu
A + Vs =0
S s'=1
From dual feasibility, A 2 0 and V. 2 for any [S]. Moreover, complementary slackness implies NNo (xo(1(()) (0(())) = 0 and v. (a - 1) = 0 for any E [S]. Considering the case where aw) (1) = 0, A₂ due to complementary slackness, and hence (w!"") = O. On the other hand, if aww (e)) 1, then v. > 0, again due to complementary slackness, which forces aw) = 1. For the intermediate case where < (w)()) < 1, both X and V must be zero, implying that alu(")) Σ. "r(("") This means that all ( equal, leading to the variance being minimized to zero. To achieve the maximum variance, consider the scenario where K out of S
variables set to 0 and the remaining as:
K variables set 1. The variance then computed
aw
(0))
1
Σ
S
(1o(1))
K (0
K 2 + S-K K (1 K 2
5
S
K(S K)
S
To maximize this quadratic function, differentiate with respect to K:
d
K(S
K)
S 2K
dK
82
52
16

---

Published as a conference paper at ICLR 2025
Setting this derivative zero yields K S/2. For even S, the maximum variance is:
( K)
( 1
5
5 4'
For odd S, is either [5/2] or [5/2]. In both cases, the maximum variance is:
I (S- - 1)
S
452
48
As S increases, the variance approaches 1/4, consistent with the even case.
This result suggests that the communication term also favors binary values for (ww) {0, 1).. Indeed, as shown in the ablation study in Figure increasing the strength of the communication term a accelerates convergence. This may be due to the communication term further reinforcing binary variables, in addition the entropy term.
B GENERALIZATION TO DISCRETE OPTIMIZATION PROBLEMS
In this section, we generalize PQQA, defined for binary optimization, to a general discrete optimiza- tion problem. Specifically, we consider the following optimization problem:
min #c @I....... KYM
[x:;; C, A),
where C' represents the characteristic parameters of the problem, and denotes the penalty coefficients. In this case, each discrete variable is relaxed output probabilities for each discrete value, denoted a (W), where W E RNN and the function satisfies Σ oWix) for all E [N]. with the softmax function being typical choice for a. We then introduce an entropy term as follows:
min [(o(WW; C, (W)))
W WERNXK
where ar (W) takes its maximum value of 1/K for all i E [N] and l E [K], and for all i E [M], there exists such that (Wax) and (WW,)) 0 for all k E [K] \ (k). For example, we can consider the following entropy, which generalizes the a-entropy:
K
(x(((w)) Σ
Σ (Ko
- 1)a E (2n n E N].
(K- 1)a +1)
where 7 E IR is penalty parameter. This entropy has the following properties: Proposition B.1. The entropy defined in Eq. (B) is equivalent with Eq. (3.2) when K = 2.
Proof. When K 2, Eq. B can be written as
1 (W.)) - 1 - (20 - 1)a -1)=)
22 (2(o
= 1-
From the properties a, for any E [N], we have a (Wa)) =1 =1 o(W2) Using this relationship. we can rewrite the expression as follows:
N
1+ (-1)a
$2 (fo(W.)))
Σ
(2o(Wa)) -
2
1=1
Finally, by noting that E {2n s(a(w)).
N) and redefining (Wa) obtain s2(o(w))
Next, we generalize the following general discrete optimization problem:
min ((:; C,
where = (k RKK When applying PQQA to this problem, use one-hot encoding to express the probability of a occurring for each i E [M] as (W,)). and relax the discrete variable I; F; o. To encode this with one-hot encoding, also employ the entropy sx sx(o (o(W)) in Eq. B Moreover, PQQA can generalized to mixed-integer optimization problems by adding the entropy term only to the integer variables.
17

---

Published as a conference paper at ICLR 2025
C ADDITIONAL IMPLEMENTATION DETAILS
C.I REASONS FOR NOT USING THE SIGMOID FUNCTION
We provide an intuitive explanation for avoiding the of the sigmoid function, a(x) 1/ (1) when mapping w to the range [0, 1]. Given the characteristics of the sigmoid function, w tends to take on extremely large positive small negative values when a (ww) is almost binary value. This makes challenging for gradient-based methods to transition from very large positive values to very small negative values and vice versa once the variable approaches discrete values. Indeed, experimental results indicate that the sigmoid function performs less effectively than the clamp function. Further exploration of transformations tailored for CO beyond the clamp function remains for future research.
C.2 ANNEALING SCHEDULE
We linearly increase y from Tiin Mmxx over the total steps. In general, set Ymin - and Tmax = 0.1. For the Max Cut problem, 7 = 20 was used for larger graphs, while "/mnn = -5 was applied for the remaining graphs.
C.3 CONHIGURATION OPTIMIZER
The learning rate was set to appropriate value from 0100,, depending the specific problem. The weight decay was fixed at 0.01 and the temperature was fixed as 7 0.001.
C.4 TRANSFORMATION FOR GENERAL DISCRETE VARIABLES
For discrete variables, each row E [N] of the updated matrix W RRN is transformed follows:
(W.n) Clamp(Wss)
Wk E [K].
LK=1 Clamp(Ww))
D ADDITIONAL EXPERIMENT DETAILS
D.1 ENERGY FUNCTION OF BENCHMARK PROBLEMS
In this section we provide the actual energy function we used for each of the problems we exper- imented in the main paper. For a graph G (V, E) label the nodes in V from N. The adjacency matrix is represented as A. For a weighted graph we simply let A. denote the edge weight between node and j. For constraint problems, coefficient as the minimum value of À such that xx argmin (0.1) [ [ar; X, C) is achieved at xr satisfying the original constraints. Such a choice of the coefficient guarantees the target distribution converges to the optimal solution of the original CO problems while keeping the target distribution as smooth as possible.
follow [Sun al. (2022) to select penalty
Max Independent Set. The MIS problem is fundamental NP-hard problem (Karp) 2010) defined as follows. Given an undirected graph GVV E), an independent set (IS) is a subset of nodes I E V where any two nodes in the are not adjacent. The MIS problem attempts find the largest IS, which is denoted Z*. In this study, denotes the IS density, where = [Z|/ J. To formulate the problem, binary variable æ; is assigned to each node i V. Then the MIS problem is formulated as follows:
Ca s.t. Zæ 0, v(i.j) E E.
(0,1)
We use the corresponding energy function in the following quadratic form:
x Ax
1(: A. c x
2
where the first term attempts to maximize the number of nodes assigned 1, and the second term penalizes the adjacent nodes marked according the penalty parameter X. In experiments
18

---

Published as a conference paper at ICLR 2025
IN and use À 2. First, for every d, a specific value P7. which is dependent only the degree d, exists such that the independent set density [/V] converges to Pa with a high probability as N approaches infinity (Bayati et al.] 2010). Second, statistical mechanical analysis provides the typical MIS density Pa
Theory and clarify that for d 16, the solution space of Z undergoes clustering transition, which is associated with hardness in sampling (Barbier et al. 2013) because the clustering is likely to create relevant barriers that affect any algorithm searching for the MIS I". Finally, the hardness is supported by analytical results in a large d limit, which indicates that, while the maximum independent set density is known to have density P 2 log(d) dd/ d, to the best of our knowledge, there is no known algorithm that can find an independent set density exceeding
Pd-+x
aig
log(d)/d Coja-Oghlan & Efthymiou 2015).
Max Clique. The max clique problem is equivalent to MIS on the dual graph. The max clique the integer programming formulation
min We (U,1)
Caai s.t. = = 0, v(i,j) & E.
The energy function is expressed as
((:; A, = cxx A [1]a(1]0 1) xx= Axx)x,
where v denotes the vector 1,)...,,)TTT IRN, In our experiments c 1y and we use À 2.
Max Cut. The MaxCut problem is also fundamental NP-hard problem Karp 2010 with practical
application in machine scheduling (Alidaee al.) 1994). ). image recognition (Neven et al. 2008
and electronic circuit layout design (ezaa & Laurent 1994). Given an graph G' == (V. E), cut set
E E defined as subset of the edge set between the node sets dividing (Vi, V/2 Vi 1/2 = V, V/ = 0). The MaxCut problems aim to find the maximum cut set, denoted C*, Here, the cut ratio is defined as v = [C)/DV/. where [C] is the cardinality the cut set. To formulate this problem, each node is assigned binary variable, where 2, indicates that node belongs to V1, and 2; 0 indicates that the node belongs to Vz. Here, 2; Ij 2x,0, = holds if the edge (i.j) E C. As result, we obtain the following:
1 (2x; - 1)((2n - -1)
min 1E(0,1
Aij (L)))E
Σ
2
Due to constraints this problem, the energy function be expressed as
1 (1-(2r;
(2x; - 1)(2r, - 11
I(:; A)
Σ Aij
2
(U)E
Balanced Graph Partition.
The balanced graph partition is formulated follows:
N I(x; = 8)
2
min #6 2E........k.
Σ
[ # 2,,:81(1; = s||æ,, = s)]
d
k
#=1 (L,))E
1=1
where & is the number of partitions. The goal of graph partitioning is achieve balanced partitions while minimizing the edge cut. The quality of the resulting partitions is assessed using the following metrics: (1) Edge cut ratio, defined as the ratio of edges across partitions to the total number of edges, and (2) Balancedness, calculated as one minus the difference between the number of nodes in each partition and the ideal partition size as follows:
2
Balanceness -
Σ s=1
si
I1(2;; = 5)
k
N
19

---

Published as a conference paper at ICLR 2025
Table 7: Synthetic data statistics.
MIS
max clique
maxcut
Name
ER-[700-800]
ER-19000-11000)
RB
ER
BA
# max nodes
800
10,915
475
1,100
1,100
# max edges
47,885
1,190,799
90,585
91,239
4,384
# instances
128
500
1,000
1,000
Table 8: Synthetic data statistics of graph coloring.
Graph # nodes
# edges
colors
anna
138
493
11
jean
80
254
10
myycie15
47
236
6
mycie16
95
755
queen5-5
25
160
5
queen6-6
36
290
queen7-7
49
476
queen8-8
64
728
9
queen9-9
81
1056
10
queen8- 12
96
1368
12
queenI 1-11
121
1980
11
13-13
169
3328
13
Table 9: Real-world data statisties.
MIS
Max Clique
Maxeut
Balanced Graph Partition
Name
Satlib
Twitter
Optsicom
Mnist
Vgg
Alexnet
Resnet
Inception
# max nodes
1,347
247
125
414
1,325
798
20,586
27,114
# max edges
5,978
12,174
375
623
2,036
1,198
32,298
40,875
# instances
500
196
10
1
1
1
Graph Coloring,
The graph coloring problem is formulated as follows:
min # $E.0.......K
Σ
[[x, = xz5]
(KJ))E
where K is number of color. Following Schuetz al. (2022b), evaluate several benchmark in- stances from the COLOR dataset (Trick] 2002 for graph coloring. These instances can be categorized as follows:
(1) Book graphs: For a given work of literature, a graph created with each node representing character. Two nodes are connected by an edge if the corresponding characters encounter each other the book.
(2) Myciel graphs: This family of graphs is based on the Mycielski transformation. The Myciel graphs are known be difficult to solve hecause they triangle free (clique number 2) but the coloring number increases in problem size.
(3) Queens graphs: This family of graphs is constructed as follows. Given an by n chessboard, a queens graph a graph made of n² nodes, each corresponding square of the board. Two nodes are then connected by an edge if the corresponding squares are in the same row, column, diagonal. other words, two nodes are adjacent if and only if queens placed on these two nodes can attack each other in single move. In all cases, the maximum clique in the graph is no more than n, and the coloring value lower-bounded by n.
20

---

Published as a conference paper at ICLR 2025
Table 10: ApR (size of independent set) and runtime evaluated three benchmarks provided by DIMES (Qiu et al. 2022). The ApR is assessed relative to the results obtained by KaMIS. Runtime is reported the total clock time, denoted in seconds (s), minutes (m), or hours (h). Methods that fail to produce results within 10 times the time limit of DIMES are marked as N/A.
SATLIB
ER-[700-800 800]
ER-19000-11000
Method
Type
ApR
ApR
ApR
Time
Time
Time
(size)
(size)
(size)
1.000
1.000
1.000
KaMIS
OR
37.58m
52.13m
7.6h
(425.96)
(44.87)
(381.31)
1.000
0.922
Gurobi
OR
26.00m
50.00m
N/A
N/A
(425.95)
(41.38)
0.865
Intel
SL+TS
N/A
N/A
20.00m
N/A
N/A
(38.80)
Li al. 2018
0.988
0.777
0.746
SL+G
23.05m
6.06m
5.02m
(420.66)
(34.86)
(284.63)
0.830
DGL
SL+TS
N/A
N/A
22.71m
N/A
N/A
(37.26)
Böther et al. 2022
0.991
0.918
0.907
LwD
RL+S
18.83
6.33m
7.56m
(422.22)
(41.17)
(345.88)
Ahn et al.
2020)
0.989
0.852
0.841
DIMES
RL+G
24.17m
6.12m
5.21m
(421.24)
(38.24)
(320.50)
Qiu et al.
2022)
0.994
0.937
0.873
RL+S
20.26m
12.01m
12.51m
(423.28)
(42.06)
(332.80)
0.995
0.998
0.990
iSCO (Sun et al. 2023b)
fewer
5,85m
1.38m
9.38m
(423.66)
(44.77)
(377.5)
0.996
1.006
1,008
more
(424.16)
15.27m
(45.15)
5.56m
(384.20)
1.25h
0.993
1.004
1,027
fewer
7.34m
44.72s
5.83m
(423.018)
(44.91)
(391.50)
PQQA (Ours)
0.994
1.005
1.039
more
(423.57)
1.21h
(45.11)
7.10m
(396.06)
58.48m
0.996
1.007
1.033
fewer
1.25h
6.82m
41.26m
(424.06)
(45.20)
(393.94)
0.996
1.009
1.043
more
(424.44)
12.46h
(45.29)
1.14h
(397.75)
6.80h
D.2 BENCHMARK DETAILS
We present additional details our experiments. First, Table Table [ shows the statistics of the synthetic datasets, including the maximum number of nodes and edges per graph and the number of test instances. Table Sable/9pro provides the corresponding statistics for the real-world graphs
E ADDITIONAL RESULTS
E. MIS
In this section, we present additional information in Table including references for each method and the sizes of the maximum independent sets obtained, alongside the MIS results discussed in Table
21


Reviews:
[{"review_id": "I3MLlO6Dau", "reviewer": "Reviewer_ATVW", "summary": "In this study, the authors present PQQA, an optimization approach that integrates QQA, gradient-based updates, and parallel run communication. The results indicate that PQQA performs comparably to or better than iSCO and other learning-based solvers across a range of combinatorial optimization (CO) problems. Notably, for larger problem instances, PQQA offers a superior trade-off between speed and solution quality.", "questions": "1. In Table 1, some of the ApR values are greater than 1. Could the authors clarify what this means?\n\n2.  While the authors mention runtime in the paper, there seems to be a discrepancy that needs further explanation. For example, in Table 1, iSCO takes about 5–15 minutes to achieve an ApR of 0.996, whereas PQQA takes over an hour for the same result. \n\n3.  Line 314 refers to Table 1 as Table 5.1. Please check for similar mistakes in other parts of the paper and ensure that table references are consistent throughout.\n\n4. In line 60, the term \"parameters\" is used. Could the authors clarify what specific parameters are being referred to in this context?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors did a great job explaining the problem being considered, including the background, methodology, theoretical properties, and related work. The numerical experiments also effectively highlight their proposed method. While I did not check the validity of the proof in the Appendix, the setup and results are very convincing.", "weaknesses": "n/a", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LvTjdEgpfh", "reviewer": "Reviewer_CsaC", "summary": "This paper proposes Parallel Quasi-Quantum Annealing (PQQA), a sampling-based algorithm for combinatorial optimization problems.  Specifically, with a continuous relaxation of the combinatorial optimization problem, an entropy metric to measure discreteness and sampling based on the Boltzmann Distribution, the authors develop an efficient general-purpose approach for combinatorial optimization.  Empirically, this approach yields high-quality solutions efficiently.", "questions": "**Questions**\n- How are the binary solutions obtained after running PQQA?  \n- How often are these solutions feasible?  If infeasible, what is done with the solutions?\n- Do the authors have any insight into how the strength of the LP relaxation of a problem affects the downstream solution quality?  \n- Why is iSCO not compared against in Table 2?\n- Why is this method not benchmarked on TSP?\n- Is there a reason iSCO is much faster on Maximum Independent Set but slower on Max Clique?  \n\n**Minor Remarks**\n-  I suggest keeping the evaluation of times consistent, i.e., always use seconds or average time to solve an instance.  Comparing performance is difficult when switching between metrics for different tables and even within tables.  \n-  Incorrect reference in Table E.1 in line 1125.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Novelty.**  Overall, this paper proposes a novel sampling-based approach for finding high-quality solutions to combinatorial optimization problems.  In particular, using $\\alpha$-entropy with the extended Boltzmann Distribution is a well-motivated and novel approach for combinatorial optimization.  \n\n- **Numerical Results.**  The authors provide extensive numerical comparisons on a wide variety of benchmarks.  These results demonstrate the PQQA can compute high-quality solutions on all instances, often at a reduced runtime compared to other methods.", "weaknesses": "Overall, I have quite a favorable opinion of the paper.  However, one significant weakness/limitation is provided below.  \n- **Simple Constraints in Benchmarks.**  The authors evaluate the maximum independent set, max clique, max cut, graph partitioning, and graph coloring.  While these constitute many combinatorial optimization problems, they all have relatively simple constraints compared to problems such as TSP, which has an exponential number of constraints.  Approaches such as iSCO are capable of dealing with this type of structure.  However, it is unclear if something similar can be done with PQAA, given the reliance on continuous relaxation, which may be less tractable for problems with exponentially many constraints.  Overall, this may limit the applicability of such approaches.  Furthermore, the authors do not acknowledge this as a limitation or discuss this at all.  I would be happy to discuss this further in the discussion period.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L7tQBkiUdU", "reviewer": "Reviewer_5JtH", "summary": "The authors proposed a learning based method for CO problems by combing Quasi-Quantum Annealling and gradient-based update\nthrough continuous relaxation. Performance are compared with iSCO on various benchmark problems.", "questions": "The paper is based on the continuous relaxation of the discrete variable. Then why not directly solving the resulting linear programming problem?", "limitations": "", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "parallel implementation on GPUs accelerates the solution process.", "weaknesses": "It seems that the algorithm does not have converence guarantees. \n\nThe algorithm cannot guarantee finding a feasible solution. constraints are moved to the objective function as a penalty term. \n\nOn benchmarks like SATLIB, it performs worse than traditional OR solvers like Gurobi. \n\nThe authors may consider larger benchmarks like MIPLIB 2017 to test the performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ox1u92YDoc", "reviewer": "Reviewer_fcsw", "summary": "The manuscript proposes a new methodology for combinatorial optimization, based on the integration of gradient-based updates and Quasi-Quantum Annealing. The manuscript is well-written using easy-to-comprehend language which led to a joyful read. The background is well-explained including prior work in the field. The computational experiments are well-chosen and comprehensive.", "questions": "- What do time measurements [s/g] really mean when different algorithms are compared? \nWhat is the time spent on? \nAre the time differences purely due to implementation differences? \nHow do the different approaches scale?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is a strong paper. \n- Very good coverage of prior work (While I am not an expert in this field the sheer amount and frequency of citations is convincing)\n- Clear introduction and background\n- The main contribution seems novel\n- The experimental results are very convincing", "weaknesses": "This is a strong paper in my opinion, and I identified only a few shortcomings. \n-  The results of the computational experiments are somewhat confusing. How can time be measured when so many different algorithms are involved? Aren't these codes in different languages? You might be able to give the reader a better intuition of your compute-time measurements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)