切除平面法

単位立方体と切除平面 $x_1+x_2+x_3\ge 2$ の交差を表した図。この図がグラフに関する問題で変数が3つの頂点に対応する場合、3つの頂点のうち少なくとも2つの頂点は選択されることを表している。

切除平面法（せつじょへいめんほう、テンプレート:Lang-en-short）とは、数理最適化において線形不等式（カット、切除平面と呼ばれる）を反復的に生成して実行可能解集合や目的関数を改善する最適化手法である。主に混合整数線形計画問題（MILP）の最適解を求める、あるいは微分可能でない凸最適化問題を解くために用いられる解法である。ラルフ・ゴモリーによってMILPに対する切除平面法が提案された。

MILPに対する切除平面法は、与えられた整数計画問題の線形計画緩和問題（整数計画問題の制約から整数条件を除いた問題）を解くことから始める。線形計画法の理論によれば、弱い仮定の下（線形計画問題が最適解を持ち、退化していない場合）では、常にある一つの端点（多面体の頂点）が最適解となることが知られている。得られた最適解が整数条件を満たすものかを検証し、整数解でなければ、その最適解と実行可能集合の凸包とを分離する分離超平面（線形不等式、妥当不等式）が存在して、これを生成する。このような不等式を見つける問題は分離問題（separation problem）と呼ばれおり、求めた不等式を線形緩和問題の制約に追加する。結果として、現在の最適解は緩和問題の実行可能解ではなくなる。この手続きを繰り返すことで最終的に整数条件を満たす解を求める。

一般の凸連続最適化に対する切除平面法は、主にKelley法、Kelley–Cheney–Goldsteinの外部近似法、バンドル法などの名称で知られている。特に微分不可能凸最小化に用いられ、凸目的関数であり劣勾配が効率的に求められるが、微分可能な凸最適化問題に対する劣勾配法が適用できない問題に対して有効である。このような事象は、ラグランジュ双対関数の凹最大化に見られる。また、特殊な構造を持つ最適化問題に対してテンプレート:仮リンクを適用した場合、元の問題は変数が指数倍となる問題に変換される。この問題に対し遅延列生成法によって変数を生成する手続きは、Dantzig–Wolfe分解後の問題に対応する双対問題に対して切除平面法での妥当不等式を生成する手続きに対応している。

歴史

切除平面法は、1958年に整数計画問題に対する小数カットがラルフ・ゴモリーによって提案されたテンプレート:Sfn。しかし、ゴモリーを含めた多くの専門家は、初期の切除平面法は数値誤差が発生しやすい不安定性と、最適解が求まるまでにかかる反復回数が非常に多くかかることから、実用的な解法ではないと考えられたテンプレート:Sfn。しかし、1990年代半ばに Gérard Cornuéjols らが、切除平面法と分枝限定法を組み合わせた分枝カット法を提案、非常に効果的な解法であることを示し、不安定性も解消されたことで状況が一変した。現在では、主な商用のMILPソルバーは何らかの方法で切除平面法を実装している。ゴモリーの小数カットは単体法で用いられる単体表から効率的に生成できるが、他の多くのカットは計算コストが高く、また分離問題がNP困難となるものもある。他のMILPに対するカットの中でも、テンプレート:仮リンクらのlift-and-projectカットはゴモリーの小数カットよりも早く最適解に収束する解法であるとされている。

ゴモリーの小数カット

以下の整数計画問題（基準形）について考える:

$\begin{array}{cc}\text{Maximize }& c^{T}x\\ \text{Subject to }& Ax\le b,\\ & x\ge 0,x_i\in Z_{+}.\end{array}$

ここで A は行列であり、b, c はベクトルである。線形制約を満たしつつ目的関数が最大となるベクトル x を求める。

基本的なアイデア

この手法は、初めに変数 x_i に対する整数条件を除去した線形計画緩和問題を解いて最適基底解を求める。幾何学的には、線形計画緩和問題の解はすべての実行可能点からなる凸多面体の頂点となる。もし最適基底解が整数条件を満たさなければ、片側が最適基底解、もう片方が元の問題の実行可能集合に分離されるような超平面を求める。この超平面を追加の線形制約として導入し、得られた線形計画緩和問題の最適解を除外していくことで新たな線形計画問題が生成される。続いて新たな線形計画問題を解き新たな最適基底解を求める。これらの手続きを繰り返し、整数条件を満たす最適解が有限の反復で得られる。

ステップ1: 線形計画緩和問題を解く

線形計画問題に対して単体法によって以下のような式の集合を求める:

