LSI Routing Problem - Routing Problem Solver Contest at DA Symposium -：4. Integer Programming Based Method

IPSJ Web Site

Bibliographic Information

Other Title
  • LSIの配線問題 -DAシンポジウムの配線問題解法コンテスト-：4．整数計画法を用いた解法
  • セイスウ ケイカクホウ オ モチイタ カイホウ

Search this article

Description

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

Journal

  • 情報処理

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

    情報処理学会

Keywords

Details 詳細情報について

Report a problem

Back to top