バイナリ制約

数学的最適化におけるバイナリ制約は、正確に 2 つの変数を含む制約です。

たとえば、nクイーン問題を考えてみましょう。この問題の目的は、n x n のチェス盤にn 個の チェスクイーンを配置し、どのクイーンも (水平、垂直、斜めに) 互いに攻撃できないようにすることです。したがって、正式な制約セットは、すべてのクイーンのペア間で「クイーン 1 はクイーン 2 を攻撃できない」、「クイーン 1 はクイーン 3 を攻撃できない」などとなります。この問題の各制約はバイナリであり、2 つの個別のクイーンの配置のみを考慮します。^[1]

すべての制約が2項である線形計画法は強多項式時間で解くことができるが、この結果はより一般的な線形計画法では成り立たないことが知られている。^[2]

参考文献

^ マリオット、キム、スタッキー、ピーター J. (1998)、制約付きプログラミング: 入門、MIT プレス、p. 282、ISBN 9780262133418。
^ Megiddo, Nimrod (1983)、「線形計画法のための真に多項式なアルゴリズムに向けて」、SIAM Journal on Computing、12 (2): 347–353、CiteSeerX 10.1.1.76.5、doi :10.1137/0212022、MR 0697165 。

[1] マリオット、キム、スタッキー、ピーター J. (1998)、制約付きプログラミング: 入門、MIT プレス、p. 282、ISBN 9780262133418。

[2] Megiddo, Nimrod (1983)、「線形計画法のための真に多項式なアルゴリズムに向けて」、SIAM Journal on Computing、12 (2): 347–353、CiteSeerX 10.1.1.76.5、doi :10.1137/0212022、MR 0697165 。