整数計画法

変数が整数値しか取れない線形計画。Integer Programming、IP。 すべての変数が整数なら IP、一部だけなら混合整数計画 (MIP)。

$$\underset{x}{\min }{c}^{\top }x\text{s.t.}Ax\le b,x\in {\mathbb{Z}}^n$$

なぜ急に難しくなるのか#

LP は多項式時間で解けるのに、 整数条件を足しただけで NP 困難になる。 実行可能領域が連続な多面体ではなく、飛び飛びの格子点になるため、 「頂点を辿れば最適解に届く」という性質が失われる。

$0$-$1$ 変数を使えば「選ぶ / 選ばない」を表現できるので、 組合せ最適化の多くが MIP として書ける。 表現力の高さと難しさは表裏一体。

解き方#

分枝限定法 (branch and bound) が基本。 Land と Doig が 1960 年に提案した。

1. 整数条件を外して LP として解く（連続緩和）
2. 解が整数ならそれが最適解
3. 整数でない変数 $x_i=2.4$ があれば、 $x_i\le 2$ と $x_i\ge 3$ の 2 つの部分問題に分ける（分枝）
4. 各部分問題の緩和解が、既知の最良解より悪ければその枝を捨てる（限定）

限定によって探索木の大部分を刈れるかどうかが実用性を決める。 切除平面法 (cutting plane) と組み合わせた branch and cut が現代のソルバの主流。

参考文献#

• Ailsa H. Land, Alison G. Doig. An Automatic Method of Solving Discrete Programming Problems. Econometrica 28(3), 1960. https://doi.org/10.2307/1910129
• Laurence A. Wolsey. Integer Programming, 2nd ed. Wiley, 2020. https://doi.org/10.1002/9781119606475