TY - JOUR
T1 - Performance Comparison of Typical Binary-Integer Encodings in an Ising Machine
AU - Tamura, Kensuke
AU - Shirai, Tatsuhiko
AU - Katsura, Hosho
AU - Tanaka, Shu
AU - Togawa, Nozomu
N1 - Funding Information:
This article is based on the results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO). The work of Shu Tanaka was supported in part by the Japan Society for the Promotion of Science (JSPS) KAKENHI under Grant 19H01553. Kensuke Tamura and Hosho Katsura acknowledge Yutaka Akagi for fruitful discussions.
Publisher Copyright:
© 2013 IEEE.
PY - 2021
Y1 - 2021
N2 - The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.
AB - The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.
KW - Ising machine
KW - Ising model
KW - binary-integer encoding
KW - combinatorial optimization problem
KW - quadratic knapsack problem
KW - quadratic unconstrained binary optimization
UR - http://www.scopus.com/inward/record.url?scp=85107233033&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107233033&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2021.3081685
DO - 10.1109/ACCESS.2021.3081685
M3 - Article
AN - SCOPUS:85107233033
SN - 2169-3536
VL - 9
SP - 81032
EP - 81039
JO - IEEE Access
JF - IEEE Access
M1 - 9435359
ER -