分岐限定法

分枝限定法（BB、B&B、またはBnB）は、最適化問題を小さなサブ問題に分割し、境界関数を使用して最適解を含まないサブ問題を排除することで、最適化問題を解く方法です。これは、離散最適化問題と組み合わせ最適化問題、および数学的最適化のためのアルゴリズム 設計パラダイムです。分枝限定法アルゴリズムは、状態空間探索による候補解の体系的な列挙で構成されます。候補解の集合は、完全な集合をルートとするルート付きツリーを形成するものと考えられています。アルゴリズムは、解集合のサブセットを表すこのツリーの枝を探索します。枝の候補解を列挙する前に、枝は最適解の推定上限と下限に対してチェックされ、アルゴリズムによってこれまでに見つかった最良の解よりも良い解を生成できない場合は破棄されます。

このアルゴリズムは、検索空間の領域/分岐の下限と上限を効率的に推定することに依存します。境界が利用できない場合、アルゴリズムは網羅的な検索に移行します。

この方法は、 1960年にブリティッシュ・ペトロリアムの支援を受けてロンドン・スクール・オブ・エコノミクスで離散計画法の研究を行っていたアイルサ・ランドとアリソン・ドイグによって初めて提案され、^{[1] [2]} NP困難な最適化問題を解くための最も一般的に使用されるツールになりました。 ^[3]「分枝限定法」という名前は、巡回セールスマン問題に関するリトルらの研究で初めて登場しました。^{[4] [5]}

分枝限定アルゴリズムの目的は、許容される解、つまり候補解の集合Sの中から、目的関数と呼ばれる実数値関数f ( x )の値を最大化または最小化する値xを見つけることです。集合Sは探索空間または実行可能領域と呼ばれます。このセクションの残りの部分では、f ( x )の最小化が望ましいと仮定します。この仮定は一般性を損なうことなく成り立ちます。なぜなら、 g ( x ) = − f ( x )の最小値を見つけることでf ( x )の最大値を見つけることができるからです。分枝限定アルゴリズムは、次の 2 つの原則に従って動作します。

• 探索空間を再帰的に小さな空間に分割し、これらの小さな空間でf ( x )を最小化します。この分割は分岐と呼ばれます。
• 分岐のみでは、候補ソリューションを力ずくで列挙し、それらすべてをテストすることになります。力ずくの検索のパフォーマンスを向上させるために、B&B アルゴリズムは、検索しようとしている最小値の境界を追跡し、これらの境界を使用して検索スペースを「整理」し、最適なソリューションが含まれていないことが証明できる候補ソリューションを排除します。

これらの原理を特定の最適化問題に対する具体的なアルゴリズムに変換するには、候補ソリューションのセットを表す何らかのデータ構造が必要です。このような表現は、問題のインスタンスと呼ばれます。インスタンスIの候補ソリューションのセットをS _Iで表します。インスタンス表現には、次の 3 つの操作が必要です。

• branch( I )は、SIのサブセットを表す2つ以上のインスタンスを生成します。（通常、サブセットは、アルゴリズムが同じ候補ソリューションを2回訪問するのを防ぐために分離されています_が、これは必須ではありません。ただし、 SI_の最適なソリューションは、少なくとも1つのサブセットに含まれている必要があります。^[6]）
• bound( I )は、Iで表される空間内の任意の候補解_の値の下限を計算します。つまり、SI内のすべてのxに対してbound( I ) ≤f ( x )となります。
• solution( I )はIが単一の候補解を表すかどうかを判定する。(オプションで、そうでない場合は、SI_の中から実行可能な解を返すように選択することができる。^[6] ) solution( I )が解を返す場合、f (solution( I ))は実行可能な解の空間全体にわたって最適な目的値の上限を提供する。

これらの操作を使用して、B&B アルゴリズムは、分岐操作によって形成されたインスタンスのツリーをトップダウンで再帰的に検索します。インスタンスIにアクセスすると、 bound( I )が現在の上限以上であるかどうかがチェックされます。そうである場合、 I は検索から安全に破棄され、再帰は停止します。この剪定手順は通常、これまでに検査されたすべてのインスタンスで確認された最小の上限を記録するグローバル変数を維持することによって実装されます。

