IEICE TRANSACTIONS on Information
A Hybrid Integer Encoding Method for Obtaining High-Quality Solutions of Quadratic Knapsack Problems on Solid-State Annealers
Summary :
For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.12 pp.2019-2031
- Publication Date
- 2022/12/01
- Publicized
- 2022/05/26
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2022PAP0006
- Type of Manuscript
- Special Section PAPER (Special Section on Forefront Computing)
- Category
Authors
Satoru JIMBO
Tokyo Institute of Technology
Daiki OKONOGI
Tokyo Institute of Technology
Kota ANDO
Hokkaido University
Thiem Van CHU
Tokyo Institute of Technology
Jaehoon YU
Tokyo Institute of Technology
Masato MOTOMURA
Tokyo Institute of Technology
Kazushi KAWAMURA
Tokyo Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoru JIMBO, Daiki OKONOGI, Kota ANDO, Thiem Van CHU, Jaehoon YU, Masato MOTOMURA, Kazushi KAWAMURA, "A Hybrid Integer Encoding Method for Obtaining High-Quality Solutions of Quadratic Knapsack Problems on Solid-State Annealers" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 12, pp. 2019-2031, December 2022, doi: 10.1587/transinf.2022PAP0006.
Abstract: For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022PAP0006/_p
Copy
@ARTICLE{e105-d_12_2019,
author={Satoru JIMBO, Daiki OKONOGI, Kota ANDO, Thiem Van CHU, Jaehoon YU, Masato MOTOMURA, Kazushi KAWAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={A Hybrid Integer Encoding Method for Obtaining High-Quality Solutions of Quadratic Knapsack Problems on Solid-State Annealers},
year={2022},
volume={E105-D},
number={12},
pages={2019-2031},
abstract={For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.},
keywords={},
doi={10.1587/transinf.2022PAP0006},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - A Hybrid Integer Encoding Method for Obtaining High-Quality Solutions of Quadratic Knapsack Problems on Solid-State Annealers
T2 - IEICE TRANSACTIONS on Information
SP - 2019
EP - 2031
AU - Satoru JIMBO
AU - Daiki OKONOGI
AU - Kota ANDO
AU - Thiem Van CHU
AU - Jaehoon YU
AU - Masato MOTOMURA
AU - Kazushi KAWAMURA
PY - 2022
DO - 10.1587/transinf.2022PAP0006
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2022
AB - For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.
ER -
English
