Evaluating the solution performance of the augmented Lagrangian function on Ising machines
Shunsuke Awai 1, Takuro Itoh 1, Keita Takahashi 1, Kotaro Tanahashi 2, Shu Tanaka 1,3,4,5 · 2026
Read Evaluating the solution performance of the augmented Lagrangian function on Ising machines by Shunsuke Awai 1, Takuro Itoh 1, Keita Takahashi 1, Kotaro Tanahashi 2, Shu Tanaka 1,3,4,5 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24241.txt.
Introduction
Awai and colleagues change how constrained problems are handed to Ising machines. These are special hardware that cut energy over binary values. Combinatorial optimisation under constraints is often written with a penalty function that fines violations. That formulation is known for touchy tuning. The augmented Lagrangian function, a trusted staple of continuous optimisation, offers an option. The team tests it in 2026, using the quadratic knapsack problem as benchmark.
Speed is time-to-epsilon: the time to reach a solution within a set margin of the best. Sweeping the method's two hyperparameters shows the augmented Lagrangian cuts that time by roughly tenfold, against the penalty formulation. Keeping one parameter small still yields feasible solutions. Typical settings reach highly exact answers earlier in the search. Awai's findings mark the augmented Lagrangian as a strong default for constrained Ising-machine problems.
Catalog record
| CREATOR | Shunsuke Awai 1, Takuro Itoh 1, Keita Takahashi 1, Kotaro Tanahashi 2, Shu Tanaka 1,3,4,5 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24241
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Evaluating the solution performance of the augmented Lagrangian function on Ising machines Shunsuke Awai 1, Takuro Itoh 1, Keita Takahashi 1, Kotaro Tanahashi 2, Shu Tanaka 1,3,4,5 Abstract We apply the augmented Lagrangian function (ALF) as a formulation for Ising machines and evaluate its performance by time-to-epsilon ( TT ε \mathrm{TT\varepsilon} ). The ALF has been well studied in continuous optimization for its numerical stability and convergence, and its advantage over the penalty function formulation is demonstrated here through the following results. Using the quadratic knapsack problem as a benchmark, we examine the dependence of TT ε \mathrm{TT\varepsilon} on the hyperparameters μ \mu and λ \lambda . The augmented Lagrangian formulation reduces TT ε \mathrm{TT\varepsilon} by roughly an order of magnitude compared with the penalty function formulation, keeping μ \mu small while obtaining feasible solutions and, for representative parameter settings, reaching high-precision solutions earlier in the search. These findings indicate that the augmented Lagrangian function is a promising formulation for improving the solution performance of Ising machines. 1 Introduction Combinatorial optimization is a mathematical problem of finding a combination of decision variables that minimizes or maximizes an objective function under given constraints [ 22 ] . Many real-world problems, such as logistics optimization, manufacturing scheduling, and communication routing, can be reduced to this form [ 5 , 30 , 32 , 1 ] . As the number of decision variables increases, the search space grows exponentially, and exhaustive search becomes intractable for large-scale problems. Developing efficient solution methods for such problems is therefore a long-standing and important challenge. To address this challenge, Ising machines have attracted attention as computing devices capable of efficiently searching for good solutions to combinatorial optimization problems [ 33 ] , and they have been applied to various practical problems such as financial optimization [ 39 , 48 , 43 ] , advertising optimization [ 45 ] , logistics [ 34 , 50 , 21 , 23 ] , materials science [ 10 , 26 , 28 , 49 , 41 , 4 ] , computer-aided engineering [ 8 , 12 , 29 ] , and biology [ 37 , 16 , 25 , 24 ] . In an Ising machine, the target combinatorial optimization problem is formulated as an Ising model, a mathematical model in statistical mechanics. The ground state of this model is then explored using state transitions based on physical or algorithmic dynamics. Representative internal algorithms of Ising machines include those based on simulated annealing (SA) and quantum annealing (QA). In SA-based Ising machines, a temperature parameter is introduced as a thermal fluctuation effect and gradually reduced to search for the ground state of the Ising model [ 27 , 18 , 19 ] . In QA-based Ising machines, quantum fluctuations are used to induce tunneling between states, and the ground state is searched for by gradually reducing the strength of these fluctuations [ 20 ] . Because Ising machines exhibit such stochastic behavior, the solution obtained can differ from trial to trial even when the same problem is solved under identical conditions. When solving a constrained combinatorial optimization problem with an Ising machine, a constraint term representing the constraints is added to the objective function, thereby casting the problem into an unconstrained form. Here, the penalty coefficient \mu , which balances the relative contributions of the objective function and the constraints, must be set to an appropriate value. The penalty coefficient \mu involves an inherent trade-off. If \mu is too small, infeasible states can have low energies, and the probability of sampling feasible solutions decreases. If \mu is too large, the energy landscape is dominated by the constraint term. In finite-time heuristic searches on Ising machines, this dominance can weaken the effect of objective-value differences, and feasible solutions with small objective error become difficult to obtain [ 44 , 2 ] . The setting of \mu that balances constraint satisfaction and solution precision is thus a key challenge. To address this trade-off, numerous tuning methods for finding an appropriate \mu have been reported [ 39 , 44 , 2 , 51 , 14 , 38 , 15 ] . One representative approach increases \mu incrementally until a feasible solution is obtained [ 39 ] . Another sets \mu based on an upper bound of the objective function value [ 2 ] , but the resulting \mu tends to be excessively large. As another approach, for the traveling salesman problem, the search range is defined by the minimum and maximum distances between any two points. Within this range, an approach that tries multiple penalty coefficients has also been proposed [ 44 ] . However, all of these methods share a common limitation: they adjust the trade-off using a single parameter. A natural formulation for mitigating this trade-off is the augmented Lagrangian function (ALF). The ALF introduces a Lagrange multiplier term in addition to the quadratic penalty term. In continuous optimization, augmented Lagrangian methods are known to alleviate the ill-conditioning associated with excessively large penalty coefficients [ 11 ] . In the present Ising-machine setting, we do not rely on this continuous-optimization convergence theory. Instead, we use the ALF as a QUBO formulation and examine whether the Lagrange multiplier term enables feasible solutions to be sampled while keeping \mu relatively small. In this sense, the ALF is expected to preserve the contribution of the objective term more effectively than the penalty function. Previous studies on the augmented Lagrangian approach for Ising machines have addressed two aspects: formulation efficiency and algorithmic efficiency. On the formulation side, the augmented Lagrangian formulation reduced the number of auxiliary variables required for inequality constraints, enabling the solution of larger-scale problems [ 7 , 3 , 13 ] . On the algorithmic side, the augmented Lagrangian method (ALM), which adaptively updates the hyperparameters based on the constraint violation, reduced the number of parameter updates compared with the conventional penalty method [ 46 , 6 ] . However, these studies did not directly evaluate how the ALF as a formulation influences the solution performance of the Ising machine. The objective of this study is therefore to evaluate the ALF as a formulation rather than as an iterative parameter-update algorithm. Using the quadratic knapsack problem as a benchmark, we formulate it with both the penalty function and the ALF on the same QUBO basis and compare their performance under two analyses. First, we quantify the dependence of \mathrm{TT\varepsilon} on \mu and \lambda and identify the parameter region in which the ALF achieves a lower \mathrm{TT\varepsilon} than the penalty function. Second, we examine the temporal evolution of the incumbent solution within the execution time to clarify how the formulation affects the early stage of the search. For the benchmark instances tested in this study, the ALF reduces \mathrm{TT\varepsilon} by roughly an order of magnitude compared with the penalty function. Furthermore, through a square-completion analysis, we show that the Lagrange multiplier term shifts the effective capacity of the constraint, providing a structural explanation for the observed improvement. The remainder of this paper is organized as follows. Section 2 introduces the input format for the Ising machine used in this study. Section 3 defines the formulation methods adopted and the evaluation metric.