二次割当問題

二次割当問題の定義は以下の通りである:

今、同じサイズの二つの集合 P（施設）および L（候補地）が与えられたとする。ここに重み関数（英語版） w: P x P → R、および距離関数 d: L x L → R が与えらえる。二次割当問題は次の式を最小とするような全単射 f: P → L を求める問題である:

最小化: ${\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))}$

重みや距離は通常実数値の行列として与えられるため、その場合、上記の式は以下の通りに書き表される:

${\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}$

行列表記にすると:

${\displaystyle \min _{X\in \Pi _{n}}\operatorname {trace} (WXD^{T}X^{T})}$

ただし、${\displaystyle \Pi _{n}}$ は ${\displaystyle n\times n}$ の置換行列であり、${\displaystyle W}$ は重み行列であり、${\displaystyle D}$ は距離行列である。

二次割当問題はNP困難として知られているため、現時点では時間計算量の観点から最適解を効率よく求めるようなアルゴリズムは発見されておらず、規模が小さな問題でさえ最適解を求めるのに時間がかかることが多い。またP=NPでない限り、任意の（定数）係数に対して多項式時間の近似アルゴリズムが存在しないことも証明されている^[2]。巡回セールスマン問題（TSP）は二次割当問題において施設間のフローをある一つのサイクル上のみフロー1と設定し、それ以外のフローは0として与え、各候補地間の距離を巡回セールスマン問題での各都市間の距離として設定した特殊な問題としてみなすことができる。このように多くの組合せ最適化問題は二次割当問題の形式として扱うことができる。

二次割当問題は元々考えられた工場の割当を決定するような問題に加えて、エレクトロニクス産業のCADにおける配置・配線（英語版）の部分に相当するプリント基板や集積回路状における最適な電子部品の配置を決定する数理モデルとして活用することができる。

また、二次割当問題はキーボード上での最適な文字の配置をモデル化するためにも用いられている。この場合、位置はキーボード上のキーに相当し、各キーの組ごとの距離はそれらのキーを打鍵するのに必要な時間に対応する。一方で施設に対応するのは文字であり、各文字の重みはテキストコーパスにおいて各二組の文字の出現頻度に比例した値となる。最適キーボード設計問題における二次割当問題によるモデル化はフランスのキーボード標準（NF Z71-300）の設計において用いられた^[3]。