分枝切除法

OR事典

分枝切除法

読み方：ぶんしせつじょほう
【英】：branch and cut method

分枝限定法において, (最小化問題の場合)下界値を改善するための手法の1つで, 各部分問題の緩和問題を解く際に, 切除平面法を組み込む方法. 下界値の改善によって無駄な列挙を大幅に省くことができるが, 組み込む制約が増えると緩和問題を解く労力も増加する. それらのトレードオフの調整が, 全体の効率を左右する鍵となる. 多くの組合せ最適化問題において大規模な例題を解くことに成功しており, 実用的な手法としても高い評価を得ている.

「OR事典」の他の用語

組合せ最適化：

並列アルゴリズム  充足可能性問題  分散アルゴリズム  分枝切除法  分枝限定法  劣勾配法  動的木

ウィキペディア

分枝カット法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/13 04:21 UTC 版)

分枝カット法（ぶんしカットほう、英: branch and cut^[1]）とは、線形計画法（Linear programming: LP）において解が整数値に限定された整数計画問題（Integer Prgramming: IP）を解くための組み合わせ最適化における解法である^[2]。分枝カット法は分枝限定法およびその整数計画問題を緩和した問題の線形計画緩和問題に対する解法の切除平面法を組み合わせた解法である。

アルゴリズム

以下は最大化の整数計画問題について考える。

まず始めに整数計画問題の整数条件を取り除いた線形計画緩和問題（英語版）を通常の単体法によって解く。このとき得られた最適解が整数条件でなければ、元の問題に存在する整数条件を満たさないため、切除平面法によって実行可能解の整数点を満たしつつ現在得られた最適解が満たさないような線形不等式を導出する。これらの不等式を新たに線形計画問題に追加することで、以降の線形計画問題で得られる最適解は整数条件を満たす解が得られることが期待される。

カット操作を終えると続いて分枝限定操作に移る。与えられた問題を複数（2つの場合が多い）の部分問題に分割する。 分割された各部分問題ごとに新たに線形計画緩和問題を解いてこれらの手続きを繰り返していく。分枝限定操作によって得られる（元の問題の制約を満たさない）非整数解の目的関数値は上界を表し、（元の問題の制約を満たす）整数解の目的関数値は下界を示す。あるノードの上界が現在得られている下界より小さい場合、そのノードは枝刈り（英語版）される。さらに線形計画緩和問題を解く際にすべての実行可能整数解が満たすような妥当不等式のグローバルカットあるいは分枝限定操作で分割された木に対応する実行可能領域内の整数点のみが十分に満たすような妥当不等式のローカルカットを切除平面法によって生成することもできる。

分枝カット法の手続きは以下の通りである:

1. アクティブな問題リスト ${\displaystyle L}$
   Optimization computes maxima and minima.

非線形（制約付き）

一般	バリア関数 ペナルティ関数法
微分可能	ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法 逐次線形二次計画法

凸最適化

凸最小化	切除平面法 簡約勾配法 劣勾配法 近接勾配法
線形 および 二次	内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法
ネットワークフロー (最大流問題)	ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア