枝分かれして切る

ブランチアンドカット^[1]は、整数線形計画法（ILP）、つまり未知数の一部またはすべてが整数値に制限されている線形計画法（LP）問題を解くための組合せ最適化手法です。 ^{[2]ブランチアンドカットでは、}分岐限定アルゴリズムを実行し、切断面を使用して線形計画法の緩和を強化します。カットが初期のLP緩和を強化するためだけに使用される場合、アルゴリズムはカットアンドブランチと呼ばれます。

この説明では、ILP が最大化問題であると想定しています。

この方法は、通常の単体アルゴリズムを使用して、整数制約のない線形計画を解きます。最適解が得られ、この解が整数であるはずの変数に対して非整数値を持つ場合、切断面アルゴリズムを使用して、すべての実行可能な整数点によって満たされるが、現在の分数解によって違反されるさらなる線形制約を見つけることができます。これらの不等式は線形計画に追加され、それを解決することで、おそらく「より分数でない」別の解が生成されます。

この時点で、アルゴリズムの分岐限定部分が開始されます。問題は複数 (通常は 2 つ) のバージョンに分割されます。次に、新しい線形計画法が単体法を使用して解決され、プロセスが繰り返されます。分岐限定プロセス中、LP 緩和の非整数解は上限として機能し、整数解は下限として機能します。上限が既存の下限よりも低い場合は、ノードを削減できます。さらに、LP 緩和を解くときに、追加の切断面が生成される場合があります。これは、グローバル カット(つまり、すべての実行可能な整数解に有効) またはローカル カット(つまり、現在考慮されている分岐限定サブツリーからのサイド制約を満たすすべての解によって満たされる) のいずれかです 。

アルゴリズムの概要は以下のとおりです。

1. 初期ILPをアクティブな問題のリストに追加する${\displaystyle L}$
2. 設定して${\displaystyle x^{*}={\text{null}}}$${\displaystyle v^{*}=-\infty }$
3. 空では ない ${\displaystyle L}$
   1. 問題を選択して削除（キューから削除）${\displaystyle L}$
   2. 問題の LP 緩和を解きます。
   3. 解が実行不可能な場合は、3 (while) に戻ります。それ以外の場合は、解を目的値で表します。${\displaystyle x}$${\displaystyle v}$
   4. の場合は、3 に戻ります。${\displaystyle v\leq v^{*}}$
   5. 整数の場合は3 に設定して戻ります。${\displaystyle x}$${\displaystyle v^{*}\leftarrow v,x^{*}\leftarrow x}$
   6. 必要に応じて、 によって違反される切断面を検索します。見つかった場合は、それらを LP 緩和に追加し、3.2 に戻ります。${\displaystyle x}$
   7. 問題を、実行可能な領域を制限した新しい問題に分割する分岐。これらの問題を追加して3に戻る。${\displaystyle L}$
4. 戻る${\displaystyle x^{*}}$

C++のような疑似コードでは、次のように記述できます。

// ILP の分岐とカットの解の擬似コード。目的が最大化されることを前提としています。
ILP_solution branch_and_cut_ILP ( IntegerLinearProgram initial_problem ) {   
    キューactive_list ; // L、上記  
    active_list.enqueue ( initial_problem ) ; //ステップ1 
    // ステップ 2
    ILP_solution最適解; // これはx*を上回っている  
    double best_objective = - std :: numeric_limits < double >:: infinity ; // 上記の v* を保持します    
    while ( ! active_list . empty ()) { // 上記のステップ3   
        LinearProgram & curr_prob = active_list . dequeue (); // ステップ 3.1    
        do { // 手順3.2-3.7  
            RelaxedLinearProgram & relaxed_prob = LP_relax ( curr_prob ); // ステップ3.2    
            LP_solution curr_relaxed_soln = LP_solve ( relaxed_prob ); // これは上記のxです    
            bool切断面が見つかる= false ;   
            if ( ! curr_relaxed_soln . is_feasible ()) { // ステップ 3.3   
                続行; // 別の解決策を試します; ステップ 3 から続行します 
            }
            double current_objective_value = curr_relaxed_soln . value (); // 上記のv    
            if ( current_objective_value <= best_objective ) { // ステップ 3.4     
                続行; // 別の解決策を試します; ステップ 3 から続行します 
            }
            if ( curr_relaxed_soln . is_integer ()) { // ステップ 3.5   
                最適な目的=現在の目的の値;  
                最適なソリューション= ILP ソリューションとしてキャスト( curr_relaxed_soln );  
                continue ; // ステップ 3 から続行します 
            }
            // 現在の緩和されたソリューションは完全ではありません
            if ( hunting_for_cutting_planes ) { // ステップ 3.6   
                違反した切断面=違反した切断面の検索( curr_relaxed_soln );  
                if ( !違反切断面.空()) { // ステップ 3.6   
                    cut_planes_found = true ; // ステップ 3.2 に進みます   
                    for ( auto &&切断面:違反した切断面) {     
                        active_list . enqueue ( LP_relax ( curr_prob , cuting_plane )); 
                    }
                    continue ; // ステップ 3.2 から続行 
                }
            }
            // ステップ 3.7: 違反した切断面が見つからないか、またはそれらを探していませんでした
            自動&&分岐した問題=分岐パーティション( curr_prob );   
            for ( auto && branch :分岐した問題) {     
                active_list.enqueue (ブランチ) ;​
            }
            continue ; // ステップ 3 から続行します 
        } while ( hunting_for_cutting_planes /* アルゴリズムのパラメータ。3.6を参照 */   
               &&切断面が見つかりました); 
        // ステップ 3.2 do-while ループの終了
    } // ステップ3のwhileループを終了 
    最適なソリューションを返す; // ステップ4  
}

上記の疑似コードでは、サブルーチンとして呼び出される関数LP_relax、LP_solve、 はbranch_partition、問題に適用可能なものとして提供されなければなりません。たとえば、 は単体アルゴリズムLP_solveを呼び出すことができます。 の分岐戦略については以下で説明します。 branch_partition

分岐カットアルゴリズムの重要なステップは分岐ステップです。このステップでは、さまざまな分岐ヒューリスティックを使用することができます。以下に説明する分岐戦略はすべて、変数分岐と呼ばれるものを含みます。^[3] 変数分岐では、現在のLP緩和の最適解で小数値 を持つ変数 を選択し、次に制約と を追加します。${\displaystyle x_{i}}$${\displaystyle x_{i}'}$${\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}}$

強い分岐

強い分岐では、実際に分岐する前に、どの候補変数が目的関数に最も良い改善をもたらすかをテストします。 完全な強い分岐では、すべての候補変数をテストするため、計算コストが高くなる可能性があります。候補変数のサブセットのみを考慮し、対応する LP 緩和のそれぞれを完了まで解かないことによって、計算コストを削減できます。

これらの分岐戦略には、疑似コスト分岐があまり有益でない早い段階で強い分岐を使用し、疑似コストが有益になるだけの分岐履歴が蓄積された後で疑似コスト分岐に切り替えるなど、多数のバリエーションがあります。

• 混合整数計画法
• SCIP: 分岐切断価格法と混合整数計画ソルバーのフレームワーク
• ABACUS – 分岐カットシステム – オープンソースソフトウェア
• COIN-OR Cbc – GitHub上のオープンソース ソフトウェア