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が解ける筈がない）

第3世代AL1(SAT)から第4世代AL3(LP)へ

 下記資料中、

Q.　4page 「人的リソースの物理限界まで配置が可能」とは、どういうことか？

質問を頂きました。

 https://www.nurse-scheduling-software.com/japanese/publications/Schedule_Nurse_Presentation_for_AI_modeling_and_state_of_the_art_solver.pdf

Ans.　

誤解を招く表現で申し訳ありません。正しくは、

「世界で一番、人的リソースの物理限界まで配置が可能」

です。絶対的な意味ではなく、相対的な意味になります。

そもそも、ナーススケジューリング問題は、規模が大きくなれば、組み合わせ爆発が生じ、リーズナブルな時間内には、解が求められない、ということが証明された問題分野（NP困難）にあります。このことが意味しているのは、「どんな規模の人的リソースでも物理限界まで配置可能」という命題は数学的にあり得ません。

なので絶対表現ではなく、他と比較して相対的に、ということを意図していました。

では、具体的に何が違うのか？　アルゴリズム上の観点で、説明します。

AL1は、現在のスケジュールナースの基幹アルゴリズムで、SATソルバベースのアルゴリズムになっています。201ｘ年のMAXSAT Competitionで、4カテゴリ中3カテゴリで優勝しましたが、それをベースとして、これまで、進化してきました。

AL3は、現在もリリースされてはいますが、問題分野がアカデミックなベンチマーク専用という意味あいが強く、実務的な貢献は殆どされていません。そのコアアルゴリズムは、数理ソルバあるいは、LPベースのソルバ、世の中にある汎用最適化ソルバ(MIPソルバ）の類と同じ学問分野にあるアルゴリズムで、AL1のSATソルバベースとは全く動作原理が異なります。

AL1 は、通常規模のナーススケジューリング問題については、無類の強さを発揮しますが、規模が大きいかつソフトエラーが多発する問題は、弱いという傾向があります。この弱点がもっとも顕著に出るのがアカデミックベンチマークです。逆にこの弱点を克服するべく、未解決のアカデミックベンチマークを全問解くという目標を掲げ、実際最後の1問を残すのみという研究実績を積み重ねてきました。

この挑戦の過程で、多くの知見を得ることが出来ました。それを現在のAL1と同じく市井の実務問題を解くソルバに技術移転することが次の課題として残っています。この課題解決の後に、ユーザさまは、AL1/AL3、好きなソルバで作業することが出来るようになります。

規模が大きい、あるいは、ソフトエラーが多発する、あるいは、物理限界の極限まで、スタッフの希望休みを詰め込みたい、といった用途には、AL3を使用することになると思います。私の経験則は、ほぼすべての師長さんが、「スタッフの希望休みを全部(極限まで)詰め込みたい」ですので、勤務表リリース前の最終段階では、結局、AL3が使用されることになる、と見ています。

もう一つの誤解は、高速性です。求解が高速であることと、求解品質は、関連がありません。高速だけども低品質であってはなりません。これからの指標は、高速であることは勿論ですが、どれだけ、「スタッフの希望休みを全部(極限まで)詰め込めるか？」です。

このスケジュールナースのエンジンが広く行き渡れば、100万人いる？日本の全てのシフト看護師・介護師に恩恵があると思うので、1社に限定することなく、広く世の中で使われるように積極的にライセンス展開をして行きたいと思います。

ユーザさまよりメールを頂きました

永くお使い頂いているユーザさまより メールを頂きました。

＊＊＊

思えば、2016年ごろにスケジュールナースを見つけて、

使わせていただいてから、もう10年近くになります。

最初の頃は、記号記述のような制約入力方法と格闘していましたが、

すぐに、わかりやすいUIに進化して、性能も向上して、

次々と新機能も追加され、使いやすさがアップしていきました。

使えば使うほど、こんなこともできてしまうのかと、スケジュールナースの

ポテンシャルの深さには、今でも驚かされています。

幾度となく、厳しく複雑な勤務条件にも遭遇しましたが、

スケジュールナースの性能と柔軟な制約記述方法のおかげで

条件をクリアすることができて、勤務の質も看護の質も落すことなく

ベストを目指した勤務表作成ができています。

スケジュールナースと菅原さんには感謝しかありません。

本当にありがとうございます。

＊＊＊

永くお使い頂きありがとうございます。引き続いて、第4世代（新ソルバ）、第5世代（AIモデリング）を準備中です。現在、世界記録更新で最後の1問に苦闘していますが、この挑戦で得た知見をフィードバックして汎用実務問題で他を圧倒するスケジュールナースがさらに進化した版ソルバを今年中に、リリースしたいと思います。

また、検証・ご評価をお願いできればと思っております。宜しくお願い致します。

Q.6月以降のカレンダーが表示されない

Q. 5月の勤務表作成にあたり、制約日の設定をしようとしたところ

6月以降の制約終了日のカレンダーが表示されなくなりました。

開始日、終了日、表示日すべて６月以降の表示ができないようです。

設定等の変更の必要がありましたら、ご教示ください。

Ans.

古いエディションをお使いのようです。（ご案内が漏れていたようです。）現在リリース中のエディションは下記二つが全てです。

https://schedule-nurse.blogspot.com/2025/12/qprivate.html

上記以外のサポートは全て停止しました。

恐れ入りますが、移行手続きをお願いいたします。

グラフのフォワードとバックワードスキャン

 前回は、ボトムアップに構築しましたが、トップダウンで、構築する方法もあります。

ボトムアップと、トップダウン、Forward/Backwardという呼び名もあります。どちらが正解ということはなく、どちらでもよいです。

二つの方向から、計算するのは、ノードを削減するときです。

そのノードを通ると最適値を上回ることが分かっているなら、そのノードを削減出来ます。

ダイカストラのアルゴリズム

 下図は、グラフアルゴリズムの様子です。

親ノードは、T枝とE枝があります。T枝は、Then,E枝は、Else.　T枝、E枝の先は、子ノード

になります。子ノードの値（浮動小数）をval0,val1とするとき、親ノードの値は、

tval=val1+coeff1

eval=val0

if (tval≦eval) val=tval;

else val=eval;

最小化・最大化を≦の向きを変えることで、求めることが出来ます。

動的計画法とダイカストラのアルゴリズムは同じ意味？

 結論から言うと、これらは同じものではありません。

アルゴリズム３で中核となすアルゴリズムは、ダイカストラのアルゴリズムです。簡単に言うと、グラフがあって、その最短重み和の経路を求めたいとき、一度計算した結果をメモしておくやり方です。この考え方は、深宇宙通信で使われる符号化方式、ビタビアルゴリズムに本質的に似ています。と言うよりも、ビタビ教授自身、類似性を認めています。

ダイクストラ法は、動的計画法（DP）の考え方を利用したアルゴリズムの一つ、という関係性です。 っくりとした違いは以下の通りです。

• 動的計画法（DP）：大きな問題を小さな部分問題に分けて解く、「考え方の枠組み（手法）」のことです。
• ダイクストラ法：グラフの最短経路を求めるための、具体的な「手順（アルゴリズム）」のことです。
• イメージとしては、「料理（動的計画法）」という大きなジャンルの中に、「カレーの作り方（ダイクストラ法）」という具体的なレシピがあるような関係です。

ダイクストラ法は、「今の地点から一番近いところを確定させる」という手順を繰り返しますが、これは「過去の計算結果（確定した距離）を使って次の計算をする」という点で、動的計画法の仕組みに基づいています。