WEKO3
アイテム
不等式制約付き組合せ最適化問題に対する列生成法とイジングマシン活用のハイブリッドアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/233704
https://ipsj.ixsq.nii.ac.jp/records/233704b153d4a7-b2bc-4e77-8490-7452d1077947
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-QS24011030.pdf (1.1 MB)
2026年3月21日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, QS:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-03-21 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | 不等式制約付き組合せ最適化問題に対する列生成法とイジングマシン活用のハイブリッドアルゴリズム | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 慶應義塾大学大学院理工学研究科基礎理工学専攻 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 慶應義塾大学大学院理工学研究科基礎理工学専攻 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 株式会社リクルート | ||||||||||||||
| 著者所属 | ||||||||||||||
| 慶應義塾大学大学院理工学研究科基礎理工学専攻／慶應義塾大学理工学部物理情報工学科／慶應義塾大学ヒト生物学―微生物叢―量子計算研究センター(WPI-Bio2Q) | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Graduate School of Science and Technology, Keio University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Graduate School of Science and Technology, Keio University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Recruit Co., Ltd. | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Graduate School of Science and Technology, Keio University / Department of Applied Physics and Physico-Informatics, Keio University / Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University | ||||||||||||||
| 著者名 |
金井, 博志
× 金井, 博志
× 山下, 将司
× 棚橋, 耕太郎
× 田中, 宗
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 組合せ最適化問題に対する高効率な次世代計算機としてイジングマシンが期待されている．実社会における諸問題を組合せ最適化問題として定式化する場合，不等式制約を伴うことがある．一方，現行のイジングマシンにおけるビット数の制限 [1-6] や定式化に対する依存性 [7] から，不等式制約付き組合せ最適化問題を直接解くことは困難である．不等式制約を有する典型的な問題として容量制約付き配送計画問題（Capacitated Vehicle Routing Problem，CVRP）がある．CVRP は，複数の車両を用いて拠点に保管された荷物を各地点に配達する総移動距離を目的関数とし，これを最小にする問題である．また，各地点の需要量の総和がその地点を担当する車両の容量を超えないという不等式制約が付与されている．CVRP は NP 困難に分類され，列生成法 [8-11] と呼ばれるヒューリスティックな手法が有効である．実行可能な経路数は地点数に対して指数関数的に増大するため，列生成法では特に有望な経路のみを逐次追加する．集合被覆問題を主問題とし，対応する双対解を用いて容量制約付きの子問題を定義する．この子問題が新規経路の作成を担っており，イジングマシンを適用することで既存のソルバーよりも高効率に解探索が可能であると示唆する結果が得られている [12]．本研究は，列生成法とイジングマシン活用によるハイブリッドアルゴリズムを通じ，イジングマシンで直接解くことが難しい不等式制約付き組合せ最適化問題を解くことを目的とする．これは，イジングマシンの活用幅を広げることにつながる．本原稿では，パラメータ化された不等式制約の難しさに対して提案手法が従来の手法に比べて計算効率の観点で良いアルゴリズムであることを数値計算結果を通じて示す． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AA12894105 | |||||||||||||
| 書誌情報 |
研究報告量子ソフトウェア（QS） 巻 2024-QS-11, 号 30, p. 1-8, 発行日 2024-03-21 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 2435-6492 | |||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
