講演抄録/キーワード |
講演名 |
2022-06-17 15:45
ペトリネットの振舞いに基づく組合せ最適化問題のQUBOモデル定式化 ○渡久平圭佑・名嘉村盛和・金城光永・島袋勝彦(琉球大) CAS2022-18 VLD2022-18 SIP2022-49 MSS2022-18 |
抄録 |
(和) |
本稿では,量子アニーリングによる最適化計算に必要なイジングモデルもしくは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 / / / |
文献情報 |
信学技報, vol. 122, no. 78, MSS2022-18, pp. 96-101, 2022年6月. |
資料番号 |
MSS2022-18 |
発行日 |
2022-06-09 (CAS, VLD, SIP, MSS) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2022-18 VLD2022-18 SIP2022-49 MSS2022-18 |
|