切除平面法のソースを表示

[[File:TSP cutting plane.png|thumb|単位立方体と切除平面 <math>x_1 + x_2 + x_3 \geq 2</math> の交差を表した図。この図がグラフに関する問題で変数が3つの頂点に対応する場合、3つの頂点のうち少なくとも2つの頂点は選択されることを表している。]]

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

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

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

== 歴史 ==
切除平面法は、1958年に整数計画問題に対する小数カットが[[ラルフ・E・ゴモリー|ラルフ・ゴモリー]]によって提案された{{sfn|藤江哲也|2003|p=771}}。しかし、ゴモリーを含めた多くの専門家は、初期の切除平面法は数値誤差が発生しやすい不安定性と、最適解が求まるまでにかかる反復回数が非常に多くかかることから、実用的な解法ではないと考えられた{{sfn|藤江哲也|2003|pp=771-772}}。しかし、1990年代半ばに Gérard Cornuéjols らが、切除平面法と[[分枝限定法]]を組み合わせた[[分枝カット法]]を提案、非常に効果的な解法であることを示し、不安定性も解消されたことで状況が一変した。現在では、主な商用のMILPソルバーは何らかの方法で切除平面法を実装している。ゴモリーの小数カットは単体法で用いられる単体表から効率的に生成できるが、他の多くのカットは計算コストが高く、また分離問題がNP困難となるものもある。他のMILPに対するカットの中でも、{{仮リンク|エゴン・バラス|en|Egon Balas}}らのlift-and-projectカットはゴモリーの小数カットよりも早く最適解に収束する解法であるとされている<ref>{{cite journal |title=A linear programming approach to the cutting stock problem |first1=Paul C |last1=Gilmore |first2=Ralph E |last2=Gomory |journal=Operations Research |year=1961 |pages=849–859 |volume=9 |issue=6 |doi=10.1287/opre.9.6.849 }}</ref><ref>{{cite journal |title=A linear programming approach to the cutting stock problem-Part II |first1=Paul C |last1=Gilmore |first2=Ralph E |last2=Gomory |journal=Operations Research |year=1963 |pages=863–888 |volume=11 |issue=6 |doi=10.1287/opre.11.6.863 }}</ref>。

== ゴモリーの小数カット ==
以下の整数計画問題（[[整数計画問題#整数計画問題の基準形と標準形|基準形]]）について考える:

: <math>\begin{align}
\text{Maximize  } & c^Tx \\
\text{Subject to  } & Ax \leq b, \\
 & x\geq 0,\, x_i \in Z_{+}.
\end{align}
</math>
ここで A は行列であり、b, c はベクトルである。線形制約を満たしつつ目的関数が最大となるベクトル x を求める。

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

=== ステップ1: 線形計画緩和問題を解く ===
線形計画問題に対して[[単体法]]によって以下のような式の集合を求める: 

:<math>x_i+\sum_j \bar a_{i,j}x_j=\bar b_i</math>

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

=== ステップ2: 妥当不等式を求める ===
基底変数の中から整数でない <math>x_i</math> を一つ選ぶ。続いて各係数を整数部分と小数部分に分解し、左辺に整数の項を右辺に小数の項の式へと書き換える:

:<math>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.</math>

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

:<math>\bar b_i - \lfloor \bar b_i \rfloor - \sum_j ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j \le 0</math>

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

:<math>\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.</math>

となる。

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

:<math>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 \ge 0,\, x_k \mbox{ an integer}.</math>

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

== 凸最適化 ==
切除平面法は[[非線形計画問題]]に対しても適用することができる。基本的な原理として、[[実行可能領域]]を有限個の閉半空間で近似し、逐次近似された[[線形計画問題]]を解くことで非線形（凸）計画問題を解いている<ref>{{cite web |last1=Boyd |first1=S. |last2=Vandenberghe |first2=L. |title=Localization and Cutting-plane Methods |url=https://web.stanford.edu/class/ee392o/localization-methods.pdf |access-date=2022-05-27 |format=講義資料 |date=2003-09-18}}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
*{{Cite journal |和書 |author=藤江哲也 |year=2003 |title=混合整数計画問題に対する分枝カット法 |journal=計測と制御 |publisher=計測自動制御学会 |volume=42 |issue=9 |pages=770-775 |issn=1883-8170 |doi=10.11499/sicejl1962.42.770 |ref=harv }}
*{{cite journal |title=Cutting planes in integer and mixed integer programming |first1=Hugues |last1=Marchand |first2=Alexander |last2=Martin |first3=Robert
 |last3=Weismantel |first4=Laurence |last4=Wolsey |journal=Discrete Applied Mathematics |year=2002 |pages=387–446 |volume=123 |issue=1–3 |doi=10.1016/s0166-218x(01)00348-1 |doi-access=free }}
*Avriel, Mordecai (2003). ''Nonlinear Programming: Analysis and Methods.'' Dover Publications. {{ISBN|0-486-43227-0}}
*[[:en:Gérard Cornuéjols|Cornuéjols, Gérard]] (2008).  [http://integer.tepper.cmu.edu/webpub/integerRioMPSjuly.pdf Valid Inequalities for Mixed Integer Linear Programs].  ''Mathematical Programming Ser. B'', (2008) 112:3–44.
*[[:en:Gérard Cornuéjols|Cornuéjols, Gérard]] (2007).  [http://integer.tepper.cmu.edu/webpub/gomory.pdf Revival of the Gomory Cuts in the 1990s].  ''Annals of Operations Research'', Vol. 149 (2007), pp.&nbsp;63–66.

== 関連項目 ==
*[[ベンダーズ分解法]]
*[[分枝カット法]]
*[[分枝限定法]]
*[[列生成法]]
*{{仮リンク|Dantzig–Wolfe分解法|en|Dantzig–Wolfe decomposition}}

== 外部リンク ==
* [http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf "Integer Programming" Section 9.8] ''Applied Mathematical Programming'' Chapter 9 Integer Programming (full text). Bradley, Hax, and Magnanti (Addison-Wesley, 1977) 

{{最適化アルゴリズム}}

{{DEFAULTSORT:せつしよへいめんほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]