2次割当問題

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

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