Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

KAZUKI IKEUCHI 1, YOSHIKI MATSUDA 2 , AND SHU TANAKA 1,3,4,5 · 2025

Read Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems by KAZUKI IKEUCHI 1, YOSHIKI MATSUDA 2 , AND SHU TANAKA 1,3,4,5 (2025) 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-2510-24237.txt.

Introduction

Kazuki Ikeuchi and two co-authors test whether solving hard optimization problems directly in higher order form beats the usual reduction step. Ising machines, including quantum annealers, promise fast solutions, but most hardware handles only linear and quadratic terms. Problems with higher order terms must be reduced, which adds variables and constraints and can lower solution quality.

The team uses a strong simulated annealing solver that handles polynomial binary problems directly, with no reduction. They compare it against a conventional quadratic approach on combinatorial problems. The study gauges when keeping the higher order form pays off in solution quality and when the standard reduction remains the better choice.

Catalog record

CREATORKAZUKI IKEUCHI 1, YOSHIKI MATSUDA 2 , AND SHU TANAKA 1,3,4,5
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-24237

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems KAZUKI IKEUCHI 1, YOSHIKI MATSUDA 2 , AND SHU TANAKA 1,3,4,5 Abstract Ising machines, including quantum annealing machines, are promising next-generation computers for combinatorial optimization problems. However, due to hardware limitations, most Ising-type hardware can only solve objective functions expressed in linear or quadratic terms of binary variables. Therefore, problems with higher-order terms require an order-reduction process, which increases the number of variables and constraints and may degrade solution quality. In this study, we evaluate the effectiveness of directly solving such problems without order reduction by using a high-performance simulated annealing-based optimization solver capable of handling polynomial unconstrained binary optimization (PUBO) formulations. We compare its performance against a conventional quadratic unconstrained binary optimization (QUBO) solver on the same hardware platform. As benchmarks, we use the low autocorrelation binary sequence (LABS) problem and the vehicle routing problem with distance balancing, both of which naturally include higher-order interactions. Results show that the PUBO solver consistently achieves superior solution quality and stability compared to its QUBO counterpart, while maintaining comparable computational time and requiring no order-reduction compilation indicating potential advantages of directly handling higher-order terms in practical optimization problems. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. † † history: Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000. † † doi: 10.1109/ACCESS.2017.DOI † † address: Graduate School of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama-shi, Kanagawa 223–8522, Japan † † address: Fixstars Corporation, 3-1-1, Shibaura, Minato-ku, Tokyo 108–0023, Japan † † address: Department of Applied Physics and Physico-Informatics, Keio University, Kanagawa 223–8522, Japan † † address: Keio University Sustainable Quantum Artificial Intelligence Center (KSQAIC), Keio University, Tokyo 108–8345, Japan † † address: Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University, Tokyo 108–8345, Japan † † titlenote: This work was partially supported by the Council for Science, Technology, and Innovation (CSTI) through the Cross-ministerial Strategic Innovation Promotion Program (SIP), “Promoting the application of advanced quantum technology platforms to social issues” (Funding agency: QST), the Japan Society for the Promotion of Science (JSPS) KAKENHI (Grant Number JP23H05447), Japan Science and Technology Agency (JST) (Grant Number JPMJPF2221). † † corresponding: Corresponding author: Kazuki Ikeuchi (e-mail: [email protected]). I Introduction Combinatorial optimization problems are widely encountered in various fields of modern society, such as logistics [ 1 , 2 , 3 ] , materials design [ 4 , 5 , 6 ] , and portfolio optimization [ 7 , 8 , 9 , 10 ] . These problems are formulated as mathematical models comprising decision variables with combinatorial structures, objective functions, and constraints. Let the decision variable vector with a combinatorial structure be denoted by \bm{z} , and its entire search space by \mathcal{S} . Furthermore, the subset of feasible solutions that satisfy all constraints is denoted by \mathcal{F} . The goal of combinatorial optimization is to find the decision variable vector that minimizes the objective function while satisfying all constraints, that is, {\bm{z}}^{*}=\operatorname*{argmin}_{\bm{z}}f_{\operatorname*{obj}}({\bm{z}}),\quad{\bm{z}}\in{\mathcal{F}}\subseteq{\mathcal{S}}, (1) where \bm{z}^{*} represents the optimal solution. However, it is well known that the number of candidate solutions (i.e., the size of {\mathcal{S}} ) increases exponentially with the number of decision variables, making exhaustive search computationally infeasible for large-scale problems. Therefore, various heuristic and metaheuristic algorithms have been developed to obtain near-optimal solutions within a practical computational time. Among the representative metaheuristic approaches, Simulated Annealing (SA) is a well-established method for combinatorial optimization. SA interprets the objective function as an energy function and introduces a temperature parameter to control the stochastic search process, gradually lowering the temperature to explore low-energy states. Thus, SA can be regarded as an algorithm based on state transitions driven by thermal fluctuations. Inspired by the concept of SA, Quantum Annealing (QA) has been proposed as a quantum-mechanical extension [ 11 , 12 , 13 ] . In QA, quantum fluctuations play a role analogous to thermal fluctuations in SA. Similar to SA, the objective function is treated as an energy function, and a parameter controlling the strength of quantum fluctuations is gradually decreased to obtain low-energy configurations. In recent years, hardware implementations of such physics-inspired algorithms, referred to as Ising machines, have been developed [ 14 , 15 , 16 ] . An Ising machine is designed to search for low-energy states of an Ising model or its equivalent Quadratic Unconstrained Binary Optimization (QUBO) formulation. In recent years, various algorithmic improvements have been developed to enhance the performance of Ising machines, such as hybrid quantum-classical schemes [ 17 , 4 , 18 , 19 , 20 ] , variable-reduction techniques [ 21 , 22 , 23 ] , and appropriate tuning of hyperparameters [ 24 , 25 , 26 , 27 , 28 ] . In parallel, Ising machines have been applied to a wide range of practical problems in various fields [ 29 , 30 ] . Since most existing hardware platforms accept QUBO as the standard input format, the energy function must be expressed as a polynomial composed solely of linear and quadratic terms of binary variables. Consequently, problems involving higher-order interactions require order-reduction techniques to transform Polynomial Unconstrained Binary Optimization (PUBO) problems into the QUBO form [ 31 , 32 ] . Several studies have been conducted to develop efficient methods for performing this order reduction [ 33 , 34 ] , and such approaches have proven to be effective in solving various optimization problems involving higher-order terms. However, order reduction techniques inevitably introduce additional auxiliary variables and constraints to maintain consistency between the original and transformed formulations. These additional components increase the problem size and structural complexity, potentially degrading the overall solution quality. Nevertheless, numerous real-world problems inherently involve higher-order interactions, such as polymer sampling [ 35 , 36 ] , protein folding [ 37 , 38 ] , and optimizing molecular adsorption configurations on alloy surfaces [ 39 ] . Accordingly, developing solvers capable of directly handling higher-order terms is becoming increasingly important. Motivated by this background, this study compares two distinct approaches for solving combinatorial optimization problems, one that directly handles higher-order terms without order reduction, and another that applies order reduction techniques to convert problems into the QUBO form. The comparative evaluation focuses on the solution quality and performance characteristics of both formulations. For this purpose, the Fixstars Amplify Annealing Engine (Amplify AE) [ 40 ] was employed. Amplify AE is a high-performance optimization solver based on the simulated annealing algorithm, designed to efficiently solve combinatorial optimization problems through energy-based searches on Ising models. In addition to conventional quadratic optimization problems, Amplify AE provides a polynomial optimization solver that can directly handle up to fourth-order terms without order reduction. Since both solvers operate on the same hardware platform and share the same underlying algorithm, Amplify AE provides a fair and consistent environment for evaluating performance differences attributable solely to order reduction. Previous studies have also investigated the implications of solving higher-order problems directly, rather than reducing them to a quadratic form. For instance, comparisons of energy gaps in the 3-SAT problem have shown that maintaining the PUBO formulation can be advantageous for adiabatic performance compared to the

Read the complete text