切除平面法#
読み: せつじょへいめんほう
英名: Cutting Plane Method
整数計画法の文脈においては，整数計画問題の解法の一つとなる．以下の手順を繰り返す．
STEP0. 整数計画問題の線形緩和問題を解く．
STEP1. 緩和解が整数性を満たしていれば終了する．
STEP2. 緩和解を満たさない妥当不等式を制約として追加する．STEP0 に戻る．
妥当不等式として Gomory cut を用いる切除平面法 [1] が最も有名である． この方法は全ての変数が整数変数である場合，有限回のステップで整数解が求まることが証明されている． 実際的には数値的問題により収束が困難とされているため，切除平面法そのものが商用ソルバーで採用されていることは稀である． しかしながら，切除平面法が整数計画法の発展に寄与していないわけではない． 実際，妥当不等式の技術を分枝限定法に組み入れることで高速化を図れることが Balas らによって発見されている [1]． 現在では Nuorium Optimizer をはじめ多くの商用ソルバーで，その技術が取り入れられている．
近年では lift-and-project cut [3] や split cut [4] など多様な妥当不等式による切除平面法の研究が進んでいる． また Gomory cut を用いた切除平面法は数値的困難が伴うとされていたが， 近年 Zanette ら [5] によって単体法の枢軸選択で辞書式順序を用いることで安定的に収束することが実証されている．
関連
参考文献
Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5):275–278, 1958. URL: https://www.ams.org/bull/1958-64-05/S0002-9904-1958-10224-4/, doi:10.1090/S0002-9904-1958-10224-4.
E. Balas, S. Ceria, G. Cornuéjols, and N. Natraj. Gomory cuts revisited. Operations Research Letters, 19(1):1–9, jul 1996. URL: https://linkinghub.elsevier.com/retrieve/pii/0167637796000077, doi:10.1016/0167-6377(96)00007-7.
Pierre Bonami. On optimizing over lift-and-project closures. Mathematical Programming Computation, 4(2):151–179, jun 2012. URL: http://link.springer.com/10.1007/s12532-012-0037-0, arXiv:1010.5412, doi:10.1007/s12532-012-0037-0.
Egon Balas and Anureet Saxena. Optimizing over the split closure. Math. Program., 113(2):219–240, 2008.
Arrigo Zanette, Matteo Fischetti, and Egon Balas. Lexicography and degeneracy: can a pure cutting plane algorithm work? Mathematical Programming, 130(1):153–176, nov 2011. URL: http://link.springer.com/10.1007/s10107-009-0335-0, doi:10.1007/s10107-009-0335-0.