INTC2 Shift type successions

 H3. Shift type successions: The shift type assignments of one nurse in two consecutive days must belong to the legal successions provided in the scenario

シフトに関するハード制約になります。

基本的には、逆循環を全て禁止にしています。日勤（D）の後に早番（E）は、NG.

遅番の後は、早番・日勤がNG.　夜勤の後は、早番・日勤・遅番がNGです。

これは、ハード制約です。このハード制約の有無でのグラフが次です。

上がハード制約なしで、4842ノード、下がハード制約ありで、2784ノードです。

グラフが大きく変化していることが分かります。ハード制約があると、解空間・探索空間共に減少します。ソルバにとっての負荷は、ノード数に比例しますから、ハード制約があった方がソルバにとっては嬉しい訳です。

実は、上のグラフは、基数制約は入っていません。グラフが大きすぎてGraphvizが描画することが出来ません。基数制約のみならば、可能ですが、全ての組み合わせを合成したグラフでは、巨大すぎて描画できません。ノード数で言うと通常のインスタンスで数万ノード、大きいと数十万になります。再挑戦を予定しているScheduling Benchmarksの未解決問題では、100万ノードを超える規模となります。

INRC2の8Weeksの規模は、数十万ノードになりますが、十分に高速な演算速度(2ms以下)で計算できるようになりました。勿論、世界最速で、現行スケジュールナースも含めて既存のものに対して30－50倍速になると思れます。これを用いて、しばらくは、INRC2に特化した評価と実装改善により全ての厳密解を提示する予定です。これだけ高速だと特別な事をしなくとも普通にBranch＆Boundして厳密解が見つかる可能性は高いと思います。

実装展開は9月以降を予定しています。

一方、Scheduling Benchmarksのネックはそこではなく、バリアソルバです。これについては、HIGHSのGPU版は精度的に期待できないので、COPTのライセンスを得て再挑戦ということになると思います。全ての未解決NSPを解決したのちに、論文化する予定です。提出された全てのベンチマークテストにおいて、厳密解を単一のソルバで実現することが積年の夢でした。どうなるかは、未だ分かりませんが。