| Presentation | 2022-06-17 QUBO Model Formulation based on Petri net Behavior for Combinatorial Optimization Problems Keisuke Tokuhira, Morikazu Nakamura, Mitsunaga Kinjo, Katsuhiko Shimabukuro, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | quantum annealing / combinatorial optimization / Petri nets / QUBO model / Ising model |
| Paper # | CAS2022-18,VLD2022-18,SIP2022-49,MSS2022-18 |
| Date of Issue | 2022-06-09 (CAS, VLD, SIP, MSS) |
| Conference Information | |
| Committee | CAS / SIP / VLD / MSS |
|---|---|
| Conference Date | 2022/6/16(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hachinohe Institute of Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Yoshinobu Maeda(Niigata Univ.) / Yukihiro Bandou(NTT) / Kazutoshi Kobayashi(Kyoto Inst. of Tech.) / Atsuo Ozaki(Osaka Inst. of Tech.) |
| Vice Chair | Yasutoshi Aibara(OmniVisionManufacturing) / Toshihisa Tanaka(Tokyo Univ. Agri.&Tech.) / Takayuki Nakachi(Ryukyu Univ.) / Minako Ikeda(NTT) / Shingo Yamaguchi(Yamaguchi Univ.) |
| Secretary | Yasutoshi Aibara(NIT, Toyama college) / Toshihisa Tanaka(Renesas) / Takayuki Nakachi(Xiaomi) / Minako Ikeda(Takushoku Univ.) / Shingo Yamaguchi(Tokyo Univ. Agri.&Tech.) |
| Assistant | 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.) |
| Paper Information | |
| Registration To | 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 |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | QUBO Model Formulation based on Petri net Behavior for Combinatorial Optimization Problems |
| Sub Title (in English) | |
| Keyword(1) | quantum annealing |
| Keyword(2) | combinatorial optimization |
| Keyword(3) | Petri nets |
| Keyword(4) | QUBO model |
| Keyword(5) | Ising model |
| 1st Author's Name | Keisuke Tokuhira |
| 1st Author's Affiliation | University of the Ryukyus(Univ. of the Ryukyus) |
| 2nd Author's Name | Morikazu Nakamura |
| 2nd Author's Affiliation | University of the Ryukyus(Univ. of the Ryukyus) |
| 3rd Author's Name | Mitsunaga Kinjo |
| 3rd Author's Affiliation | University of the Ryukyus(Univ. of the Ryukyus) |
| 4th Author's Name | Katsuhiko Shimabukuro |
| 4th Author's Affiliation | University of the Ryukyus(Univ. of the Ryukyus) |
| Date | 2022-06-17 |
| Paper # | CAS2022-18,VLD2022-18,SIP2022-49,MSS2022-18 |
| Volume (vol) | vol.122 |
| Number (no) | CAS-75,VLD-76,SIP-77,MSS-78 |
| Page | pp.pp.96-101(CAS), pp.96-101(VLD), pp.96-101(SIP), pp.96-101(MSS), |
| #Pages | 6 |
| Date of Issue | 2022-06-09 (CAS, VLD, SIP, MSS) |