2020年7月20日~7月24日にThe 57th ACM/IEEE Design Automation Conference (DAC) 2020 にて本研究室修了生の党が研究発表を行いました (発表日は7月25日).DACは,集積回路設計におけるトップ会議であることに加え,今年は新型コロナウィルスの影響により完全virtual会議となったことから,例年にも増して多数の参加者がありました.
党の発表は,組合せ最適化問題として広く知られているトラベリングセールスマン問題(TSP)をイジングモデルソルバを用いて解く際の,計算の高速化に関するものです.イジングモデルとは,近傍と相互作用を持つスピンにより磁性体の性質を模したモデルであり,様々な最適化問題を高並列かつ高速に解ける可能性があることから最近注目されています.ただしTSPのように,最適化問題をイジングモデルにマッピングする際に,多くの(TSPの場合は全ての)スピン間の相互作用を考慮する必要がある場合には,解の質が十分でなく,また多数の相互作用を考慮して計算を進めるために,計算時間も多く必要とする課題がありました.本論文では,TSPにおいて遠方の都市間の移動は最短経路を求める際には考慮する必要がないという性質に着目して,都市を再帰的にクラスタリングしながらイジングモデルソルバで訪問経路を求める手法を提案しています.スピン間の相互作用を減らすことにより,TSPの解の質を向上し,また計算を高速に行うことができることを示しています.
- Akira Dan, Riu Shimizu, Takeshi Nishikawa, Song Bian and Takashi Sato, “Clustering approach for solving traveling salesman problems via Ising model based solver,” in Proc. ACM/IEEE Design Automation Conference (DAC), pp.26.1:1-26.1:6, July 2020.