切除平面法

【せつじょへいめんほう (cutting plane method)】

組合せ最適化問題を解くための解法の1つで, ゴモリー (Gomory) によって1958年に発表された. 問題を整数計画として定式化し, その線形緩和問題を解くと一般に小数解を得る. その小数解を切り落とし, すべての整数解を残すような超平面から導かれる半空間を制約として線形緩和問題に逐次加えながら, 最終的に整数解を得ようというアプローチ. 理論的に完成度の高い手法ではあるが, 収束するまでに加える制約の数が多くなるなどの実用上の問題が残されている.