SchedulingBenchmarks instance15再挑戦

 マルチスレッド化して様子を見てみました。スレッド数は８にしました。下記は、テスト中の様子です。

約２日走らせて、LB＝３８２６．６　UB＝３８２８となっています。なので、UB＝３８２７が発見されれば、即終了です。後、僅かのように見えますが、実際には、BranchingTreeの爆発状態にあり、終了まで２週間程度かかる見込みです。（大体こういうテストをしているとWindows強制アップデートによりテスト途中終了となってしまうのが常です。）

経験的には、ここまで来て未だUB=3827を発見できないということは、その解は本当に存在しない、すなわちUB=3828こそが厳密解である可能性が非常に高い、ということです。ただし、UB=3827解が存在しないという厳密な証明のためには、LB=3827プラスアルファとなるまでBranchingTreeをスキャニングする必要がある、ということです。

CPUの稼働率を見ると、

上のように、稼働率100%とはなっていません。Hyperthreadを加味して最低50%程度稼働しているべきなのがそうなっていないのは、キャッシュヒット率によるものであると推察されます。

A)この稼働率を上げることが出来れば、速度アップとなるはずです。

B）もう一つの問題として、インスタンス23以上では、128GBRAMをもってしてもグラフ規模が大きすぎてコンパイルできない、という問題があります。

A)B)の両方を一挙に完結する方法として、グラフの縮約化があります。要するにメモリのダイエットです。厳密解を得るのに必要な緒元を失うことなしに、ダイエットを行うことは、instance15を解くことは勿論ですが、instance23を解くにも必要なことです。

この方法が実用化出来れば、アルゴリズム３の使用頻度が3%から20%位に上がるかもしれません。というのは、多くの実務インスタンスにおいてもグラフコンパイル速度がネックとなっている為です。

instance15だけを見れば、cutting plane 的なアプローチの方が適しているように思えますが、グラフダイエットこそが本丸であると思います。そしてそれは、アルゴリズム３実用化のために必要でもあります。アルゴリズム３の実用化は、これまで知られていない多くの実務インスタンスの厳密解を知るのに大きく寄与するはずです。