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
Untuk merumuskan Masalah Tas Beg Kuadratik (QKPs) ke dalam bentuk Pengoptimuman Perduaan Tidak Terkandas Kuadratik (QUBO), adalah perlu untuk memperkenalkan pembolehubah integer, yang menukar dan menggabungkan kekangan kapasiti ransel ke dalam fungsi tenaga keseluruhan. Dalam QUBO, pembolehubah integer ini dikodkan dengan pembolehubah perduaan tambahan, dan kaedah pengekodan yang digunakan untuknya mempengaruhi tingkah laku Simulated Annealing (SA) dengan ketara. Untuk meningkatkan kecekapan SA bagi contoh QKP, kertas kerja ini mula-mula memvisualisasikan dan menganalisis proses penyepuhlindapan mereka yang dikodkan oleh kaedah pengekodan binari dan unari konvensional. Berdasarkan analisis ini, kami mencadangkan pengekodan hibrid novel (HE), mendapatkan yang terbaik daripada kedua-dua dunia. HE yang dicadangkan memperoleh penyelesaian yang boleh dilaksanakan dalam penilaian, mengatasi prestasi yang lain dalam model berskala kecil dan sederhana.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -