LSIの配線問題 -DAシンポジウムの配線問題解法コンテスト-：4．整数計画法を用いた解法

情報処理学会 Web Site

書誌事項

タイトル別名
  • LSI Routing Problem - Routing Problem Solver Contest at DA Symposium -：4. Integer Programming Based Method
  • セイスウ ケイカクホウ オ モチイタ カイホウ

この論文をさがす

説明

本稿では, DAシンポジウムの配線問題解法コンテストの課題となった『LSIの配線問題』に対する, 整数計画法を用いた解法について記す. 本稿で記す解法は, 対象となる問題を0-1整数線形計画問題に定式化し, これを商用ソルバ（ソフトウェア）で解くというものである. 定式化においては, LSIの配線計画問題を無向グラフ上のパス集合を求める問題と捉え, これを表す0-1変数を導入し, 問題を表現する制約式を提案している. ソルバによる求解時間を短縮するために, 更に追加する制約式を提案し, その性能を計算機実験によって確認する.

収録刊行物

  • 情報処理

    情報処理 59 (3), 239-242, 2018-02-15

    情報処理学会

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