スケジュールナースのブログ

2026年4月3日金曜日

前方グラフと後方グラフによる削減

単純にFowardとBackwardを使うと上手く行きません。

下図で、前方和と後方和を各々足して、各ノード共、a+b+cにしたいのですが、

単純にすると、そうはならないことが分かります。

どちらか一方の和は、一歩引いて、a+b+c　となるようにします。

2026年4月2日木曜日

Ryan-Foster Branchingとは

0/1　Branchingだと、1側が重いのに比べて0側は、軽い、と言うかあまり効かないことが多いです。こうした偏りを是正する方法として、Ryan-Foster　Branchingと言う方法があります。

例えば、

休休　A

勤勤　B

休勤　C

勤休　D

A/B とC/DでBranchingします。比較として、通常ブランチ

休

～休み

を考えてみます。休＝１でブランチとすると、これはかなり強い限定になります。しかし、～休=0のブランチは、休み以外を選択するわけで、弱い限定になります。この傾向はシフト数が多くれば多いほど、強まります。１が強い限定を生み、0が弱い限定しか生まない、ということは、Tree構築においてバランスが悪い結果となります。1ブランチの枝は短いのに対して0枝は、長い枝になります。なので、なるべく同じ確率となるようにしたい訳です。これが、Ryan-Foster　Branchの背景になります。

複雑な割には、効果が少ないと判断して、スケジュールナースでは採用していませんが、SCIPでは、割に使っているようです。

SCIP Doxygen Documentation: Ryan/Foster branching

2026年4月1日水曜日

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

2026年3月31日火曜日

第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社に限定することなく、広く世の中で使われるように積極的にライセンス展開をして行きたいと思います。

2026年3月30日月曜日

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

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

＊＊＊

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

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

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

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

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

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

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

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

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

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

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

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

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

＊＊＊

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

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