改善方法を構想しました。
一つには、BranchingTreeのパラレル化です。マルチスレッドで、残っているBranchingTreeを潰していきます。ネックは、グラフを解く速度ではなくリニアソルバCLPの速度であることが分かっているので、CLPのマルチスレッド数がその上限の速度向上となります。しかしながら、この方法でも十分ではありません。
そこで、LB改善専門の専用スレッドを立ち上げます。このスレッドは、LB(Lower Bound)が求まったあとに、通常のBranching Tree Search（左側）とは独立、かつ並列にLBだけを改善します。
LB改善とは何か？というと、リニアソルバで求めたBranching Tree Rootのフラクショナルな値を整数化していくことです。それでは、Branch＆Boundと何が違うか？というと問題を分割しません。Rootのまま行います。なので、そこでフラクショナルを整数に出来たとき、何某かLB改善に寄与するはずです。その問題の目的関数値の最小公約数で決まる値以下にUB-LBギャップまで改善出来た場合、最適値証明が完了します。INRC2の場合は、最小公約数は、５です。（重みが１０，１５，２０，３０）です。必ずしも全てのFractionalを整数化する必要はありません。UB-LBギャップー５>=0となるまで改善出来れば十分です。別な言い方をするなら、全てのFractionalを整数化出来た時、UBが未知だとしてもリニアソルバの値が即最適値UBとなります。
INRC4Weeksのように通常は、左側ループのみで厳密解が求まります。しかし、長時間廻しても求まらない、若しくは求まらない可能性を考えて右側ループも最初から廻します。現在の状況からするとINRC8Weeksの場合は、1時間も廻すともうこれは尋常ではない＝BranchingTree爆発ということが分かるので、その時点で右側に全力投入したほうがよいかもしれません。
これは、INRC8WEEKSに対して8時間以内に厳密解が求めるためのアイデアであり、やむにやまれず、手段を選んでられない状況から考えました。もう意地になっているいうか、これを解くことが自分の使命のように思い込んでしまっている自分が怖いです。
ところで、整数計画創始者ゴモリーの考案した方法は、ゴモリーカットと呼ばれています。
CPLEX→CLP/Gruribi→ZIB/Highs→COPT
という最近のCOPTの攻勢をみるにつけ、アカデミックなバックグラウンドは、全て繋がっている、のが面白い、というかそれだけ難しい分野ということが言えると思います。最先端のMIPソルバを開発できる人は、非常に限られており、会社から会社へ移動することによって成長と遂げてきたという歴史があります。COPTの中の人達も、スタンフォード出身だったのですね。
とりあえず、この方法を菅原カットと呼ぼうと思います。平面削除は、アナログをデジタル化する方法です。一方、菅原カットは、デジタルからアナログを改善する方法です。実装してみて、どんなものなのか、今後数週に渡り、実装・評価していきます。
0 件のコメント:
コメントを投稿