Branching Treeの可視化

 Algorithm4のデバッグをしていて必要になったので作りました。定番のGraphVizで可視化しています。このツールは、Verilog　Simulatorでもお世話になっていて使うのは10年振りくらいです。

Instance8のBranching　Treeです。このインスタンスの厳密解はLB=UB＝1300が知られています。Branchingを行うのは、最適解、すなわち目的関数値が最小になる整数解を得るためです。連続変数での緩和解は、ROOT　Nodeの値1296.57として得られています。

で、Branchingを行って、それまで得られた最小の整数解以上の目的関数値だった場合、そのノード以下は調べる必要がないという状況が生まれます。これをPruneすると言います。PruneしたNodeでは、子Nodeがありません。たとえば、So Far　UB=1300が得られている状況で、連続緩和解1299.1が得られたとします。重みの種類は1,2３,100であるとすると、整数解の目的関数値は1300が有りえる値です。その値は既に得られているので、もはやそのNode以下は見る必要がない、ということになります。

そう風に、ありえる全てのノードを調べて最適解を探します。一般にNodeを下降していくと、LBは上がって行きます。あるレベル（段）では、もうこれより小さなLB値は有り得ないということが分かります。そうすると全体のLBも上げることが出来ます。また、Prune効果によって、調べるべきNode数も減少していき、ついに調べるNodeがない(Empty)状態になったとき、LB==UBの証明、となる訳です。

組み合わせ最適化で爆発するのは、このBranching　Treeが調べても調べてもNodeが増え続ける一方という状況です。こうなると有限の時間内に最適解を見つけることができないので、LBとUBの間にGapが生じたままになります。よく論文でGAPが何％以下になった、という記述がありますが、これは、調べるべきNodeをEmptyに出来なかったという裏返しでもあります。

LBに近いLBが最初から分かっていれば、PruneできるNodeが増えて、結果的に調べるNode数を減らせるので嬉しい状況です。その目的の為、ヒューリスティクス解を使うのも良くやる手法です。また、出来る限り早期にLBに近いUBを得たいので、最初はDFS(Depth　First　Search)を行うのも常道手段です。

こういった手順を踏むので、最初の実行可能解が得られる時間が長いのがAl4の特徴です。また得られる整数解は、離散的にしか得られません。(AL1みたいに一個一個減りません)

しかし、Al1では難しいインスタンスでも、時間をかければ厳密解に到達する可能性が高いのが特徴です。今回のRefactoringは、昨今のManyCore環境を生かしたコンセプトになっており、コア数が多ければ多いほど高い能力を発揮します。コア数が増え続けるのは今後も変わることのないトレンドでしょう。主体はAL1で変わらないとは思いますが、AL4を使う場面も多くなってくると予想しています。