The Significance of Solving Instance 24 - インスタンス２４が解かれた意義

 Although I cannot strictly claim to have “solved” the problem without a formal proof of optimality, let us allow ourselves to say it is solved, given that the LB–UB gap is only 0.00247%.

For decades, the nurse scheduling problem has been treated as a textbook example of NP‑hardness. The common belief has been simple: because it is NP‑hard, obtaining exact optimal solutions is essentially infeasible. Textbooks and academic literature have repeated this narrative, and even today most of them focus on approximation methods and metaheuristics rather than exact approaches.

NP‑hardness tells us that as the problem size grows, solving it within a reasonable time becomes difficult. But the theory says nothing about what that “absolute size” actually is. It certainly does not claim that real‑world NSP instances must be impossible to solve.

We NSP researchers have spent years trying to understand where that boundary truly lies—or to push it further. Now that the largest instance in history has been solved, it becomes harder to rely on the old excuse that “real‑world NSPs are NP‑hard, so of course we cannot obtain optimal solutions.” This does not mean that every real‑world NSP will suddenly become solvable, but it does suggest a small paradigm shift. After all, every academically published benchmark instance has now been solved. At the very least, textbooks will need to be updated.

For INRC1 and INRC2, all optimal solutions have been obtained. For Scheduling Benchmarks, the final remaining instance has been solved with a gap of only 0.00247%, essentially optimal. With this, I consider the long‑standing goal of solving all academic benchmark instances to be complete. (The pursuit of GAP = 0% is left to future researchers.) It has taken nine years since my presentation at RAMP. Back then, none of INRC2 and only about half of Scheduling Benchmarks had been solved. It is thanks to the achievements of pioneers such as Tim Curtois, and the advanced capabilities of the COPT Barrier Solver, that we have finally reached this point. This long challenge now comes to an end.

Finally, I close this post with gratitude to my wife, who supported me without complaint through a challenge whose feasibility was never guaranteed—something that would never be tolerated in a private company.

Optimality証明が出来ていないので解けたとは言えないのですが、LB-UB=GAP=0.00247%に免じて解けた、としましょう。

今までナーススケジューリング問題は、NP困難の代表的問題とされて、NP困難だから、完全な最適解を得ることは困難だ、というのが一般的常識でした。実際、組み合わせ最適化関連の教科書や文献では、そのような記述がされてきて、今でも教科書は、厳密解を目指さない近似解法、メタヒューリスティクス的解法の紹介が主です。

NP困難は、規模が大きくなれば、やがてReasonableな時間内に解くことは困難な問題である、ということです。しかし、理論は、その絶対規模については、何も表明してはいません。現実の市井のNSPがそうである、とは言っていないのです。

私達、NSP研究者は、その限界がどこにあるかを知りたい、あるいは、その限界を少しでも遠くにやりたい、ということを糧にして研究活動を行ってきました。

今回、史上最大規模の問題が解けたからには、市井のNSPが、NP困難だから解けなくて当たり前（最適解は分からなくても当然）、という一般常識や言い訳が、言いにくくなった、ということです。もちろん、全ての市井のNSPがただちに解ける、ということではありませんが、これまでの一般常識を少しだけパラダイムシフトする効果はあるかもしれない、という意義があります。論文として公表されているすべてのアカデミックベンチマークは解けたのですから。少なくとも、教科書は、修正する必要があるでしょう。

INRC1,INRC2については、全ての最適解、SchedulingBenchmarsについては、最後の1問についてGAP=0.00247%とほぼ最適解を得ることが出来ました。これで、アカデミックベンチマークを全て解く、という目標は完遂したとします。（GAP＝0％については、後進に託します）RAMPでの発表から実に9年を要してしまいました。あの当時、INRC2は全問、SchedulingBenchmarksは、半分程度しか解かれていませんでした。Tim Curtoisさんら先人の業績や、COPT Barrier Solverという先進のソフトウェアがあって初めてここまで来ることができました。永い挑戦もこれで終わりです。

最後に、民間企業ならば、到底許されることはない、実現できるかどうかわからない挑戦に対して、文句も言わずにずっと支えてくれた妻に感謝し本稿を閉じます。