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