分枝カット法

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

アルゴリズム

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

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

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

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

1. アクティブな問題リスト ${\displaystyle L}$ に初期のILP（整数計画問題）を追加する
2. ${\displaystyle x^{*}={\text{null}}}$、${\displaystyle v^{*}=-\infty }$ とおく
3. ${\displaystyle L}$ が空になるまで反復
   1. ${\displaystyle L}$ から問題を一つ選択し削除する (de-que)
   2. 選択した問題の線形計画緩和問題を解く
   3. もし緩和問題が実行不可能の場合、ステップ3に戻る　そうでなければ、解を ${\displaystyle x}$、その目的関数値を ${\displaystyle v}$ と記す
   4. もし、${\displaystyle v\leq v^{*}}$ ならば、ステップ3へ戻る
   5. もし、${\displaystyle x}$ が整数ならば、${\displaystyle v^{*}\leftarrow v,x^{*}\leftarrow x}$と代入し、ステップ3へ戻る
   6. 必要に応じて適宜切除平面法によって ${\displaystyle x}$ が違反となるような妥当不等式を求める　妥当不等式が求まったならば、それらを線形計画緩和問題の制約に加えてステップ3.2へ戻る
   7. 分枝操作によって新たに実行可能領域が限定された複数の子問題に分割し、それらの子問題を ${\displaystyle L}$ に加えてステップ3へ戻る
4. 最適整数解 ${\displaystyle x^{*}}$を返す

疑似コード

C++風の疑似コードを以下に記す:

// 最大化の整数計画問題に対する分枝カット法の疑似コード
ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem) {
    queue active_list; // L, above
    active_list.enqueue(initial_problem); // step 1
    // step 2
    ILP_solution optimal_solution; // this will hold x* above
    double best_objective = -std::numeric_limits<double>::infinity; // will hold v* above
    while (!active_list.empty()) { // step 3 above
        LinearProgram& curr_prob = active_list.dequeue(); // step 3.1
        do { // steps 3.2-3.7
            RelaxedLinearProgram& relaxed_prob = LP_relax(curr_prob); // step 3.2
            LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // this is x above
            bool cutting_planes_found = false;
            if (!curr_relaxed_soln.is_feasible()) { // step 3.3
                continue; // try another solution; continues at step 3
            }
            double current_objective_value = curr_relaxed_soln.value(); // v above
            if (current_objective_value <= best_objective) { // step 3.4
                continue; // try another solution; continues at step 3
            }
            if (curr_relaxed_soln.is_integer()) { // step 3.5
                best_objective = current_objective_value;
                optimal_solution = cast_as_ILP_solution(curr_relaxed_soln);
                continue; // continues at step 3
            }
            // current relaxed solution isn't integral
            if (hunting_for_cutting_planes) { // step 3.6
                violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln);
                if (!violated_cutting_planes.empty()) { // step 3.6
                    cutting_planes_found = true; // will continue at step 3.2
                    for (auto&& cutting_plane : violated_cutting_planes) {
                        active_list.enqueue(LP_relax(curr_prob, cutting_plane));
                    }
                    continue; // continues at step 3.2
                }
            }
            // step 3.7: either violated cutting planes not found, or we weren't looking for them
            auto&& branched_problems = branch_partition(curr_prob);
            for (auto&& branch : branched_problems) {
                active_list.enqueue(branch);
            }
            continue; // continues at step 3
        } while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */
               && cutting_planes_found);
        // end step 3.2 do-while loop
    } // end step 3 while loop
    return optimal_solution; // step 4
}

上記の疑似コードではLP_relax、LP_solve、branch_partitionのサブルーチンは与えられる問題に応じた手法を実装する必要がある。例えば、LP_solveでは単体法が挙げられる。分枝操作戦略branch_partitionに関しては以下の節で説明を行う。

分枝戦略

分枝カット法で重要なステップとなるのは分枝操作が挙げられる。分枝操作で使用できる戦略方法としていくつかのヒューリスティック的手法が存在する。以下に記される分枝戦略はいずれも変数の値によって決定される^[3]。これは現在の線形計画緩和問題の最適解において非整数値を取る変数 ${\displaystyle x_{i}}$ を一つ選び、その変数に2つの制約 ${\displaystyle x_{i}\leq \left\lfloor x_{i}'\right\rfloor }$、${\displaystyle x_{i}\geq \left\lceil x_{i}'\right\rceil }$ をそれぞれ追加する方法を示す。

整数から最も離れている変数の分枝

この分枝戦略は小数部分が 0.5 に最も近い変数を選択する。

疑似コスト分枝

疑似コスト分枝戦略は各変数 ${\displaystyle x_{i}}$ に対して、その変数を分枝に選んだ際に目的関数がどの程度変化したかを記録していく戦略である。過去の分枝による目的関数の変化をもとに最も大きな変化が予測される変数を分枝する変数として選択する。探索の初期段階では分枝による目的関数の変化の情報が不足することから、疑似コスト分枝戦略では有効な情報を提供しにくい。

強分枝

強分枝戦略では分枝操作を行う前に分枝の候補となる変数に対して分枝操作を行ったことによる目的関数の変化を計算する。強分枝戦略は候補変数のすべての変数に対して目的関数の影響度合いを計算する完全な強分枝戦略を採用することも可能であるが、計算コストが候補変数に応じて高くなる。計算コストを減らすために候補変数の一部のみの影響を計算することや、各変数に対応する線形計画緩和問題の計算を中断する方法が挙げられる。

分枝戦略の方法は類似のものを含め多数存在する。分枝操作の初期段階では疑似コストを計算するための情報をあまり持たないことから強分枝戦略を採用し、疑似コストを計算するための情報が十分に集まった段階で適宜疑似コスト分枝戦略に切り替えるような分枝戦略も存在する。