以下は、任意の目的関数f を最小化する一般的な分岐限定アルゴリズムの骨組みです。^[3]これから実際のアルゴリズムを得るには、問題固有の分岐規則だけでなく、探索木のノード上のfの下限を計算する境界関数bound が必要です。そのため、ここで提示する一般的なアルゴリズムは高階関数です。

1. ヒューリスティックを使用して、最適化問題の解x _{hを見つけます。その値}B = f ( x _h )を保存します。(ヒューリスティックが利用できない場合は、B を無限大に設定します。) B は、これまでに見つかった最良の解を示し、候補解の上限として使用されます。
2. 問題の変数が割り当てられていない部分的なソリューションを保持するキューを初期化します。
3. キューが空になるまでループします。
   1. ノードN をキューから削除します。
   2. N が単一の候補解x を表し、f ( x ) < Bである場合、x がこれまでの最善の解です。これを記録し、B ← f ( x )と設定します。
   3. それ以外の場合は、Nで分岐して新しいノードN _{i を}生成します。それぞれについて:
      1. bound( N _i ) > Bの場合は何もしません。このノードの下限が問題の上限よりも大きいため、最適な解決策にはつながらず、破棄できます。
      2. それ以外の場合は、N _{i を}キューに格納します。

いくつかの異なるキューデータ構造を使用できます。このFIFO キューベースの実装では、幅優先探索が行われます。スタック(LIFO キュー) では深さ優先アルゴリズムが行われます。下限でノードをソートする優先キューを使用すると、最良優先の分岐限定アルゴリズムが得られます。 ^[3]この前提に基づく最良優先探索アルゴリズムの例としては、ダイクストラのアルゴリズムとその派生であるA* 検索があります。深さ優先のバリアントは、初期ソリューションを生成するための適切なヒューリスティックがない場合に推奨されます。完全なソリューション、つまり上限をすばやく生成できるためです。^[7]

上記のC++のような疑似コード実装は次のとおりです。

// C++ のような分岐限定の実装、
// 目的関数fが最小化されると仮定する
組み合わせソリューション分岐制限解決( 
    組み合わせ問題の問題、  
    目的関数目的関数/*f*/ 、  
    BoundingFunction下限関数/*境界*/ )   
{
    // 上記の手順 1。
    double problem_upper_bound = std :: numeric_limits < double >:: infinity ; // = B    
    CombinatorialSolution heuristic_solution = heuristic_solve ( problem ); // x_h    
    problem_upper_bound = objective_function ( heuristic_solution ); // B = f(x_h)   
    組み合わせソリューションcurrent_optimum = heuristic_solution ;   
    // 上記のステップ2
    キュー< CandidateSolutionTree > candidate_queue ; 
    // 問題固有のキューの初期化
    candidate_queue = populate_candidates (問題);  
    while ( ! candidate_queue . empty ()) { // 上記のステップ3   
        // ステップ 3.1
        CandidateSolutionTreeノード= candidate_queue . pop ();   
        // 「ノード」は上記のNを表す
        if ( node . represents_single_candidate ()) { // ステップ3.2   
            if (目的関数(ノード.候補()) <問題の上限) {    
                current_optimum =ノード.candidate ( ) ;  
                問題の上限=目的関数(現在の最適値);  
            }
            // そうでない場合、ノードは最適ではない単一の候補です
        }
        else { // ステップ3.3: ノードは候補ソリューションのブランチを表します  
            // "child_branch"は上記のN_iを表します
            for ( auto && child_branch : node . candidate_nodes ) {     
                if (下限関数(子ブランチ) <=問題の上限) {    
                    candidate_queue . enqueue ( child_branch ); // ステップ 3.3.2 
                }
                // それ以外の場合、bound(N_i) > B なので、枝を刈り込みます。ステップ 3.3.1
            }
        }
    }
    current_optimumを返します。 
}

上記の疑似コードでは、サブルーチンとして呼び出される関数heuristic_solveとが、populate_candidates問題に応じて提供される必要があります。関数f ( objective_function) とbound ( ) は、記述どおりに関数オブジェクトlower_bound_functionとして扱われ、 C++ プログラミング言語の ラムダ式、関数ポインタ、およびその他のタイプの呼び出し可能オブジェクトに対応する可能性があります。

