Instance22世界記録更新 By Algorithm3

 更新しましたが、未だ途中経過なので承認申請はしていません。

UB:31279⇒３１１６１(Search Spaceがまた前回(Instance21)から上がって、１０の18953乗になっています。）

今回は、Algorithm3によるソルバでの途中経過です。Algroritm3は、Near Optimalなアルゴリズムで、基本的に厳密解を保証しません。厳密解アルゴリズムは、Algorithm4ですが、今までの評価では、Algorithm3がAlgorithm4に精度的に劣るケースは発見されていません。また、Algorithm4では、instance21以上では、実質的にコンパイル不可能ですが、Algorithm3では、(解けるかどうかは別にして)コンパイルは可能です。また、実務的インスタンス、例えば池上ベンチマークもAlgorithm4ではコンパイルできませんが、Algorithm３では問題なくコンパイル可能です。まとめると、

Algorithm1：SAT系ソルバ

Algorithm4 :数理的ソルバ　(コンパイル出来れば)速い　厳密解探索用、コンパイル出来ないことがある。

Algorithm3 :数理的ソルバ　汎用　Near Optimal。  Algorithm1で時間がかかる場合、精度と速度で有利（ソフト制約が多数かつ多数のソフトエラーが残る場合）。また長大規模(3ヶ月以上）または、大規模(100人以上)でも、Algoritm1より有利になります。コンパイル出来ないことはないことを目指している。(しかし、経験的に枯れたAlgorithm1レベルになるには１年以上必要）

CPUコア数が、多くなればなるほど、Algorithm3は有利となります。また、この条件下での学術ベンチマークでは、Gurobi/Cplex、AutoRoster含め他のソルバを圧倒します。

現在、Algorithm3についてベンチマークの評価とチューニング作業中です。

実務インスタンスについては、シフト系については、実装を完了していますが、タスク系については、未だ実装していません。また、ペア制約も現在実装未です。