ストロングブランチ

 Instance18は、厳密解には到達するものの厳密解であることの証明 =LB==UBが出来ていませんでした。8時間探索し続けましたが出来なかったのが、ストロングブランチを適用することにより、厳密解として解くことが出来ました。

ストロングブランチは、昔からあるテクニックで、パテントがあったとしてもとっくに切れているはずです。

ストロングブランチを行うのは、通常BranchingTreeのTopから最初のn levelで行います。通常、fractionalな値を持つ変数は、複数存在します。それらは、次のBranchingの候補となります。それらの候補のどれが最もふさわしいかは、実際にBranchしてみないと分かりません。実際に暫定的なBranchingを行い、候補から絞りこむ作業を多分、ストロングブランチと呼んでいると思います。

最初のn levelしか行わないのは、コスト(計算時間）がかかるからです。実際に全てのfractional値に対して行う訳にもいかないので、ある程度確率的にコストと効果を睨んでレベルと候補数を決定する必要があります。

具体的には、候補に対して、branch後の目的関数値が最も高いもの(悪いもの）を選びます。例えば、

branch1 のTrue値　1361 False値　1370

branch2 のTrue値　1359 False値　1365

...

候補がいくつかあるものとします。この場合、branch1の選択になります。良い値ではなく悪い方を選ぶのがミソです。これをTree Top付近で行うことによって、Branching Treeが極端に小さくなる場合があります。(常時、小さくなるのではなく小さくなる場合もある。）結果、全てのTree分岐を見ることが出来て、有限時間内に厳密解であることが判明する、という仕組みです。

その効果は、時として絶大で、Instance18では、

8時間以上　→　136秒で厳密解証明が完了

となりました。Gurobiでは、前回(Ver9.01)1351sec、今回(Ver9.50)735秒だったので、中々優秀な結果です。

採用することにしました。

また、Instance19も、厳密解証明が出来るようになりました。

これで、Instance22以下で厳密解証明が出来ないのは、Instance9とInstance15のみとなりました。