がのベクトルである場合、分枝限定法を区間解析^[8]や請負業者法と組み合わせて、大域的最小値の保証された囲みを提供することができる。^{[9] [10]}${\displaystyle \mathbf {x} }$${\displaystyle \mathbb {R} ^{n}}$

このアプローチは、多くのNP 困難な問題に使用されます。

• 整数計画法
• 非線形計画法
• 巡回セールスマン問題（TSP）^{[4] [11]}
• 二次割り当て問題(QAP)
• 最大満足問題(MAX-SAT)
• 最近傍探索^[12]（福永啓之助）
• フローショップのスケジュール
• 在庫問題を切り詰める
• 計算系統学
• 反転を設定する
• パラメータ推定
• 0/1 ナップサック問題
• セットカバーの問題
• 機械学習における特徴選択^{[13] [14]}
• コンピュータビジョンにおける構造化予測^{[15] : 267–276}
• アークルーティング問題（中国の郵便配達人問題を含む）
• タレントのスケジュール、シーン撮影の手配問題

分岐限定法は、さまざまなヒューリスティックの基礎にもなります。たとえば、上限と下限の差が特定のしきい値よりも小さくなったときに分岐を停止したい場合があります。これは、ソリューションが「実用的な目的に十分」な場合に使用され、必要な計算を大幅に削減できます。このタイプのソリューションは、使用されるコスト関数にノイズが多い場合や、統計的推定の結果であるため正確にはわかっておらず、特定の確率で値の範囲内にあることだけがわかっている場合に特に適しています。^{[引用が必要]}

Nauらは、A*、B*、アルファベータ検索アルゴリズムも包含する分岐限定法の一般化を提示している。^[16]

この問題を解決するには分岐限定法が使える

これらの制約を 最大限に活用する${\displaystyle Z=5x_{1}+6x_{2}}$

${\displaystyle x_{1}+x_{2}\leq 50}$

${\displaystyle 4x_{1}+7x_{2}\leq 280}$

${\displaystyle x_{1},x_{2}\geq 0}$

${\displaystyle x_{1}}$およびは整数です。 ${\displaystyle x_{2}}$

最初のステップは、整数制約を緩和することです。最初の方程式には、直線を形成する 2 つの端点があります:および。ベクトル点 および を使用して 2 番目の直線を形成できます。 ${\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}}$

3 番目の点は です。これは凸包領域なので、解は領域の頂点の 1 つにあります。行削減を使用して交差点を見つけることができます。これは、または値が 276.667 の交差点です。領域上で線をスイープして他の端点をテストし、これが実数上の最大値であることを確認します。 ${\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}}$${\displaystyle {\begin{bmatrix}23.333\\26.667\end{bmatrix}}}$

最大の小数部を持つ変数を選択します。この場合、 は分岐限定法のパラメータになります。 に分岐して 276 @ を取得します。整数解に到達したので、他の分岐 に移動します。 275.75 @ を取得します。小数点があるので に分岐して274.571 @ を見つけます。他の分岐を試しても実行可能な解はありません。したがって、最大値は および で 276です。 ${\displaystyle x_{2}}$${\displaystyle x_{2}\leq 26}$${\displaystyle \langle 24,26\rangle }$${\displaystyle x_{2}\geq 27}$${\displaystyle \langle 22.75,27\rangle }$${\displaystyle x_{1}}$${\displaystyle x_{1}\leq 22}$${\displaystyle \langle 22,27.4286\rangle }$${\displaystyle x_{1}\geq 23}$${\displaystyle x_{1}\longmapsto 24}$${\displaystyle x_{2}\longmapsto 26}$

• バックトラッキング
• 分岐切断法は、分岐限定法と切断面法を組み合わせたもので、整数線形計画法を解くために広く使用されています。
• 進化アルゴリズム
• アルファベータ剪定

• LiPS – 線形、整数、目標計画問題を解決することを目的とした、無料で使いやすい GUI プログラム。
• Cbc (Coin-or Branch and Cut) は、C++ で書かれたオープンソースの混合整数計画ソルバーです。