2次割当問題

提供: ORWiki
2007年7月17日 (火) 16:17時点における122.17.2.240 (トーク)による版
ナビゲーションに移動 検索に移動

【にじわりあてもんだい (quadratic assignment problem (QAP))】

目的関数が2次式となる割当問題のこと. 設置予定の工場とその場所候補が与えられており, 工場, 間の輸送量が, 場所, 間の距離がとするとき, 輸送の量と距離の積の総和を最小化する問題は, に設置する際に1となる0-1変数 を導入すると, 割当問題の制約に対して目的関数は2次式となる. 巡回セールスマン問題や施設配置問題などの多くのNP困難な問題が, 2次割当問題に帰着できる.