文献

J-GLOBAL ID：201902252755392198   整理番号：19A0961606

実イジング計算機による制約付きスロット配置問題の解法

著者 (5件)： 金丸翔 (早稲田大 大学院基幹理工学研究科) ,  川村一志 (早稲田大 基幹理工) ,  田中宗 (早稲田大 グリーン・コンピューティング・システム研究機構) ,  田中宗 (JST-さきがけ) ,  戸川望 (早稲田大 大学院基幹理工学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2019  号： ARC-235  ページ： Vol.2019-ARC-235,No.52,1-6 (WEB ONLY)  発行年： 2019年03月10日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： イジング計算機は組合せ最適化問題を物理システムにマッピングすることで,組合せ最適化問題の準最適解を高速に得ることができるとして注目されている.スロット配置問題は論理ブロックの最適配置や最適配送決定において重要な役割を果たす組合せ最適化問題である.本研究では,スロット配置問題に制約条件を付加した問題をイジング計算機によって効率よく解法する手法を提案する.イジング計算機でこの問題を解法するため,この問題をイジングモデルで表現する.まず,スロット配置問題をイジングモデルの状態空間で表現する際に満足すべき制約条件が満たされているとき,イジングモデルのエネルギーが最小となる制約項を導入する.この制約をスロット配置制約と呼ぶ.また,今回は付加する制約条件として,特定の部品が一定の距離以内に置かれなければならない,というものを考える.この制約を違反したときにエネルギーが大きくなる付加制約項を導入する.この制約を付加制約と呼ぶ.更に,配置された部品間の配線数とマンハッタン距離の加重和である目的関数項をイジングモデルで表現する.また,イジング計算機によって得られた解に対し,解釈処理なるアイデアを導入することで,スロット配置制約を満たさない解が得られたとしても,スロット配置制約を満たす解に解釈し直す手法を提案する.デジタルアニーラを利用し,単純なSA手法とデジタルアニーラで比較した結果,制約付きスロット配置問題において,SAと同程度の精度の準最適解を得るのに必要なデジタルアニーラの時間が最大で約1/50に圧縮することができた.(著者抄録)

シソーラス用語： コンピュータ ,  *計算機アーキテクチャ ,  *組合せ最適化問題 ,  配置問題 ,  割当問題 ,  Ising模型 ,  シミュレーテッドアニーリング ,  制約条件 ,  解法 ,  目的関数 ,  定式化 ,  評価試験 ,  ハミルトニアン ,  アルゴリズム ,  写像
準シソーラス用語： *イジング計算機 ,  スロット配置問題 ,  デジタルアニーラ ,  マッピング ,  二次割当問題

分類 (2件)： ディジタル計算機方式一般  (JC02010O) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (12件)：

• Johnson, M., Amin, M., Gildert, S., Lanting, T., Hamze,F., Dickson, N., Harris, R., Berkley, A., Johansson,J., Bunyk, P., Chapple, E., Enderud, C., Hilton, J.,Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Per-minov, I., Rich, C., Thom, M., Tolkacheva, E., Truncik,C., Uchaikin, S., Wang, J., Wilson, B. and Rose, G.:Quantum annealing with manufactured spins, Nature, Vol. 473, No. 7346, pp. 194-198 (2011).
• Yamaoka, M., Yoshimura, C., Hayashi, M., Okuyama,T., Aoki, H. and Mizuno, H.: A 20k-spin Isingchip to solve combinatorial optimization problems withCMOS annealing, IEEE Journal of Solid-State Circuits, Vol. 51, No. 1, pp. 303-309 (2016).
• Tsukamoto, S., Takatsu, M., Matsuba, S. and Tamura, H.: An accelerator architecture for combinatorial optimization problems, Fujitsu Scientific & Technical Journal, Vol. 53, No. 5, pp. 8-13 (2017).
• Utsunomiya, S., Takata, K. and Yamamoto, Y.: Mapping of Ising models onto injection-locked laser systems, Opt. Express, Vol. 19, No. 19, pp. 18091-18108 (2011).
• Yoshimura, C., Hayashi, M., Okuyama, T., and Yamaoka M.: FPGA-based annealing processor for Ising model, Proc. 2016 Fourth International Symposium on Computing and Networking (CANDAR), pp. 436-442 (2016).

タイトルに関連する用語 (5件)： 計算機 ,  制約 ,  スロット ,  配置問題 ,  解法