妥当不等式

妥当不等式#

  • 読み: だとうふとうしき

  • 英名: Valid Inequality,Cutting Plane

  • 別名: 切除平面

整数計画問題において,実行可能領域内の点が満たすことのできる不等式のこと. 妥当不等式には,一般の整数計画問題に適用できるものと,特殊な形の整数計画問題に適用できるものの二種類がある. 前者の例としては,ゴモリーカットや MIR カット,後者の例としてはナップサック問題のナップサックカットなどがある. 妥当不等式を加えることによって,問題の連続緩和解が整数最適解に近づく. 従来は切除平面法を対象とした研究や,個別の問題に特化した研究がされていたが, 近年分枝限定法の枠組みの中で有効に活用する方法,すなわち分枝カット法が見出された [1]. これ以来,多くの整数計画ソルバーは,分枝カット法が実装されている.

分枝カット法においては,特に混合整数ゴモリーカットと MIR カットが有効とされている. 混合整数ゴモリーカットは,線形緩和問題を単体法で解いて得られる最適タブローの情報を用いてカットを生成する. 緩和解が整数性を満たさない場合,必ず緩和解は生成された妥当不等式を満たさないことが特徴である. ただし,生成されるカットが密であったり数値的性質が悪かったりする場合があるので注意が必要である. MIR カットは,特に Wolsey-Marchand の c-MIR カットが有名である [2]. これは様々な古典的カットの構成法をもとに考案されたカットである. ヒューリスティックに構成されるため,混合整数ゴモリーカットとは違い,緩和解を満たさない妥当不等式が必ず構成できる保証はないが, 実務的な問題に対して強力な効果を発揮するとされている.

関連

参考文献

[1]

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.

[2]

Hugues Marchand and Laurence A Wolsey. Aggregation and Mixed Integer Rounding to Solve MIPS. Operations Research, 49(3):363–371, mar 2001. URL: http://www.jstor.org/stable/3088633.