分枝カット法のソースを表示

'''分枝カット法'''（ぶんしカットほう、{{Lang-en-short|branch and cut}}<ref>{{Cite journal|last=Padberg|first=Manfred|last2=Rinaldi|first2=Giovanni|date=1991|title=A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems|journal=SIAM Review|language=en|volume=33|issue=1|pages=60–100|doi=10.1137/1033004|issn=0036-1445}}</ref>）とは、[[線形計画法]]（Linear programming: LP）において解が[[整数|整数値]]に限定された[[整数計画問題]]（Integer Prgramming: IP）を解くための[[組み合わせ最適化]]における解法である<ref>{{cite journal|last=John E.|first=Mitchell|title=Branch-and-Cut Algorithms for Combinatorial Optimization Problems|journal=Handbook of Applied Optimization|year=2002|pages=65–77|url=http://eaton.math.rpi.edu/faculty/Mitchell/papers/bc_hao.pdf}}</ref>。分枝カット法は[[分枝限定法]]およびその整数計画問題を緩和した問題の線形計画緩和問題に対する解法の[[切除平面法]]を組み合わせた解法である。

== アルゴリズム ==
以下は最大化の整数計画問題について考える。

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

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

{{anchors|Algorithm summary}}分枝カット法の手続きは以下の通りである:

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

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

<syntaxhighlight lang="c++" line="1">
// 最大化の整数計画問題に対する分枝カット法の疑似コード
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
}
</syntaxhighlight>

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

== 分枝戦略 ==
分枝カット法で重要なステップとなるのは分枝操作が挙げられる。分枝操作で使用できる戦略方法としていくつかのヒューリスティック的手法が存在する。以下に記される分枝戦略はいずれも変数の値によって決定される<ref>{{Cite journal|last=Achterberg|first=Tobias|last2=Koch|first2=Thorsten|last3=Martin|first3=Alexander|date=2005|title=Branching rules revisited|journal=Operations Research Letters|language=en|volume=33|issue=1|pages=42–54|doi=10.1016/j.orl.2004.04.002}}</ref>。これは現在の線形計画緩和問題の最適解において非整数値を取る変数 <math>x_i</math> を一つ選び、その変数に2つの制約 <math>x_i \le \left\lfloor x_i' \right\rfloor</math>、<math> x_i \ge \left\lceil x_i' \right\rceil</math> をそれぞれ追加する方法を示す。

; 整数から最も離れている変数の分枝: この分枝戦略は小数部分が 0.5 に最も近い変数を選択する。
; 疑似コスト分枝: 疑似コスト分枝戦略は各変数 <math>x_i</math> に対して、その変数を分枝に選んだ際に目的関数がどの程度変化したかを記録していく戦略である。過去の分枝による目的関数の変化をもとに最も大きな変化が予測される変数を分枝する変数として選択する。探索の初期段階では分枝による目的関数の変化の情報が不足することから、疑似コスト分枝戦略では有効な情報を提供しにくい。
; 強分枝: 強分枝戦略では分枝操作を行う前に分枝の候補となる変数に対して分枝操作を行ったことによる目的関数の変化を計算する。強分枝戦略は候補変数のすべての変数に対して目的関数の影響度合いを計算する完全な強分枝戦略を採用することも可能であるが、計算コストが候補変数に応じて高くなる。計算コストを減らすために候補変数の一部のみの影響を計算することや、各変数に対応する線形計画緩和問題の計算を中断する方法が挙げられる。

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 外部リンク ==
* [https://web.archive.org/web/20050901073653/http://www.cs.sandia.gov/opt/survey/mip.html Mixed Integer Programming]
* [http://scip.zib.de SCIP]: framework for branch-cut-and-price and a mixed integer programming solver 
* [https://software.cs.uni-koeln.de/abacus/ ABACUS – A Branch-And-CUt System] – open source software
* [https://github.com/coin-or/Cbc COIN-OR Cbc] – open source software on [[GitHub]]

{{最適化アルゴリズム}}

{{DEFAULTSORT:ふんしかつとほう}}
[[Category:組合せ最適化]]
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]