| 講演名 | 2023-11-15 補正処理を導入した部分QUBOアニーリングによる複数日旅程最適化 野口 竜弥(早大), 深田 佳佑(早大), 鮑 思雅(早大), 戸川 望(早大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 複数日旅程最適化問題とは，複数日に亘って観光スポットやホテルを巡回する最適な経路を探索する組合せ最適化問題である．組合せ最適化問題を効率よく求解する計算機として，量子アニーラやイジングマシンが研究されている．量子アニーラは，組合せ最適化問題をQuadratic Unconstrained Binary Optimization (QUBO)モデルにマッピングすることで問題を求解できるが，ハードウェアの制約により入力できる問題サイズに上限があるため，問題サイズによってはQUBOモデルをそのまま求解することが困難な場合がある．そこで，QUBOモデルを量子アニーラに入力可能なサイズの部分QUBOに分割することで，大きなサイズの組合せ最適化問題を求解することができるが，量子アニーラは必ずしも問題の制約を満たす解を出力するとは限らない．そこで本稿では，量子アニーラによる部分QUBOアニーリングによって複数日旅程最適化問題の制約を満たさない解が得られた場合，問題の制約を満たすように解を補正する補正処理を部分QUBOアニーリング中に導入する手法を提案する．量子アニーラを用いた実験の結果，補正処理の導入により複数日旅程最適化問題の解が改善されることを確認した． |
| 抄録(英) | |
| キーワード(和) | 組合せ最適化問題 / 複数日旅程最適化問題 / 量子アニーラ / イジングモデル / QUBOモデル / 補正処理 |
| キーワード(英) | |
| 資料番号 | VLD2023-36,ICD2023-44,DC2023-43,RECONF2023-39 |
| 発行日 | 2023-11-08 (VLD, ICD, DC, RECONF) |
| 研究会情報 | |
| 研究会 | VLD / DC / RECONF / ICD / IPSJ-SLDM |
|---|---|
| 開催期間 | 2023/11/15(から3日開催) |
| 開催地（和） | くまもと市民会館シアーズホーム夢ホール |
| 開催地（英） | Civic Auditorium Sears Home Yume Hall |
| テーマ（和） | デザインガイア2023 -VLSI設計の新しい大地- |
| テーマ（英） | Design Gaia 2023 -New Field of VLSI Design- |
| 委員長氏名（和） | 中武 繁寿(北九州市大) / 土屋 達弘(阪大) / 山口 佳樹(筑波大) / 池田 誠(東大) / 越智 裕之(立命館大) |
| 委員長氏名（英） | Shigetoshi Nakatake(Univ. of Kitakyushu) / Tatsuhiro Tsuchiya(Osaka Univ.) / Yoshiki Yamaguchi(Tsukuba Univ.) / Makoto Ikeda(Univ. of Tokyo) / Hiroyuki Ochi(Ritsumeikan Univ.) |
| 副委員長氏名（和） | 桜井 祐市(日立) / 細川 利典(日大) / 井口 寧(北陸先端大) / 泉 知論(立命館大) / 若林 準人(ソニーセミコンダクタソリューションズ) |
| 副委員長氏名（英） | Yuichi Sakurai(Hitachi) / Toshinori Hosokawa(Nihon Univ.) / Yasushi Inoguchi(JAIST) / Tomonori Izumi(Ritsumeikan Univ.) / Hayato Wakabayashi(Sony Semiconductor Solutions) |
| 幹事氏名（和） | 笹川 幸宏(ソシオネクスト) / 今井 雅(弘前大) / 新井 雅之(日大) / 難波 一輝(千葉大) / 小林 悠記(NEC) / 佐藤 幸紀(豊橋技科大) / 吉原 義昭(キオクシア) / 宮地 幸祐(信州大) / 今川 隆司(明大) / 岸田 亮(富山県立大) / 田中 勇気(日立) / 五十嵐 友則(ルネサス) |
| 幹事氏名（英） | Yukihiro Sasagawa(Socionext) / Masashi Imai(Hirosaki Univ.) / Masayuki Arai(Nihon Univ.) / Kazuteru Namba(Chiba Univ.) / Yuuki Kobayashi(NEC) / Yukinori Sato(Toyohashi Univ. of Tech.) / Yoshiaki Yoshihara(Kioxia) / Kosuke Miyaji(Shinshu Univ.) / Takashi Imagawa(Meiji Univ.) / Ryo Kishida(Toyama Prefectural Univ.) / Yuki Tanaka(HITACHI) / Tomonori Igarashi(Renesas) |
| 幹事補佐氏名（和） | 西元 琢真(日立) / / 竹村 幸尚(インテル) / 長名 保範(熊本大) / 白井 僚(京大) / 塩見 準(阪大) / 久保木 猛(熊本大) |
| 幹事補佐氏名（英） | Takuma Nishimoto(Hitachi) / / Yukitaka Takemura(INTEL) / Yasunori Osana(Kumamoto Univ.) / Ryo Shirai(Kyoto Univ.) / Jun Shiomi(Osaka Univ.) / Takeshi Kuboki(Kumamoto University) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on VLSI Design Technologies / Technical Committee on Dependable Computing / Technical Committee on Reconfigurable Systems / Technical Committee on Integrated Circuits and Devices / Special Interest Group on System and LSI Design Methodology |
|---|---|
| 本文の言語 | JPN-ONLY |
| タイトル（和） | 補正処理を導入した部分QUBOアニーリングによる複数日旅程最適化 |
| サブタイトル（和） | |
| タイトル（英） | |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化問題 |
| キーワード(2)（和/英） | 複数日旅程最適化問題 |
| キーワード(3)（和/英） | 量子アニーラ |
| キーワード(4)（和/英） | イジングモデル |
| キーワード(5)（和/英） | QUBOモデル |
| キーワード(6)（和/英） | 補正処理 |
| 第 1 著者 氏名（和/英） | 野口 竜弥 |
| 第 1 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 第 2 著者 氏名（和/英） | 深田 佳佑 |
| 第 2 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 第 3 著者 氏名（和/英） | 鮑 思雅 |
| 第 3 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 第 4 著者 氏名（和/英） | 戸川 望 |
| 第 4 著者 所属（和/英） | 早稲田大学(略称：早大) |
| 発表年月日 | 2023-11-15 |
| 資料番号 | VLD2023-36,ICD2023-44,DC2023-43,RECONF2023-39 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | VLD-258,ICD-259,DC-260,RECONF-261 |
| ページ範囲 | pp.37-42(VLD), pp.37-42(ICD), pp.37-42(DC), pp.37-42(RECONF), |
| ページ数 | 6 |
| 発行日 | 2023-11-08 (VLD, ICD, DC, RECONF) |