$x_i+\sum _j{\overline{a}}_{i,j}{x}_j={\overline{b}}_i$

ここで x_i は基底変数であり、x_j は非基底変数である（線形計画緩和問題の最適値は$x_i={\overline{b}}_i$であり、$x_j=0$である）。各制約に対応する係数を ${\overline{b}}_i$および${\overline{a}}_{i,j}$ として単体法の手順を記述する。これらの係数は行列 A およびベクトル b とは異なることに注意する。

ステップ2: 妥当不等式を求める

基底変数の中から整数でない $x_i$ を一つ選ぶ。続いて各係数を整数部分と小数部分に分解し、左辺に整数の項を右辺に小数の項の式へと書き換える:

$x_i+\sum _j\lfloor {\overline{a}}_{i,j}\rfloor x_j-\lfloor {\overline{b}}_i\rfloor ={\overline{b}}_i-\lfloor {\overline{b}}_i\rfloor -\sum _j({\overline{a}}_{i,j}-\lfloor {\overline{a}}_{i,j}\rfloor )x_j.$

実行可能領域では整数点をとるため、左辺の $x_i$, $x_j$, $\lfloor {\overline{a}}_{i,j}\rfloor$ は整数値をとる。一方、右辺は ${\overline{b}}_i-\lfloor {\overline{b}}_i\rfloor$ は小数値であることから1より小さい値となり、$-\sum _j({\overline{a}}_{i,j}-\lfloor {\overline{a}}_{i,j}\rfloor )x_j$ に関しても、${\overline{a}}_{i,j}-\lfloor {\overline{a}}_{i,j}\rfloor$、$x_j$が非負の値であることから負の値をとり、厳密に1より小さい値をとる。それゆえ各辺の値はいかなる場合でも 0 以下の値をとる。このことから以下の不等式が導かれ:

${\overline{b}}_i-\lfloor {\overline{b}}_i\rfloor -\sum _j({\overline{a}}_{i,j}-\lfloor {\overline{a}}_{i,j}\rfloor )x_j\le 0$

実行可能領域では整数点に対応しなければならない。加えて、非基底変数は基底解において常に 0 をとるため、もし基底解 x の基底変数 x_i が整数値でない場合は、

${\overline{b}}_i-\lfloor {\overline{b}}_i\rfloor -\sum _j({\overline{a}}_{i,j}-\lfloor {\overline{a}}_{i,j}\rfloor )x_j={\overline{b}}_i-\lfloor {\overline{b}}_i\rfloor >0.$

となる。

結論

このことから、求まった不等式は線形計画緩和問題の最適解に関しては成り立たないものであり、なおかつ元の問題の実行可能集合は不等式を満たすものであることから、小数カットはこれらを分離する超平面（半空間）としての役割を果たす。より具体的には、不等式 ${\overline{b}}_i-\lfloor {\overline{b}}_i\rfloor -\sum _j({\overline{a}}_{i,j}-\lfloor {\overline{a}}_{i,j}\rfloor )x_j$ は実行可能領域の整数点に対しては 0 以下の値をとり、線形計画緩和問題の最適基底解は厳密に正の値（整数値とは限らない）をとる。新たに生成された不等式制約にスラック変数 $x_k$ を導入し、制約式:

$x_k+\sum _j(\lfloor {\overline{a}}_{i,j}\rfloor -{\overline{a}}_{i,j})x_j=\lfloor {\overline{b}}_i\rfloor -{\overline{b}}_i,x_k\ge 0,x_k\text{ an integer}.$

を線形計画問題の制約に付け加える。

凸最適化

切除平面法は非線形計画問題に対しても適用することができる。基本的な原理として、実行可能領域を有限個の閉半空間で近似し、逐次近似された線形計画問題を解くことで非線形（凸）計画問題を解いている。

参考文献

• テンプレート:Cite journal
• テンプレート:Cite journal
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publications. テンプレート:ISBN
• Cornuéjols, Gérard (2008). Valid Inequalities for Mixed Integer Linear Programs. Mathematical Programming Ser. B, (2008) 112:3–44.
• Cornuéjols, Gérard (2007). Revival of the Gomory Cuts in the 1990s. Annals of Operations Research, Vol. 149 (2007), pp. 63–66.

関連項目

• ベンダーズ分解法
• 分枝カット法
• 分枝限定法
• 列生成法
• テンプレート:仮リンク

外部リンク

• "Integer Programming" Section 9.8 Applied Mathematical Programming Chapter 9 Integer Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977)