The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
QKP(Quadratic Knapsack Problem)를 QUBO(Quadratic Unconstrained Binary Optimization) 형식으로 공식화하려면 배낭 용량 제약 조건을 전체 에너지 함수로 변환하고 통합하는 정수 변수를 도입해야 합니다. QUBO에서는 이 정수 변수가 보조 바이너리 변수로 인코딩되며, 이에 사용되는 인코딩 방법은 SA(Simulated Annealing)의 동작에 큰 영향을 미칩니다. QKP 인스턴스에 대한 SA의 효율성을 향상시키기 위해 본 논문에서는 먼저 기존 바이너리 및 단항 인코딩 방법으로 인코딩된 어닐링 프로세스를 시각화하고 분석했습니다. 이 분석을 바탕으로 우리는 두 가지 장점을 모두 활용하는 새로운 하이브리드 인코딩(HE)을 제안했습니다. 제안된 HE는 평가에서 실행 가능한 솔루션을 얻었으며 중소 규모 모델에서 다른 것보다 뛰어난 성능을 보였습니다.
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
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.
부
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
부
@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},}
부
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 -