トップ > 数理計画用語集 > 切除平面法

数理計画用語集

切除平面法

読み:せつじょへいめんほう
関連:Cutting Plane Method

整数計画法の文脈においては,整数計画問題の解法の一つとなる.以下の手順を繰り返す.

STEP0. 整数計画問題線形緩和問題を解く.

STEP1. 緩和解が整数性を満たしていれば終了する.

STEP2. 緩和解を満たさない妥当不等式を制約として追加する.STEP0 に戻る.

妥当不等式として Gomory cut を用いる切除平面法が最も有名である([1]).この方法は全ての変数が整数変数である場合,有限回のステップで整数解が求まることが証明されている.実際的には数値的問題により収束が困難とされているため,切除平面法そのものが商用ソルバーで採用されていることは稀である.しかしながら,切除平面法が整数計画法の発展に寄与していないわけではない.実際,妥当不等式の技術を分枝限定法に組み入れることで高速化を図れることが Balas らによって発見されている([2]).現在では Numerical Optimizer をはじめ多くの商用ソルバーで,その技術が取り入れられている.

近年では lift-and-project cut[3] や split cut [4] など多様な妥当不等式による切除平面法の研究が進んでいる.また Gomory cut を用いた切除平面法は数値的困難が伴うとされていたが,近年Zanette らによって単体法の枢軸選択で辞書式順序を用いることで安定的に収束することが実証されている([5]).

[参考]
[1] R. Gomory, Outline of an algorithm for integer solutions to linear programs
[2] E. Balas, S. Ceriab, G. Cornuejols, N. Natrajc, Gomory cuts revisited, Operations Research Letters, 19, Issue 1, 1996, pp.1-9
[3] Pierre Bonami, On optimizing over lift-and-project closures, http://arxiv.org/abs/1010.5412
[4] E. Balas, A Saxena , Optimizing over the split closure, Mathematical Programming, 113, 2, 2008, pp. 219-240
[5] A. Zanette, M. Fischetti, E. Balas, Lexicography and degeneracy: can a pure cutting plane algorithm work?, Mathematical Programming, 130, 1, 2011, pp.153-176