文献

J-GLOBAL ID：201202263781218780   整理番号：12A1359289

二次割当問題に関する3つのアイデア

Three Ideas for the Quadratic Assignment Problem

著者 (3件)： FISCHETTI Matteo (Univ. Padova, Padova, ITA) ,  MONACI Michele (Univ. Padova, Padova, ITA) ,  SALVAGNIN Domenico (Univ. Padova, Padova, ITA)
資料名： Operations Research  (Operations Research)
巻： 60  号： 4  ページ： 954-964  発行年： 2012年07月 
JST資料番号： D0249A  ISSN： 0030-364X  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Eschermann等(1990)によって導入された2次割当問題の困難な事例(”escインスタンス”)に関する解法を考察した。具体的には,その解法に関する3つのアイデアについて述べた上で,それらが解法に与える効果を論じた。それらのアイデアには,1)対象性の利用,2)混合整数線形モデルとアルゴリズム,3)ファシリティフロー分割スキームが含まれる。また,単一のPCを用いた数値計算の結果を示した。簡単な事例(esc16*,esc32e,esc32g)に関しては,数秒あるいは数分で解を算出できる。非常に難しい事例(esc32c,esc32d,esc64a)に関しては,30分以内,tai64cに関しては,5時間程度で解を算出できる。さらに,ファシリティフロー分割スキームによって,esc32hやesc128を最適に解くことができる。

シソーラス用語： *割当問題 ,  線形計画法 ,  *整数計画法 ,  対称性 ,  アルゴリズム ,  分枝限定法 ,  CPU時間 ,  NP困難 ,  組合せ最適化問題
準シソーラス用語： 二次割当問題 ,  計算時間 ,  混合整数線形計画法 ,  分枝限定アルゴリズム

分類 (1件)： 数理計画法  (KA03030M)

タイトルに関連する用語 (2件)： 二次割当問題 ,  アイデア