最適化セミナーのご案内

B.2.3 分枝限定法

 Numerical Optimizerは,整数変数を含む線形/二次計画問題に対して単体法(options.method = "simplex")か有効制約法(options.method = "asqp")が指定された場合,さらに一般の非線形計画問題に対して大域的最適化(options.method = "global")が指定された場合,分枝限定法と呼ばれるアルゴリズムを用います.

 分枝限定法は元の問題の実行可能領域を解き易い形にしたもの(緩和問題)を解くことを繰り返して厳密解を求めようとするものです.整数計画問題の場合,緩和問題は整数変数の範囲を含む連続領域に広げたものとして定義します.また,大域的最適化問題の場合には式を二項演算に分解して凸緩和という式を用いますが,ここでは0-1整数変数を含む線形計画法の例で説明します.

 0-1整数変数は[0,1]の範囲を自由に動けるように拡張した線形計画問題が緩和問題となります.緩和問題の解を見て整数になっていない変数を整数値に固定する,という操作を網羅的に繰り返すのが分枝限定法の基本的な流れです.この過程は次の図のような木(分枝木)の形に表すことができ,整数制約を満たす解はこの木の「葉」の部分(先端部分)に現れます.

 しかし,「葉」に現れる可能性のある整数制約を満たす解は,整数変数の数に対して指数的な個数となり,それらを比較して最適なものを採用するだけでは,現実的な規模の問題に対して効率の良い解法とは言えません.分枝限定法は,緩和した問題の最適解における目的関数値と,その問題の変数の一部を固定した問題の目的関数値の大小関係を使って探索を効率化します.

 解いている問題が最小化問題であれば,緩和問題の最適解の目的関数値はその問題の変数の一部を固定した問題よりも,(実行可能領域が広いので)同じか大きくなることが言えます.これを分枝木に置きかえると,ある問題から枝分かれした問題の目的関数値は,元の問題よりも確実に同じか大きいを目的関数値を持つ,ということになります.最小化問題を解いているときにもし,10という最適解を持つ実行可能解が得られ,またある緩和問題の最適解における目的関数値が11だったとします.この場合,その緩和問題から枝分れした問題は確実に11よりも同じか大きい最適解しか持ちません.10より良い最適解を与える可能性がないので,この時点で11という最適解を持つ緩和問題から,枝分かれした問題を調べる必要はありません.この操作は「下界値テスト」による分枝の「限定」と呼びます.この操作を適宜行えば,最適な問題が得られる見込のない緩和問題に煩わされることなく,厳密解を効率良く求めることができます.

 この方法を計算手続きにすると,次の図のように表現することができます.

 アルゴリズムは調べるべき緩和問題のリストから,一つ緩和問題を取得して(問題選択),いずれかの変数を選んで(分枝変数選択)整数に固定し,派生した問題を作成して単体法を起動して緩和解を計算してリストに戻します.実行可能解が求まったらリスト中の問題に対して下界値テストをかけて,リストの内容を削減します.

 リストには最初,「分枝木」の「根」にあたる,すべての変数を緩和した問題が一つのみ置かれます.リストにある問題がすべて消失した段階でアルゴリズムは終了します.求解途中の問題の最適解は最小化問題の場合,緩和問題の最適解の目的関数値の最小値以上となります.この値のことを下界と言い,計算の進行に対する目安となります.下界値が計算途中にどのように出力されるかは「分枝限定法による出力」をご参照ください.

 このようなアルゴリズムの性質上,たとえ規模の小さな問題であっても,分枝限定法では一般に緩和問題を数多く解く必要があり,通常の連続変数のみを含む問題よりも時間がかかります.また,計算が停止する条件が,上述の「下界値テスト」の成否,すなわち計算途中に得られる実行可能解の良さと,そのタイミングに依存するため,計算に所要する時間をあらかじめ予測することは難しいと言えます.

 Numerical Optimizerは,

  • 下界値テストに供する実行可能解を高速に求める方法(ヒューリスティクス)
  • 分枝の際に選択する変数を選ぶ方法の工夫(分枝変数選択)
  • 緩和問題の解を元の問題に近づける工夫(切除平面法/前処理)

といった技術によって分枝限定法の効率化を計っていますが,いずれもヒューリスティックなものですべての問題に対して効果を発揮するものではなく,調整のためにはパラメータ設定が必要な場合があります.パラメータ設定の具体的な方法については「整数計画法(simplex/asqp)/大域的最適化(global)に有効なパラメータ」の項に解説があります.


 

 

上に戻る