| 講演名 | 2019-11-14 グリッド分割を用いたイジングモデルによる巡回セールスマン問題の解法 党 璋(京大), 西川 剛史(京大), 佐藤 高史(京大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 組合せ最適化問題の近似解を効率的に求める手法として，イジングモデルを用いる解法が注目を集めている．代表的な組合せ最適化問題として巡回セールスマン問題が知られているが，イジングモデルを用いて巡回セールスマン問題を解こうとすると，制約条件を満たす解が得られにくく，制約条件を満たす解を得られたとしても解の品質が十分でないという課題が存在する．本稿では，制約条件を満たしやすく，かつ，高品質の解を求めることができるように，グリッド分割を併用する解法を提案し，巡回セールスマン問題のベンチマークを用いて評価する．提案手法によって，解の平均値が既存手法と比べて最大で72.8%改善されることを確認した． |
| 抄録(英) | Ising-model based solver is gaining increasing attention for its efficiency in finding approximate solutions for combinatorial optimization problems. The traveling salesman problem is known as a typical combinatorial optimization problem. However, when solving the traveling salesman problem using the Ising-model based solver, it is difficult to obtain a solution that satisfies the constraints. In addition, the quality of the solution tend to be insufficient even if the constraints could be met. In this paper, we propose a method that uses grid partitioning, with which a high-quality solution that satisfies constraints are obtained. Through the evaluation using benchmark problems, the quality of the solution with the proposed method has been improved up to 72.8%. |
| キーワード(和) | 組合せ最適化問題 / 巡回セールスマン問題 / イジングモデル / アニーリング / グリッド分割 |
| キーワード(英) | Combinatorial optimization problem / traveling salesman problem / ising model / annealing / grid partitioning |
| 資料番号 | VLD2019-40,DC2019-64 |
| 発行日 | 2019-11-06 (VLD, DC) |
| 研究会情報 | |
| 研究会 | VLD / DC / CPSY / RECONF / ICD / IE / IPSJ-SLDM / IPSJ-EMB / IPSJ-ARC |
|---|---|
| 開催期間 | 2019/11/13(から3日開催) |
| 開催地（和） | 愛媛県男女共同参画センター |
| 開催地（英） | Ehime Prefecture Gender Equality Center |
| テーマ（和） | デザインガイア2019 -VLSI設計の新しい大地- |
| テーマ（英） | Design Gaia 2019 -New Field of VLSI Design- |
| 委員長氏名（和） | 戸川 望(早大) / 福本 聡(首都大東京) / 入江 英嗣(東大) / 柴田 裕一郎(長崎大) / 永田 真(神戸大) / 木全 英明(NTT) / 田宮 豊(富士通研) / / 井上 弘士(九大) |
| 委員長氏名（英） | Nozomu Togawa(Waseda Univ.) / Satoshi Fukumoto(Tokyo Metropolitan Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Yuichiro Shibata(Nagasaki Univ.) / Makoto Nagata(Kobe Univ.) / Hideaki Kimata(NTT) / Yutaka Tamiya(Fujitsu Lab.) / / Hiroshi Inoue(Kyushu Univ.) |
| 副委員長氏名（和） | 福田 大輔(富士通研) / 高橋 寛(愛媛大) / 鯉渕 道紘(NII) / 中島 耕太(富士通研) / 佐野 健太郎(理研) / 山口 佳樹(筑波大) / 高橋 真史(東芝メモリ) / 児玉 和也(NII) / 高橋 桂太(名大) |
| 副委員長氏名（英） | Daisuke Fukuda(Fujitsu Labs.) / Hiroshi Takahashi(Ehime Univ.) / Michihiro Koibuchi(NII) / Kota Nakajima(Fujitsu Lab.) / Kentaro Sano(RIKEN) / Yoshiki Yamaguchi(Tsukuba Univ.) / Masafumi Takahashi(Toshiba-memory) / Kazuya Kodama(NII) / Keita Takahashi(Nagoya Univ.) |
| 幹事氏名（和） | 小平 行秀(会津大) / 桜井 祐市(日立) / 新井 雅之(日大) / 難波 一輝(千葉大) / 津邑 公暁(名工大) / 高前田 伸也(北大) / 谷川 一哉(広島市大) / 三好 健文(イーツリーズ・ジャパン) / 夏井 雅典(東北大) / 柘植 政利(ソシオネクスト) / 早瀬 和也(NTT) / 松尾 康孝(NHK) / 土谷 亮(滋賀県大) / 岩崎 裕江(NTT) / 佐々木 通(三菱電機) / / 近藤 正章(東大) / 塩谷 亮太(名大) / 田中 美帆(富士通研) / 長谷川 揚平(東芝メモリ) |
| 幹事氏名（英） | Yukihide Kohira(Univ. of Aizu) / Yuichi Sakurai(Hitachi) / Masayuki Arai(Nihon Univ.) / Kazuteru Namba(Chiba Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Shinya Takameda(Hokkaido Univ.) / Kazuya Tanigawa(Hiroshima City Univ.) / Takefumi Miyoshi(e-trees.Japan) / Masanori Natsui(Tohoku Univ.) / Masatoshi Tsuge(Socionext) / Kazuya Hayase(NTT) / Yasutaka Matsuo(NHK) / Akira Tsuchiya(Univ. Shiga Prefecture) / Hiroe Iwasaki(NTT) / Toru Sasaki(Mitsubishi Electric) / / Masaaki Kondo(Univ. of Tokyo) / Ryota Shioya(Nagoya Univ.) / Miho Tanaka(Fujitsu Labs.) / Yohei Hasegawa(Toshiba Memory) |
| 幹事補佐氏名（和） | 池田 一樹(日立) / / 有間 英志(東大) / 小川 周吾(日立) / 小林 悠記(NEC) / 中原 啓貴(東工大) / 廣瀬 哲也(阪大) / 新居 浩二(フローディア) / 久保木 猛(九大) / 海野 恭平(KDDI総合研究所) / 福嶋 慶繁(名工大) |
| 幹事補佐氏名（英） | Kazuki Ikeda(Hitachi) / / Eiji Arima(Univ. of Tokyo) / Shugo Ogawa(Hitachi) / Yuuki Kobayashi(NEC) / Hiroki Nakahara(Tokyo Inst. of Tech.) / Tetsuya Hirose(Osaka Univ.) / Koji Nii(Floadia) / Takeshi Kuboki(Kyushu Univ.) / Kyohei Unno(KDDI Research) / Norishige Fukushima(Nagoya Inst. of Tech.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on VLSI Design Technologies / Technical Committee on Dependable Computing / Technical Committee on Computer Systems / Technical Committee on Reconfigurable Systems / Technical Committee on Integrated Circuits and Devices / Technical Committee on Image Engineering / Special Interest Group on System and LSI Design Methodology / Special Interest Group on Embedded Systems / Special Interest Group on System Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グリッド分割を用いたイジングモデルによる巡回セールスマン問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving Traveling Salesman Problem Using Grid Partitioning via Ising-Model based Solver |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化問題 / Combinatorial optimization problem |
| キーワード(2)（和/英） | 巡回セールスマン問題 / traveling salesman problem |
| キーワード(3)（和/英） | イジングモデル / ising model |
| キーワード(4)（和/英） | アニーリング / annealing |
| キーワード(5)（和/英） | グリッド分割 / grid partitioning |
| 第 1 著者 氏名（和/英） | 党 璋 / Akira Dan |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 第 2 著者 氏名（和/英） | 西川 剛史 / Takeshi Nishikawa |
| 第 2 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 第 3 著者 氏名（和/英） | 佐藤 高史 / Takashi Sato |
| 第 3 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 発表年月日 | 2019-11-14 |
| 資料番号 | VLD2019-40,DC2019-64 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | VLD-282,DC-283 |
| ページ範囲 | pp.97-102(VLD), pp.97-102(DC), |
| ページ数 | 6 |
| 発行日 | 2019-11-06 (VLD, DC) |