Branching DepthとFractionalsの関係

 次のグラフは、Instance22上での、Branching Depth とLpソルバのFractional数をプロットしたものです。

大まかに言って、Branchingが進めば、Lpソルバの値で、Fractionals（整数０でも１でもない、その間にある数）が減って行きます。SimplexとBarrierソルバの比較では、Simplexの方がFractionalsの数は、減る傾向にありますが、速度的に問題外のため、この規模では、Barrier　ソルバ一択です。注意するべきは、Fractionals以外の点、つまり０か１の整数値は、Validな値という訳ではなく、Branchによって、整数になったりならなかったりします。なので、整数になった、即0/1確定、ということではありません。しかし、一時的な整数値にせよ、大半の整数値は、正解であることが多いので、それを信じて整数化HeurisitcsであるMaxSATを走らせる、というのが、私の整数化方法です。当然、Fractionalsの数が少なければ少ないほど、真値により近づける可能性が高まります。

Branchingを最後まで行い、Fractionalsが0になれば、全部整数になったということなので、整数解が得られます。しかし、それは膨大な時間がかかってしまうので、上記Heurisitcsを導入し、整数解をなるべく途中段階で拾う、ということを行います。上の例では、MaxSATソルバBranch　Depthに応じて4回起動して、4回目に最終解を得ています。

Depth0（ROOT）では、Timeout設定が良くなくてTimeoutになっていますが、UB＝3万数千といったオーダになります。通常は、Branching　Depthを早く稼いだ方が速くより小さなUBを得ることが出来ます。、Instance22の場合は、500Depth程度で、かなり近い値、1000Depthで、収束値に到達しました。

以上が数理ソルバでのBranchingの動きになります。