切断面法

数学的最適化では、 切断面法は、 カットと呼ばれる線形不等式によって実行可能なセットまたは目的関数を繰り返し改良するさまざまな最適化方法のいずれかです。このような手順は、一般に、混合整数線形計画法（MILP）の問題に対する整数解を見つけるため、および必ずしも微分可能ではない一般的な凸最適化問題を解決するために使用されます。 MILPを解決するための切断面の使用は、Ralph E. Gomoryによって導入されました。

MILPの切断面法は、非整数線形プログラム、つまり指定された整数プログラムの線形緩和を解くことにより機能します。線形計画法の理論では、（線形プログラムに最適な解があり、実行可能領域に線が含まれていない場合）穏やかな仮定の下で、常に最適な極値点または角点を見つけることができると規定されています。得られた最適値は整数解であるかどうかがテストされます。そうでない場合、真の実行可能セットの凸包から最適を分離する線形不等式が存在することが保証されます。そのような不平等を見つけることは分離問題であり、そのような不平等はカットです。リラックスした線形プログラムにカットを追加できます。次に、現在の非整数解法は緩和に適さなくなります。このプロセスは、最適な整数解が見つかるまで繰り返されます。

一般的な凸連続最適化およびバリアントの切断面法は、さまざまな名前で知られています：ケリーの方法、ケリー-チェニー-ゴールドスタインの方法、およびバンドルの方法。これらは一般に、微分可能な凸最小化に使用されます。この場合、凸目的関数とその部分勾配は効率的に評価できますが、微分可能な最適化のための通常の勾配法は使用できません。この状況は、ラグランジアン双対関数の凹型最大化にとって最も典型的です。もう1つの一般的な状況は、Dantzig–Wolfe分解を構造化された最適化問題に適用することです。この場合、指数関数的な変数の定式化が得られます。遅延列生成を使用してこれらの変数をオンデマンドで生成することは、それぞれの二重問題で切断面を実行することと同じです。

ゴモリーのカット

切断面は、1950年代にRalph Gomoryによって、整数計画法と混合整数計画法の問題を解決する方法として提案されました。ただし、Gomory自身を含むほとんどの専門家は、数値の不安定性のために非実用的であると見なし、ソリューションに向けて前進するには多くのカットが必要だったため、効果的ではないと考えました。 1990年代半ばにジェラールコルヌエホルスと同僚が分岐限定（分岐限定と呼ばれる）および数値的不安定性を克服する方法と組み合わせて非常に効果的であることを示したとき、事態は好転しました。現在、すべての商用MILPソルバーは、何らかの方法でGomoryカットを使用しています。ゴモリーカットはシンプレックスタブローから非常に効率的に生成されますが、他の多くのタイプのカットは高価であるか、NPを分離するのが困難です。 MILPの他の一般的なカットの中でも、最も顕著なのは、リフトアンドプロジェクトがGomoryのカットを支配していることです。

整数計画問題を（標準形式で）定式化してみましょう：

cTxSubjectをAx = b、x≥0、xiすべての整数に最大化します。{\ displaystyle {\ begin {aligned} {\ text {Maximize}}＆c ^ {T} x \\ {\ text {Subject to}}＆Ax = b 、\\＆x \ geq 0、\、x_ {i} {\ text {すべての整数}}。\ end {aligned}}}

この方法では、まずxiが整数であるという要件を削除し、関連する線形計画問題を解いて基本的な実行可能なソリューションを取得します。幾何学的に、このソリューションは、すべての実行可能なポイントで構成される凸ポリトープの頂点になります。この頂点が整数点でない場合、メソッドは、頂点が一方にあり、実行可能なすべての整数点が他方にある超平面を見つけます。次に、これを追加の線形制約として追加して、見つかった頂点を除外し、修正線形プログラムを作成します。次に、新しいプログラムが解決され、整数解が見つかるまでプロセスが繰り返されます。

シンプレックス法を使用して線形プログラムを解くと、次の形式の方程式のセットが生成されます。

xi + ∑a¯i、jxj =b¯i{\ displaystyle x_ {i} + \ sum {\ bar {a}} _ {i、j} x_ {j} = {\ bar {b}} _ {i} }

ここで、 xiは基本変数、 xjは非基本変数です。整数部が左側に、小数部が右側になるように、この方程式を書き直します。

xi + ∑⌊a¯i、j⌋xj−⌊b¯i⌋ = b¯i−⌊b¯i⌋−∑（a¯i、j−⌊a¯i、j⌋）xj。{\ displaystyle x_ { i} + \ sum \ lfloor {\ bar {a}} _ {i、j} \ rfloor x_ {j}-\ lfloor {\ bar {b}} _ {i} \ rfloor = {\ bar {b}} _ {i}-\ lfloor {\ bar {b}} _ {i} \ rfloor-\ sum（{\ bar {a}} _ {i、j}-\ lfloor {\ bar {a}} _ {i 、j} \ rfloor）x_ {j}。}

実行可能領域内の整数ポイントの場合、この方程式の右辺は1未満で、左辺は整数です。したがって、共通値は0以下でなければなりません。したがって、不等式

b¯i−⌊b¯i⌋−∑（a¯i、j−⌊a¯i、j⌋）xj≤0{\ displaystyle {\ bar {b}} _ {i}-\ lfloor {\ bar { b}} _ {i} \ rfloor-\ sum（{\ bar {a}} _ {i、j}-\ lfloor {\ bar {a}} _ {i、j} \ rfloor）x_ {j} \ leq 0}

実行可能領域内の整数点を保持する必要があります。さらに、非基本変数は基本ソリューションで0に等しく、 xiが基本ソリューションxの整数でない場合、

b¯i−⌊b¯i⌋−∑（a¯i、j−⌊a¯i、j⌋）xj = b¯i−⌊b¯i⌋> 0。{\ displaystyle {\ bar {b}} _ {i}-\ lfloor {\ bar {b}} _ {i} \ rfloor-\ sum（{\ bar {a}} _ {i、j}-\ lfloor {\ bar {a}} _ {i 、j} \ rfloor）x_ {j} = {\ bar {b}} _ {i}-\ lfloor {\ bar {b}} _ {i} \ rfloor> 0。}

したがって、上記の不等式は基本的な実行可能なソリューションを除外しているため、望ましい特性を備えたカットです。この不等式のために新しいスラック変数xkを導入すると、新しい制約が線形プログラムに追加されます。つまり、

xk + ∑（⌊a¯i、j⌋−a¯i、j）xj = ⌊b¯i⌋−b¯i、xk≥0、xk整数。{\ displaystyle x_ {k} + \ sum（\ lfloor {\ bar {a}} _ {i、j} \ rfloor-{\ bar {a}} _ {i、j}）x_ {j} = \ lfloor {\ bar {b}} _ {i} \ rfloor -{\ bar {b}} _ {i}、\、x_ {k} \ geq 0、\、x_ {k} {\ mbox {an integer}}。}

凸最適化

切断面法は、非線形計画法にも適用できます。根底にある原則は、有限の閉半空間のセットによって非線形（凸）プログラムの実行可能領域を近似し、近似線形プログラムのシーケンスを解くことです。