二次割当問題とは？わかりやすく解説

二次割当問題（にじわりあてもんだい、英: quadratic assignment problem、略称：QAP）とは、数学の数理最適化やオペレーションズ・リサーチにおける組合せ最適化問題の一種である。クープマンスおよびベックマンにより初めて考案された施設配置問題（英語版）に由来する問題である^[1]。

二次割当問題は以下のような事例に対するモデルを扱う:

今、

n

個の建設予定の施設および

n

個の候補地がある。各二つの候補地間にはそれぞれ距離が設定され、各施設間にはそれぞれフロー（重み）が設定されている（フローの例は各施設間どうしで運ばなければならない物資の量など）。二次割当問題は各施設間のフローが候補地間どうしの距離に応じた費用がかかるとしたときに、それらの費用の合計が最小に抑えられるようなそれぞれ異なった候補地に各施設を建設する割当を決定する問題である。

直感的には、ある施設間でのフローが大きいものは距離の近い候補地にそれぞれ配置することが求められる。

二次割当問題は割当問題（英語版）と類似した問題のように思われるが、二次割当問題は目的関数（最適にしたい事柄）が二次の項で表現されることが割当問題とは異なった問題として扱われる。このことは二次割当問題の名称に二次が入っていることにも表れている。

厳密な定義

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

今、同じサイズの二つの集合

P

（施設）および

L

（候補地）が与えられたとする。ここに重み関数（英語版）

w : P x P \to R

、および距離関数

d : L x L \to R

が与えらえる。二次割当問題は次の式を最小とするような全単射

f : P \to L

を求める問題である:

最小化:

\sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))

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

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

行列表記にすると:

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

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

計算複雑性

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

応用

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

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

脚注

[脚注の使い方]

^ Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76
^ Sahni, Sartaj; Gonzalez, Teofilo (July 1976). “P-Complete Approximation Problems”. Journal of the ACM 23 (3): 555–565. doi:10.1145/321958.321975. hdl:10338.dmlcz/103883. ISSN 0004-5411.
^ John, Maximilian; Karrenbauer, Andreas (2019). “Dynamic Sparsification for Quadratic Assignment Problems”. Mathematical Optimization Theory and Operations Research. 11548. Cham: Springer International Publishing. p. 232–246. doi:10.1007/978-3-030-22629-9_17. ISBN 978-3-030-22628-2. オリジナルの2025-01-16時点におけるアーカイブ。

参考文献

Michael R. Garey; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5 A2.5: ND43, pg.218.

外部リンク

QAPLIB - 二次割当問題のライブラリ
MAOS-QAP - Javaベースの二次割当問題ソルバ
R package qap: 二次割当問題に対する発見的解法
QAPソルバ - Windows10,11で使用できるメタヒューリスティックQAPソルバ

[1] Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76

[2] Sahni, Sartaj; Gonzalez, Teofilo (July 1976). “P-Complete Approximation Problems”. Journal of the ACM 23 (3): 555–565. doi:10.1145/321958.321975. hdl:10338.dmlcz/103883. ISSN 0004-5411.

[3] John, Maximilian; Karrenbauer, Andreas (2019). “Dynamic Sparsification for Quadratic Assignment Problems”. Mathematical Optimization Theory and Operations Research. 11548. Cham: Springer International Publishing. p. 232–246. doi:10.1007/978-3-030-22629-9_17. ISBN 978-3-030-22628-2. オリジナルの2025-01-16時点におけるアーカイブ。

[1]

[2]

[3]

二次割当問題とは？ わかりやすく解説