pith. sign in

arxiv: 2511.17245 · v3 · submitted 2025-11-21 · ❄️ cond-mat.stat-mech

Simulated Annealing for Quadratic and Higher-Order Unconstrained Integer Optimization

Kohei Suzuki This is my paper

Pith reviewed 2026-05-17 20:40 UTC · model grok-4.3

classification ❄️ cond-mat.stat-mech
keywords simulated annealingquadratic unconstrained integer optimizationhigher-order unconstrained integer optimizationMetropolis methodQUBO conversioncombinatorial optimizationinteger variables
0
0 comments X

The pith

Direct simulated annealing on integer variables outperforms QUBO conversions for quadratic and higher-order problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that simulated annealing can be applied directly to problems with integer-valued variables and higher-order interactions without first converting them into quadratic unconstrained binary optimization forms. Conventional conversions require binary encoding of integers and reduction of higher-order terms, which inflates the number of variables and interactions and creates a computational bottleneck. The direct approach avoids this expansion and introduces an optimal-transition Metropolis update rule that improves efficiency when integer ranges are wide. Numerical tests show the direct method delivers shorter run times and higher-quality solutions than the converted QUBO route. A reader who solves real-world combinatorial problems with natural integer representations would care because the method removes the overhead that has previously limited scale.

Core claim

A direct simulated-annealing framework for quadratic and higher-order unconstrained integer optimization (QUIO and HUIO) problems achieves higher efficiency and better solution quality than the conventional route of converting the same problems into QUBO instances via binary encoding and term reduction.

What carries the argument

Direct SA updates on integer variables combined with the optimal-transition Metropolis method that selects state changes to maintain efficiency across wide variable ranges.

If this is right

  • The number of variables and interactions remains unchanged by the problem formulation instead of growing with binary encoding.
  • For large-scale instances the conversion step itself ceases to dominate runtime.
  • The optimal-transition Metropolis rule provides measurable speed-up precisely when the allowed integer range is wide.
  • Solution quality improves on the tested benchmark set relative to the converted formulation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same direct-update idea could be tested inside other local-search metaheuristics that currently rely on QUBO preprocessing.
  • Problems whose natural variables are integers with moderate but not tiny ranges become newly practical targets for annealing hardware that accepts higher-order or integer couplings.
  • When integer ranges grow very large, the per-sweep cost of the direct method may still need further engineering to stay competitive.

Load-bearing premise

Implementing the direct updates on integer variables and higher-order terms adds no hidden computational costs that cancel the savings from skipping the QUBO conversion.

What would settle it

A timing comparison on a large-scale instance with wide integer ranges in which the direct method's per-update cost exceeds the overhead of the QUBO conversion and produces longer total run times.

Figures

Figures reproduced from arXiv: 2511.17245 by Kohei Suzuki.

