| 講演名 | 2022-06-17 ペトリネットの振舞いに基づく組合せ最適化問題のQUBOモデル定式化 渡久平 圭佑(琉球大), 名嘉村 盛和(琉球大), 金城 光永(琉球大), 島袋 勝彦(琉球大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では，量子アニーリングによる最適化計算に必要なイジングモデルもしくはQUBOモデルを，対象の問題を表現したペトリネットの振舞いから生成する手法を提案する．最初にペトリネットの振舞いに関連する発火条件，状態方程式，可達問題，保存性のQUBOモデルを整理した後，巡回セールスマン問題，およびジョブショップスケジューリング問題の定式化を行う．これにより，これらの最適化問題のQUBOモデルの定式化がペトリネットの振る舞いにおける基本的な制約と問題独自の制約を組み合わせることで容易に定式化できることを示す． |
| 抄録(英) | This paper proposes a method to generate Ising or QUBO models based on Petri net behavioral properties for combinatorial optimization by quantum annealing or quantum-inspired annealing. We present the QUBO models for the firing condition, the state equation, the reachability problem, and conservativeness in Petri net behaviors. We apply our Petri net-based formulation to well-known problems, the traveler's salesman problem and the job-shop scheduling problem, to show the usefulness of our approach. |
| キーワード(和) | 量子アニーリング / 組合せ最適化 / ペトリネット / QUBOモデル / イジングモデル |
| キーワード(英) | quantum annealing / combinatorial optimization / Petri nets / QUBO model / Ising model |
| 資料番号 | CAS2022-18,VLD2022-18,SIP2022-49,MSS2022-18 |
| 発行日 | 2022-06-09 (CAS, VLD, SIP, MSS) |
| 研究会情報 | |
| 研究会 | CAS / SIP / VLD / MSS |
|---|---|
| 開催期間 | 2022/6/16(から2日開催) |
| 開催地（和） | 八戸工業大学 1号館201室（多目的ホール） |
| 開催地（英） | Hachinohe Institute of Technology |
| テーマ（和） | システムと信号処理および一般 |
| テーマ（英） | |
| 委員長氏名（和） | 前田 義信(新潟大) / 坂東 幸浩(NTT) / 小林 和淑(京都工繊大) / 尾崎 敦夫(阪工大) |
| 委員長氏名（英） | Yoshinobu Maeda(Niigata Univ.) / Yukihiro Bandou(NTT) / Kazutoshi Kobayashi(Kyoto Inst. of Tech.) / Atsuo Ozaki(Osaka Inst. of Tech.) |
| 副委員長氏名（和） | 相原 康敏(オムニビジョン) / 田中 聡久(東京農工大) / 仲地 孝之(琉球大学) / 池田 奈美子(NTT) / 山口 真悟(山口大) |
| 副委員長氏名（英） | Yasutoshi Aibara(OmniVisionManufacturing) / Toshihisa Tanaka(Tokyo Univ. Agri.&Tech.) / Takayuki Nakachi(Ryukyu Univ.) / Minako Ikeda(NTT) / Shingo Yamaguchi(Yamaguchi Univ.) |
| 幹事氏名（和） | 伊藤 尚(富山高専) / 鈴木 寛人(ルネサスエレクトロニクス) / 杉本 憲治郎(Xiaomi) / 渡辺 修(拓殖大) / 田中 雄一(東京農工大) / 兼本 大輔(大阪大学) / 宮村 信(NEC) / 小林 孝一(北大) / 劉 健全(NEC) |
| 幹事氏名（英） | Nao Ito(NIT, Toyama college) / Hiroto Suzuki(Renesas) / Kenjiro Sugimoto(Xiaomi) / Osamu Watanabe(Takushoku Univ.) / Yuichi Tanaka(Tokyo Univ. Agri.&Tech.) / Daisuke Kanemoto(Osaka Univ.) / Makoto Miyamura(NEC) / Koichi Kobayashi(Hokkaido Univ.) / Jianquan Liui(NEC) |
| 幹事補佐氏名（和） | 山口 基(テクノプロ) / 中村 洋平(日立) / 佐藤 隆英(山梨大) / 下田 真二(ソニーLSIデザイン) / 越田 俊介(八戸工大) / 吉田 太一(電通大) / 京地 清介(北九州市立大) / / 白井 匡人(島根大) |
| 幹事補佐氏名（英） | Motoi Yamaguchi(TECHNOPRO) / Yohei Nakamura(Hitachi) / Takahide Sato(Univ. of Yamanashi) / Shinji Shimoda(Sony LSI Design) / Shunsuke Koshita(Hachinohe Inst. of Tech.) / Taichi Yoshida(UEC) / Seisuke Kyochi(Univ. of Kitakyushu) / / Masato Shirai(Shimane Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Circuits and Systems / Technical Committee on Signal Processing / Technical Committee on VLSI Design Technologies / Technical Committee on Mathematical Systems Science and its Applications |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ペトリネットの振舞いに基づく組合せ最適化問題のQUBOモデル定式化 |
| サブタイトル（和） | |
| タイトル（英） | QUBO Model Formulation based on Petri net Behavior for Combinatorial Optimization Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子アニーリング / quantum annealing |
| キーワード(2)（和/英） | 組合せ最適化 / combinatorial optimization |
| キーワード(3)（和/英） | ペトリネット / Petri nets |
| キーワード(4)（和/英） | QUBOモデル / QUBO model |
| キーワード(5)（和/英） | イジングモデル / Ising model |
| 第 1 著者 氏名（和/英） | 渡久平 圭佑 / Keisuke Tokuhira |
| 第 1 著者 所属（和/英） | 琉球大学(略称：琉球大) University of the Ryukyus(略称：Univ. of the Ryukyus) |
| 第 2 著者 氏名（和/英） | 名嘉村 盛和 / Morikazu Nakamura |
| 第 2 著者 所属（和/英） | 琉球大学(略称：琉球大) University of the Ryukyus(略称：Univ. of the Ryukyus) |
| 第 3 著者 氏名（和/英） | 金城 光永 / Mitsunaga Kinjo |
| 第 3 著者 所属（和/英） | 琉球大学(略称：琉球大) University of the Ryukyus(略称：Univ. of the Ryukyus) |
| 第 4 著者 氏名（和/英） | 島袋 勝彦 / Katsuhiko Shimabukuro |
| 第 4 著者 所属（和/英） | 琉球大学(略称：琉球大) University of the Ryukyus(略称：Univ. of the Ryukyus) |
| 発表年月日 | 2022-06-17 |
| 資料番号 | CAS2022-18,VLD2022-18,SIP2022-49,MSS2022-18 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | CAS-75,VLD-76,SIP-77,MSS-78 |
| ページ範囲 | pp.96-101(CAS), pp.96-101(VLD), pp.96-101(SIP), pp.96-101(MSS), |
| ページ数 | 6 |
| 発行日 | 2022-06-09 (CAS, VLD, SIP, MSS) |