Cumulative Capacity Cut、「MIPソルバに投げる」は、失敗

 またしても、アプローチが失敗しました。

キャパシティカットが良さそうでしたので、

https://schedule-nurse.blogspot.com/2026/03/blog-post_22.html

さらにこの発想を強めて(Tightening)、Day毎の累計制約として抽出しました。具体的には、休み数制約（制約としては存在しないものの時間制約や総勤務数制約に相当）と、土日勤務数制約のDay毎の累計制約として取り出して、LB取得後にMIPソルバに投げるというものです。この方法をCumulative Capacity Cutと命名しました。発想は、Roster毎の資源総計だけではなく、Day毎の資源を明示することによって、Cover制約達成を促進する狙いです。

結果は、

これにより、例えば、インスタンス2/4/14は、Lpソルバの段階で、真のUBに等しくなり、COPTでもHIGHSでも一瞬で解けています。また、真のUBに近接した結果となった、インスタンス10,11,12,20についても速いです。これらの結果は、スケジュールナースが維持する世界最速記録よりも速いのではないかと思います。

この結果、Lpソルバが真のUB値と等しくなったときに、UB値でカットオフしなくとも（MIPソルバは真のUB値を知らない）MIPソルバは一瞬で、UB値を算出できる、←SATソルバより速い、ということが分かりました。

で、問題はインスタンス13になります。このインスタンスに関しては、期間は1カ月であるもののシフト数は19と多く、スタッフ数120人と、いわばインスタンス24のミニチュア版、と見ることもできます。残念ながら、Lpソルバの段階で、真のUB値には遠く、MIPソルバに渡しても、長期の時間がかかっています。ただ、COPTにしても解けなかったインスタンス13が有限時間内に解けるようにはなったので、一定の効果があることは分かります。

まとめとして

１）LpソルバのLBが真のUB値に等しいとき、MIPソルバが最強。SATソルバより速い

２）LpソルバのLBが真のUB値から遠ければ遠い程、MIPソルバが解けない可能性が高まる

３）LpソルバのLBを上げることは正義

ということが分かりました。市井の実務インスタンスは、インスタンス8程度なので、実務インスタンスにおいてMIPソルバを活用できる場面もある、と考えます。(SAT整数化より速い場面もある。)　

いずれにせよ、このアプローチで進んで、インスタンス24が解ける見込みはないと判断しました。（ミニチュア版でこの遅さなら、超巨大インスタンス24が解ける筈がない）