Spin-Variable Reduction Method for Handling Linear Equality Constraints in Ising Machines

We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy sol...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2023-08, Vol.72 (8), p.2151-2164
Main Authors: Shirai, Tatsuhiko, Togawa, Nozomu
Format: Article
Language:English
Subjects:
Combinatorial analysis
Combinatorial optimization problem
Equality
Ising machine
Ising model
Linear programming
metaheuristics
Operations research
Optimization
Quantum annealing
Reduction
Search problems
Simulated annealing
Stationary state
Symbols
variable reduction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a spin-variable reduction method for Ising machines to handle linear equality constraints in a combinatorial optimization problem. Ising machines including quantum-annealing machines can effectively solve combinatorial optimization problems. They are designed to find the lowest-energy solution of a quadratic unconstrained binary optimization (QUBO), which is mapped from the combinatorial optimization problem. The proposed method reduces the number of binary variables to formulate the QUBO compared to the conventional penalty method. We demonstrate a sufficient condition to obtain the optimum of the combinatorial optimization problem in the spin-variable reduction method and its general applicability. We apply it to typical combinatorial optimization problems, such as the graph k k -partitioning problem and the quadratic assignment problem. Experiments using simulated-annealing and quantum-annealing based Ising machines demonstrate that the spin-variable reduction method outperforms the penalty method. The proposed method extends the application of Ising machines to larger-size combinatorial optimization problems with linear equality constraints.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2023.3239539