単位立方体と切断面の交点x 1 + x 2 + x 3 ≥ 2 {\displaystyle x_{1}+x_{2}+x_{3}\geq 2} 数理 最適化 において、カッティングプレーン法とは、線形不等式（ カット と呼ばれる）を用いて実行可能集合 または目的関数を反復的に細分化する様々な最適化手法の総称である。このような手法は、混合整数線形計画問題（MILP）の 整数 解を求める場合や、必ずしも微分可能ではない一般的な凸最適化 問題を解く場合によく用いられる。カッティングプレーン法をMILPの解法として導入したのはラルフ・E・ゴモリー である。
混合整数線形計画問題（MILP）に対するカットプレーン法は、与えられた整数計画問題の線形緩和で ある非整数線形計画問題を解くことによって機能します。線形計画理論によれば、緩やかな仮定（線形計画問題に最適解が存在し、実行可能領域に直線が含まれていない場合）の下では、常に最適解となる極点または角点を見つけることができます。得られた最適解 が整数解であるかどうかをテストします。整数解でない場合、最適解を真の実行可能集合の凸包から 分離する 線形不等式が存在することが保証されます。このような不等式を見つけることが分離問題 であり、このような不等式がカット です。カットは緩和された線形計画問題に追加できます。すると、現在の非整数解は緩和に対して実行可能ではなくなります。このプロセスは、最適な整数解が見つかるまで繰り返されます。
一般的な凸連続最適化のための切断平面法とその変種は、ケリー法、ケリー・チェイニー・ゴールドスタイン法、バンドル法 など、さまざまな名称で知られています。これらは、凸目的関数とその劣勾配を 効率的に評価できるものの、微分可能な最適化のための通常の勾配法が使用できない非微分可能な凸最小化によく用いられます。このような状況は、ラグランジュ双対関数の凹最大化で最も典型的です。もう1つの一般的な状況は、 ダンツィヒ・ウォルフ分解 を構造化最適化問題に適用し、指数関数的に多くの変数を持つ定式化を得る場合です。遅延列生成 によってこれらの変数をオンデマンドで生成することは、対応する双対問題に対して切断平面法を実行することと同じです。
歴史 カットプレーンは、 1950年代にラルフ・ゴモリー によって整数計画問題と混合整数計画問題の解法として提案されました。しかし、ゴモリー自身を含むほとんどの専門家は、数値的不安定性のため、また解に近づくために多くのカットラウンドが必要となるため、非実用的であると考えていました。1990年代半ばにジェラール・コルヌジョル と共同研究者が、分岐限定法（分岐カットと呼ばれる）と組み合わせることで非常に効果的であり、数値的不安定性を克服する方法であることを示したことで、状況 は一変 しました。現在では、すべての商用MILPソルバーは何らかの形でゴモリーカットを使用しています。ゴモリーカットは単体タブローから非常に効率的に生成されますが、他の多くのタイプのカットは、分離にコストがかかるか、NP困難です。MILPの他の一般的なカットの中で、最も注目すべきはリフトアンドプロジェクションが ゴモリーカットを凌駕しています。[ 1 ] [ 2 ]
整数計画問題を（標準形式 で）次のように定式化する。
最大化する c T x 条件 A x ≤ b 、 x ≥ 0 、 x 私 すべての整数 。 {\displaystyle {\begin{aligned}{\text{最大化}}&c^{T}x\\{\text{制約条件}}&Ax\leq b,\\&x\geq 0,\,x_{i}{\text{すべての整数}}.\end{aligned}}} ここで、Aは行列、b、cはベクトルである。ベクトルxは未知であり、線形制約を満たしつつ目的関数を最大化するように求める必要がある。
概略 この手法では、まず x i が 整数であるという要件を削除し、関連する緩和線形計画問題を解いて基本的な実行可能解を取得します。幾何学的には、この解はすべての実行可能点からなる凸多面体の頂点になります。この頂点が整数点でない場合、この手法では、頂点を片側に、すべての実行可能な整数点をもう片側に持つ超平面を見つけます。次に、この超平面を、見つかった頂点を除外するための追加の線形制約として追加し、修正された線形計画を作成します。新しい計画を解き、整数解が見つかるまでこのプロセスを繰り返します。
ステップ2：線形制約を見つける ここで基本的な変数を考えてみましょう。x 私 {\displaystyle x_{i}}
x 私 + ∑ j ⌊ 1 ¯ 私 、 j ⌋ x j − ⌊ b ¯ 私 ⌋ = b ¯ 私 − ⌊ b ¯ 私 ⌋ − ∑ j （ 1 ¯ 私 、 j − ⌊ 1 ¯ 私 、 j ⌋ ） x j 。 {\displaystyle x_{i}+\sum _{j}\lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}.} 実行可能領域内の任意の整数点に対して、すべての項が整数であるため、左辺は整数になります。x 私 {\displaystyle x_{i}} x j {\displaystyle x_{j}} ⌊ 1 ¯ 私 、 j ⌋ {\displaystyle \lfloor {\bar {a}}_{i,j}\rfloor } ⌊ b ¯ 私 ⌋ {\displaystyle \lfloor {\bar {b}}_{i}\rfloor } b ¯ 私 − ⌊ b ¯ 私 ⌋ {\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor } − ∑ j （ 1 ¯ 私 、 j − ⌊ 1 ¯ 私 、 j ⌋ ） x j {\displaystyle -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}
b ¯ 私 − ⌊ b ¯ 私 ⌋ − ∑ j （ 1 ¯ 私 、 j − ⌊ 1 ¯ 私 、 j ⌋ ） x j ≤ 0 {\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0} 実行可能領域内の任意の整数点に対して成り立つ必要があります。さらに、非基本変数は任意の基本解で0に等しく、基本解xに対して x iが 整数でない場合、
b ¯ 私 − ⌊ b ¯ 私 ⌋ − ∑ j （ 1 ¯ 私 、 j − ⌊ 1 ¯ 私 、 j ⌋ ） x j = b ¯ 私 − ⌊ b ¯ 私 ⌋ > 0. {\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor >0.}
結論 したがって、上記の不等式は基本的な実行可能解を除外し、したがって望ましい特性を持つカットとなります。より正確には、b ¯ 私 − ⌊ b ¯ 私 ⌋ − ∑ j （ 1 ¯ 私 、 j − ⌊ 1 ¯ 私 、 j ⌋ ） x j {\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}} k を導入すると、線形計画に新しい制約が追加される。
x k + ∑ j （ ⌊ 1 ¯ 私 、 j ⌋ − 1 ¯ 私 、 j ） x j = ⌊ b ¯ 私 ⌋ − b ¯ 私 、 x k ≥ 0 、 x k 整数 。 {\displaystyle x_{k}+\sum _{j}(\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}}.}
参考文献 ↑ Gilmore, Paul C; Gomory, Ralph E (1961). "切削在庫問題に対する線形計画法アプローチ". Operations Research . 9 (6): 849– 859. doi : 10.1287/opre.9.6.849 . ↑ Gilmore, Paul C; Gomory, Ralph E (1963). "切削在庫問題に対する線形計画法アプローチ - パート II". Operations Research . 11 (6): 863– 888. doi : 10.1287/opre.11.6.863 . ↑ Boyd, S.; Vandenberghe, L. (2003年9月18日). 「局所化と切断平面法」 (講義ノート) . 2022年 5月27日 取得 。 Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002). "整数計画法および混合整数計画法における切断平面" . Discrete Applied Mathematics . 123 ( 1– 3): 387– 446. doi : 10.1016/s0166-218x(01)00348-1 . アヴリエル、モルデカイ（2003）。非線形計画法：分析と手法。 ドーバー出版。ISBN 0-486-43227-0 Cornuéjols, Gérard (2008). 混合整数線形計画問題に対する有効な不等式. Mathematical Programming Ser. B , (2008) 112:3–44. Cornuéjols, Gérard (2007). 1990年代におけるゴモリー・カットの復活。Annals of Operations Research 、第149巻（2007年）、63-66ページ 。
外部リンク 「整数計画法」第9.8節 応用数理計画法 第9章 整数計画法（全文）。Bradley、Hax、Magnanti著（Addison-Wesley、1977年） 「線形整数計画問題に対するゴモリーカットの生成：方法と理由」線形整数計画問題に対するゴモリーカットの生成：方法と理由