Figure 1
Figure 1. Figure 1: (b), only the heat bath method exhibits annealing time (a) (b) 1000 sweeps 100 samples 1000 sweeps 100 samples [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Annealing time as a function of p for (a) E FC p,u=1 (z) and (b) E ML p,u=10(z). Each data point represents the mean annealing time over 100 samples, with 1000 sweeps and N = 100 variables. Error bars indicate the standard error but are too small to be visible. that increases linearly with 2u + 1. Next, we investigate how the exponent p in the monomial z p influences the annealing time [PITH_FULL_IMAGE:fi… view at source ↗
Figure 4
Figure 4. Figure 4: Temperature T dependence of the mean energy for E ML p=30,u=1 (z). Each data point represents the mean energy at temperature T during SA, av￾eraged over 1000 samples, and the number of sweeps is (a) 1000 and (b) 100000. The number of variables is N = 100, and the black dotted line indi￾cates the ground-state energy, −100. ficients, and its characteristics therefore differ from those of the fully connected … view at source ↗
Figure 6
Figure 6. Figure 6: Sweep dependence of the mean energy for (a) E ML p=2,u=106 (z) and (b) E ML p=30,u=1 (z). Each data point represents the mean energy averaged over 1000 samples. Error bars indicate the standard error but are too small to be visible. The number of variables is N = 100 and the black dotted line indicates the ground-state energy, −100. 4.4 Energy as a function of annealing time In this subsection, we examine … view at source ↗
Figure 8
Figure 8. Figure 8: Annealing time dependence of the mean energy obtained by SA with different transition probabilities for (a) E ML p=2,u=106 (z) and (b) E ML p=30,u=1 (z), Each data point represents the mean energy averaged over 1000 samples. Error bars indicate the standard error of both energy and annealing time but are too small to be visible. The number of variables is N = 100 and the black dotted line indicates the gro… view at source ↗
Figure 7
Figure 7. Figure 7: Annealing time dependence of the mean energy for the random in￾teraction model [Eq. (34)] with (a) p = 2, u = 1, (b) p = 2, u = 100, (c) p = 4, u = 1, and (d) p = 4, u = 100. Each data point represents the mean energy averaged over 1000 samples. Error bars indicate the standard error of both energy and annealing time but are too small to be visible. The number of variables is N = 100 and the number of inte… view at source ↗
read the original abstract

Simulated annealing (SA) is a key algorithm for solving combinatorial optimization problems, which model numerous real-world systems. While SA is commonly used to solve quadratic unconstrained binary optimization (QUBO) problems, many practical problems are more naturally formulated using integer variables. We therefore study quadratic and higher-order unconstrained integer optimization (QUIO and HUIO) problems, which generalize QUBO by allowing integer-valued variables and higher-order interactions. Conventional approaches often convert these problems into QUBO formulations through binary encoding and the reduction of higher-order terms. Such conversions, however, greatly increase the number of variables and interactions, resulting in long computation times and, for large-scale problems, even making the conversion itself a dominant computational bottleneck. To overcome this limitation, we propose an efficient framework that directly applies SA to QUIO and HUIO problems without converting them into QUBO. Within this framework, we introduce an optimal-transition Metropolis method, designed to improve efficiency when the variable range is wide, and evaluate its performance alongside the conventional Metropolis and heat bath methods. Numerical experiments demonstrate that the proposed direct approach achieves higher efficiency and better solution quality than the conventional QUBO-based formulation and reveal the practical advantages of the optimal-transition Metropolis method. The algorithm developed in this study is available as part of the open-source library OpenJij, which provides a Python front end with a C++ backend.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript proposes a direct simulated annealing framework for quadratic and higher-order unconstrained integer optimization (QUIO and HUIO) problems that avoids conversion to QUBO formulations. It introduces an optimal-transition Metropolis method for efficiency with wide variable ranges, compares it to standard Metropolis and heat-bath algorithms, and reports numerical experiments claiming superior efficiency and solution quality over QUBO-based approaches. The implementation is released as part of the OpenJij open-source library.

Significance. If the performance advantages hold, the work addresses a practical bottleneck in combinatorial optimization arising from binary encoding overhead, which is relevant to statistical-mechanics models and integer-variable problems in scheduling or resource allocation. The open-source release and the new Metropolis variant support reproducibility and further development.

major comments (1)
  1. [Numerical Experiments] Numerical Experiments section: the central claims of higher efficiency and better solution quality rest on numerical experiments, yet the manuscript provides no visible data details, error bars, or complete methodology for the tested instances and variable ranges. This gap prevents verification that direct SA incurs no hidden per-update costs that offset the avoided QUBO overhead, which is load-bearing for the main conclusion.
minor comments (2)
  1. [Abstract] The abstract introduces the 'optimal-transition Metropolis method' without a one-sentence description of its transition rule; a brief clarification would improve immediate readability.
  2. [Introduction] Ensure that the distinction between QUIO/HUIO and QUBO is illustrated with at least one concrete example problem (e.g., from statistical mechanics) in the introduction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. The single major comment identifies a genuine gap in experimental documentation that we will address in revision.

read point-by-point responses

  1. Referee: Numerical Experiments section: the central claims of higher efficiency and better solution quality rest on numerical experiments, yet the manuscript provides no visible data details, error bars, or complete methodology for the tested instances and variable ranges. This gap prevents verification that direct SA incurs no hidden per-update costs that offset the avoided QUBO overhead, which is load-bearing for the main conclusion.

    Authors: We agree that the current Numerical Experiments section is insufficiently detailed for independent verification. In the revised manuscript we will add: (i) explicit descriptions of all benchmark instances, including exact variable ranges, problem sizes, and interaction orders; (ii) error bars and statistics from at least 20 independent runs per instance; (iii) a complete methodology subsection with pseudocode and parameter settings; and (iv) separate timing breakdowns that isolate per-update computational cost from encoding overhead. These additions will directly demonstrate that the observed speed-ups are not offset by hidden costs in the direct formulation. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic proposal with independent experiments

full rationale

The paper proposes a direct SA framework for QUIO/HUIO problems, introduces an optimal-transition Metropolis method, and supports its claims via numerical experiments comparing efficiency and solution quality against QUBO conversion. No derivation chain, predictions, or first-principles results reduce to inputs by construction. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations are present. The central claims rest on the described algorithms and external benchmarks from experiments, which are independent of the proposal itself. This is a standard self-contained algorithmic paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Central claim rests on standard SA convergence assumptions and the practical efficiency of the new transition method for wide integer ranges.

axioms (1)
  • domain assumption Simulated annealing converges to good solutions under suitable cooling schedules for integer and higher-order problems
    Invoked implicitly as the basis for applying SA directly.
invented entities (1)
  • optimal-transition Metropolis method no independent evidence
    purpose: Improve proposal efficiency when integer variable ranges are wide
    New component introduced to address limitations of standard Metropolis and heat bath methods.

pith-pipeline@v0.9.0 · 5541 in / 1115 out tokens · 34522 ms · 2026-05-17T20:40:53.175081+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages · 1 internal anchor

  1. [1]

    Simulated Annealing for Quadratic and Higher-Order Unconstrained Integer Optimization

    Introduction Combinatorial optimization problems play a central role in a wide range of real-world applications, including finance, lo- gistics, drug discovery, and scheduling. Many of these prob- lems are NP-complete or NP-hard, and obtaining exact so- lutions in polynomial time is generally intractable. 1) There- fore, efficient approximation algorithms...

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  2. [2]

    We begin with the quadratic unconstrained integer optimization

    Model In this section, we introduce the polynomial unconstrained integer optimization, namely QUIO and HUIO. We begin with the quadratic unconstrained integer optimization. QUIO is defined as the problem of minimizing a quadratic function composed of integer variables: Ep=2(z)= X i1 Ji1zi1 + X i1,i2 Ji1,i2zi1zi2 .(1) Here,z=(z 1,z 2, . . . ,zN) is the set...

    work page

  3. [3]

    Section 3.1 outlines the SA procedure itself, in- cluding initialization, cooling schedule, and update rules

    Simulated Annealing In this section, we present the SA framework for general QUIO and HUIO, and describe several techniques to make it efficient. Section 3.1 outlines the SA procedure itself, in- cluding initialization, cooling schedule, and update rules. Sec- tion 3.2 then explains a method for efficiently evaluating the energy difference when a variable...

    work page

  4. [4]

    Results In this section, we present numerical results for SA with the transition probabilities described in Sect. 3.3. Our pro- posed algorithms are implemented in the open-source library OpenJij,36) and are freely available for use. All numerical ex- periments presented below were performed using OpenJij on a machine equipped with an Apple M1 Max process...

    work page

  5. [5]

    Promoting the ap- plication of advanced quantum technology platforms to social issues

    Summary We proposed an SA method for optimizing polynomial functions composed of integer variables, namely the QUIO and HUIO problems. By storing and updating the coefficients required for energy-difference computations, we can evalu- ate the transition probabilities efficiently. We also proposed a method for estimating the initial and final temperatures ...

    work page

  6. [6]

    Lucas: Front

    A. Lucas: Front. Phys.2(2014)

    work page 2014

  7. [7]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi: Science220(1983) 671

    work page 1983

  8. [8]

    ˇCern´y: Journal of Optimization Theory and Applications45(1985) 41

    V . ˇCern´y: Journal of Optimization Theory and Applications45(1985) 41

    work page 1985

  9. [9]

    Kochenberger, J.-K

    G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. L ¨u, H. Wang, and Y . Wang: Journal of Combinatorial Optimization28(2014) 58

    work page 2014

  10. [10]

    Glover, G

    F. Glover, G. Kochenberger, R. Hennig, and Y . Du: Annals of Opera- tions Research314(2022) 141

    work page 2022

  11. [11]

    Karimi and P

    S. Karimi and P. Ronagh: Quantum Information Processing18(2019) 94

    work page 2019

  12. [12]

    Tamura, T

    K. Tamura, T. Shirai, H. Katsura, S. Tanaka, and N. Togawa: IEEE Ac- cess9(2021) 81032

    work page 2021

  13. [13]

    Boros and P

    E. Boros and P. L. Hammer: Discrete Applied Mathematics123(2002) 155

    work page 2002

  14. [14]

    Anthony, E

    M. Anthony, E. Boros, Y . Crama, and A. Gruber: Mathematical Pro- gramming162(2017) 115

    work page 2017

  15. [15]

    Cardoso, R

    M. Cardoso, R. Salcedo, S. de Azevedo, and D. Barbosa: Computers & Chemical Engineering21(1997) 1349

    work page 1997

  16. [16]

    Abramson and M

    D. Abramson and M. Randall: Annals of Operations Research86 (1999) 3

    work page 1999

  17. [17]

    ´Alvaro Rubio-Garc ´ıa, J. J. Garc ´ıa-Ripoll, and D. Porras: arXiv:2210.00807

    work page arXiv

  18. [18]

    P. Tian, H. Wang, and D. Zhang: IFAC Proceedings V olumes28(1995)

    work page 1995

  19. [19]

    7th IFAC Symposium on Large Scale Systems: Theory and Appli- cations 1995, London, UK, 11-13 July, 1995

    work page 1995

  20. [20]

    Metropolis, A

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller: J. Chem. Phys.21(1953) 1087

    work page 1953

  21. [21]

    W. K. Hastings: Biometrika57(1970) 97

    work page 1970

  22. [22]

    Barker: Australian Journal of Physics18(1965) 119

    A. Barker: Australian Journal of Physics18(1965) 119

    work page 1965

  23. [23]

    Geman and D

    S. Geman and D. Geman: IEEE Transactions on Pattern Analysis and Machine IntelligencePAMI-6(1984) 721

    work page 1984

  24. [24]

    Glover, J.-K

    F. Glover, J.-K. Hao, and G. Kochenberger: International Journal of Metaheuristics1(2011) 232

    work page 2011

  25. [25]

    Glover, J.-K

    F. Glover, J.-K. Hao, and G. Kochenberger: International Journal of Metaheuristics1(2011) 317

    work page 2011

  26. [26]

    Couzini ´e, Y

    Y . Couzini ´e, Y . Nishiya, H. Nishi, T. Kosugi, H. Nishimori, and Y .-i. Matsushita: Phys. Rev. A109(2024) 032416

    work page 2024

  27. [27]

    B.-Y . Wang, X. Cui, Q. Zeng, Y . Zhan, M.-H. Yung, and Y . Shi: Com- munications Physics8(2025) 150

    work page 2025

  28. [28]

    Ikeuchi, Y

    K. Ikeuchi, Y . Matsuda, and S. Tanaka: arXiv:2510.24237

    work page arXiv

  29. [29]

    D. P. Bertsekas:Constrained Optimization and Lagrange Multiplier Methods(Academic Press, New York, 1982)

    work page 1982

  30. [30]

    Szu and R

    H. Szu and R. Hartley: Physics Letters A122(1987) 157

    work page 1987

  31. [31]

    Ingber: Control and Cybernetics25(1996) 33

    L. Ingber: Control and Cybernetics25(1996) 33

    work page 1996

  32. [32]

    Nourani and B

    Y . Nourani and B. Andresen: Journal of Physics A: Mathematical and General31(1998) 8373

    work page 1998

  33. [33]

    Cohn and M

    H. Cohn and M. Fielding: SIAM Journal on Optimization9(1999) 779

    work page 1999

  34. [34]

    Mahdi, S

    W. Mahdi, S. A. Medjahed, and M. Ouali: Computaci ´on y Sistemas21 (2017) 493

    work page 2017

  35. [35]

    Devroye:Non-Uniform Random Variate Generation(Springer Sci- ence & Business Media, 1986)

    L. Devroye:Non-Uniform Random Variate Generation(Springer Sci- ence & Business Media, 1986)

    work page 1986

  36. [36]

    Dekkers and E

    A. Dekkers and E. Aarts: Mathematical Programming50(1991) 367

    work page 1991

  37. [37]

    M. M. Ali and C. Storey: Journal of Global Optimization11(1997) 181

    work page 1997

  38. [38]

    M. Ali, A. T ¨orn, and S. Viitanen: Computers & Operations Research29 (2002) 87

    work page 2002

  39. [39]

    Locatelli: inSimulated Annealing Algorithms for Continuous Global Optimization, ed

    M. Locatelli: inSimulated Annealing Algorithms for Continuous Global Optimization, ed. P. M. Pardalos and H. E. Romeijn (Springer US, Boston, MA, 2002), pp. 179–229

    work page 2002

  40. [40]

    S. R. White: AIP Conference Proceedings122(1984) 261

    work page 1984

  41. [41]

    E. E. Aarts and V . Laarhoven: Philips Journal of Research40(1985) 193

    work page 1985

  42. [42]

    Nishimura, Y

    K. Nishimura, Y . Sakamoto, T. Shimizu, K. Suzuki, and Y . Yamashiro. OpenJij. DOI: 10.5281/zenodo.15790495

    work page doi:10.5281/zenodo.15790495

  43. [43]

    Hiromi, S

    I. Hiromi, S. Taro, and T. Toshiki. presented at The 39th Annual Con- ference of the Japanese Society for Artificial Intelligence, 2025

    work page 2025

  44. [44]

    Toshiki, S

    T. Toshiki, S. Taro, and I. Hiromi. presented at The 39th Annual Con- ference of the Japanese Society for Artificial Intelligence, 2025

    work page 2025

  45. [45]

    kinematic fitting

    T. Toshiki, S. Taro, and I. Hiromi. OMMX. DOI: 10.5281/zen- odo.17638431

    work page doi:10.5281/zen-

  46. [46]

    Frigessi, C.-R

    A. Frigessi, C.-R. Hwang, and L. Younes: The Annals of Applied Prob- ability2(1992) 610

    work page 1992

  47. [47]

    J. S. LIU: Biometrika83(1996) 681

    work page 1996

  48. [48]

    Pollet, S

    L. Pollet, S. M. A. Rombouts, K. Van Houcke, and K. Heyde: Phys. Rev. E70(2004) 056705

    work page 2004

  49. [49]

    Suwa and S

    H. Suwa and S. Todo: Phys. Rev. Lett.105(2010) 120603

    work page 2010

  50. [50]

    Chen, W.-K

    T.-L. Chen, W.-K. Chen, C.-R. Hwang, and H.-M. Pai: SIAM Journal on Control and Optimization50(2012) 2743

    work page 2012

  51. [51]

    R. H. Swendsen and J.-S. Wang: Phys. Rev. Lett.58(1987) 86

    work page 1987

  52. [52]

    Wolff: Phys

    U. Wolff: Phys. Rev. Lett.62(1989) 361. 10

    work page 1989