分枝切除法
分枝カット法
分枝カット法（ぶんしカットほう、英: branch and cut[1]）とは、線形計画法（Linear programming: LP）において解が整数値に限定された整数計画問題（Integer Prgramming: IP）を解くための組み合わせ最適化における解法である[2]。分枝カット法は分枝限定法およびその整数計画問題を緩和した問題の線形計画緩和問題に対する解法の切除平面法を組み合わせた解法である。
アルゴリズム
以下は最大化の整数計画問題について考える。
まず始めに整数計画問題の整数条件を取り除いた線形計画緩和問題を通常の単体法によって解く。このとき得られた最適解が整数条件でなければ、元の問題に存在する整数条件を満たさないため、切除平面法によって実行可能解の整数点を満たしつつ現在得られた最適解が満たさないような線形不等式を導出する。これらの不等式を新たに線形計画問題に追加することで、以降の線形計画問題で得られる最適解は整数条件を満たす解が得られることが期待される。
カット操作を終えると続いて分枝限定操作に移る。与えられた問題を複数（2つの場合が多い）の部分問題に分割する。 分割された各部分問題ごとに新たに線形計画緩和問題を解いてこれらの手続きを繰り返していく。分枝限定操作によって得られる（元の問題の制約を満たさない）非整数解の目的関数値は上界を表し、（元の問題の制約を満たす）整数解の目的関数値は下界を示す。あるノードの上界が現在得られている下界より小さい場合、そのノードは枝刈りされる。さらに線形計画緩和問題を解く際にすべての実行可能整数解が満たすような妥当不等式のグローバルカットあるいは分枝限定操作で分割された木に対応する実行可能領域内の整数点のみが十分に満たすような妥当不等式のローカルカットを切除平面法によって生成することもできる。
分枝カット法の手続きは以下の通りである:
- アクティブな問題リスト
Optimization computes maxima and minima.
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
| ||||
| ネットワークフロー (最大流問題) |
