申し訳ありません。対応は行っておりません。
様式9については、以下が詳しいですが、
https://lp.henry-app.jp/column/yoshiki9
どちらかというと勤怠管理の範疇に属します。加算要件を満足させるためのシフト要件については、スケジュールナースで如何様にも記述可能です。が、その中で用いられるシフトは、モデリング（簡易化）したものであり、実勤務時間を正確に記述したものではありません。
https://www.nurse-scheduling-software.com/japanese/nurse_scheduling_problem/chapter33/
それを実勤務時間形式である様式9に落とすには、
スケジュールナースExcel解⇒様式9Excel
へ変換を行う作業となります。
言い換えれば、シフト要件に特化したスケジュールナースの範疇ではなく、モデリングしたシフトと実勤務時間との対応を把握している病院サイドでの対応というスタンスとなります。
Ans.
似た実装として例として、以下があります。
https://schedule-nurse.blogspot.com/2024/04/q_14.html
題意は、特定のスタッフとそれ以外との夜勤ペア回数を最大１回にしたいということですが、
これは、日々の列制約（全てのペア組み合わせ）に対して、行制約＝今月期間中に最大１回と、列と行の複合制約となります。こうした複合制約については、Pythonでしか書けません。
以下は、プロジェクトを走らせた様子です。解がない可能性がありますので、
■ソフト制約にする（ソフトレベル設定で、適用と重みを設定）
することと、言語制約にチェックを入れることが必要です。
実装は、以下となります。Python記述は、ブラックボックスとして扱えるように記述しています。（僅か十数行です。”夜勤”の部分をご自分のプロジェクトのシフト名に入れ替えれば汎用的に使える記述です。）
import sc3
def ペア回数制限Sub(person1,person2):
if person1==person2:#同じ人は制約しない
return
list=[]
for day in 今月:
v1=sc3.GetShiftVar(person1,day,'夜勤')
v2=sc3.GetShiftVar(person2,day,'夜勤')
list.append(v1&v2)
s=staffdef[person1]+"と"+staffdef[person2]+"の組み合わせ回数"
print(s)
sc3.AddSoft(sc3.SeqError(0,1,3,list),s,5)#min max allowable errors 最大1回に制限
def ペア回数制限():
for 特別person in 夜勤ペア最大１回:
for person in 全スタッフ:
ペア回数制限Sub(特別person,person)
ペア回数制限()
■メインリニアソルバ
INRC2 ８Weeksの規模に対しては、明らかにHighs IPMが有利です。ソフト制約が基数制約にある場合は、より有利に働くと見ています。
Instance23/24については、今のところ、Highs PDLP一択です。（近い将来 Highs IPMがGPUを使ったコルスキー分解をサポートするようになれば、PDLPを使わない可能性はあります。）
■サブ問題(RCSPP)
instance22 以上では、グラフ化が出来ないので、基数制約以外をグラフ化する方式にしました。なんとか、Rootまでは、持ってきたものの、それ以降のBranch＆Bound操作で時間がかかりすぎることが分かりました。
R_calc_timeがその計算時間で、ときに10分以上要しているのが分かります。100Rosterだと、その100倍かかり、さらにそれが数回以上収束に要しています。
このままでは、1カ月経っても目的Depthまで到達することは出来ません。想定Depthは、１０００で、１Depthに数時間かかるようでは、到底現実的な時間内には、収まりません。大規模Lp問題に取り組む前に、まずこの問題を解決する必要があります。
Highs ipmをinstance22 を W/O Cardinals Graph in rosterで走らせると、24時間経ってもROOT LP値を得ることができません。
現状のHighs ipmで行うと、恐らくは、一カ月以上計算機を廻さないといけないでしょう。そこでPDLPに期待がかかるのですが、高精度、kkt_tolerance=1e-7にすると、IPMと時間的には大差ありません。(4060Ti)
そこで、初期は、精度を落として、1e-4からスタートし、徐々に精度を上げる方式を取ることで、高速化できないかを検討しました。1e-4ならば、高速に解が得られます。また、解の安定性のための初期スケーリング処理も必要ないようです。
下のグラフは、kkt_tolerance=1e-4での目的関数値の変化のグラフです。
Q.夜勤と当直の行制約で以下を実現するにはどうしたらよいでしょうか？
①
当直数を個人ごとに最大―最小パターンで最大数と最小数を決める
②
夜勤数も同様に最大―最小パターンで最大数と最小数を決める。
③
当直数と夜勤数の合計を最大―最小パターンで最大数と最小数を決めて、その範囲でシフトを割り当てる。
例
スタッフ名１は月当たり当直を１～２回、夜勤を１～０回、当直と夜勤の合計が１～２回の勤務条件とした場合。
月当たりの当直数と夜勤数のパターンとして次の４パターンになるかと思います。
|
当直（１～２回） |
夜勤（０～１回） |
計（１～２回） |
|
２ |
０ |
２ |
|
１ |
０ |
１ |
|
１ |
１ |
２ |
|
２ |
０ |
２ |
添付したプロジェクトで試しに当直と夜勤をシフト集合で深夜としてみましたが、深夜のシフトが割り当てられてしまいます。
上表の４パターンのどれかに当てはまるシフトを実現するにはどのように制約すればよいのでしょうか？
Ans.
考え方は、正しいです。ただし、実装が間違っていました。
以下の制約で「深」は、意図した合成集合「深夜」になっていません。
正しくは、これを用いて、次のように制約すべきです。
Condensed Interior-Point Methods for Scalable Nonlinear Programming on GPUs
によれば、cuDSS の性能向上が著しいようです。未だ、Preview版ですが、そのうち正式版になることが期待されます。現在Highs ipm solverは、疎行列に対してコルスキー分解を使用していませんが、近い将来、GPUを用いた高速化が期待できます。
Linear Solver は、PDLPがありますが、高精度を必要な場合は、さほど速度アップを期待できません。その用途において補完できるのではないかと思います。
いずれにせよ、大規模問題については、GPU演算は必須の様相を呈しています。現在取り組んでいる大規模問題についてもGPU(4060TI16GB)のパワー不足が明らかですので、パワーアップを検討中です。
KKT_toleranceを1e-7にすると、IPMよりもかなり遅くなりますし、それでいて精度も未だ十分ではありません。1e-4にして、推定値を求めるにはよいのですが、PDLPで厳密解を目指して最後まで通すには、不十分であると結論しました。
また、WarmStartもやってみましたが、全く効果がありませんでした。
そこで、Rootで、PDLPで推定⇒IPMに切り替えというのが、最も経済的なアプローチということになると思います。 残念ながらHIGHS IPMは、未だマルチスレッド化もされていないし、コルスキー分解のGPU化もなされていないので、相当遅いのを覚悟しなければなりません。
AL1単独で、コンパイルを試みましたが、128GBPCでも出来ませんでした。
リソースモニタを見ると60GB程度まで消費していました。つまり最大の128GBは、消費していないので、SATソルバの限界と見ます。SATソルバの内部は、32ビットのアドレシングであり、その他のビットも割り当てられるために、有効なアドレシングは、30ビット程度です。2^30=1000万Clauses程度までです。恐らくそれを超えてしまったものと推察されます。
ちなみに、Instance23までは、コンパイル出来30GB程度でした。
Instance24は、超長大規模問題ということです。
＜AL1が使えないと＞
AL3中、AL1は、整数化機構として動作します。LPソルバの推定値を現実の整数世界に変換する機構として動作しています。これが使えないということは、LPソルバが整数値を出力するまで、延々とBranch＆Boundを繰り返す必要があります。要するに膨大な時間を要する、ということです。
＜GPU側の課題＞
GPUが１５秒、その他が５０秒程度かかっています。稼働８時間程度で、未だROOT OBJ値は得られていません。
GPUの時間は、安定しない時期もあり１分以上かかっていたときもありましたが、ここ数分みていると安定して以下のようになっていました。
未だよく雰囲気を掴めていません。PDLPの演算時間がこの程度で済んでいるならば、ISM/PDLPの選択は、PDLP一択になります。現状Defaultの精度で。
１）Double⇒Floatによる高速化
２）終段以外は、精度を落として高速化
３）WarmStart処理
等の高速化手段は未だ残っているので、これらが課題になります。WarmStartについては、何もしていません。Highs側で勝手にやってくれることを期待していますが、リリースコメントを見ると、「モデルを変えたらSetSolutionで再セットする必要がある」となっているので、効いているのかどうか分かりません。
＜CPU側の課題＞
CPU側の演算がネックになっています。
１）GetBasisをPDLPでも構わず使っていますが、これが動くものなのかどうか？
２）Roster演算のマルチスレッド化
３）Roster演算で初期Feasibility解を見つけられていない問題
２）について、その方法は前回レポートしました。
３）は、
初期各RosterのFeasible解を求めていますが、Timeoutで求まっていないRosterが数か所あります。Instancfe22までは、綺麗に求まっていたのですが、流石にInstance23は、各Rosterにとっても規模が大きく求まっていません。一旦でも求まれば、後はそれをベースに改善していくので、最終的にFeasibleになっていれば、それでも問題ないとも言えますが、気分的には、よろしくありません。（改善すべきです）
引き続き検証を進めます。
二つのStrategyがあります。
一つ目は、Br＆Bound自体をマルチスレッド化します。
下がこのモードで走らせたときの様子です。thr=スレッドNoになっています。
このCPUの場合コア数は、８なので8threadsで走らせています。
下のように基数制約を全てオフにしてコンパイルしてみました。
課題を確認するためです。
その他に、メモリ所要が多すぎるという問題が露呈しました。
Instance23 3GB
Instance24 18GB
食っています。肝心の核心に辿り着く前に、こんなに食っているのは驚きです。
この辺のダイエットも考えねばなりません。
課題
１）メモリダイエット
２）Roster基数制約をグラフコンパイルしない準最適化方法
３）MasterLP CLP⇒IPM⇒PDLP
同時コンパイルのテクニックを駆使したとしても、Instance22以上では、完全なグラフ化は、困難であることが判明しました。SecondaryCardinalsの3個以上の組み合わせで、メモリ的に破綻してしまいことが、複数のグラフ化方法で確認しました。
そこで、完全なグラフ化を一旦諦めて、次の方針に切り替えることにしました。
１）グラフは、基数制約以外でコンパイルする
２）Rosterの最適値・準最適値は、１）グラフを用いて複数の求解により求める
Roster毎の最適値が求まれば、系全体の最適値も担保できますが、２）で常に最適解が求められる保証はありません。２）が準最適解の場合は、系全体の最適値も準最適解となってしまいます。しかも、それなりに時間がかかってしまうことが予想されます。
どのようにして、最適解を求めるかは、後ほど検討することにして、現時点での課題をまとめます。
１）任意中間ゲートの同時コンパイル化グラフの作成
２）基数制約以下のグラフ化と複数求解によるRoster毎の準最適解導出アルゴリズムの作成
やはり、最後の難関２問は半端ないです。
スケジュールナースの解をExcelにおとしたときに、１日ずれてしまいました。
先月まではこんなことはなかったです。
なぜかわかりますでしょうか。
Ans.
分かりません。スケジュールナースが出力しているのは、ExcelシートSheet1です。
それを整形して施設フォーマットに変換しているのは、Excelマクロでして、スケジュールナースの範疇ではありません。大変恐れ入りますが、マクロで作成された(施設のシステム担当の?)方に診てもらったら如何でしょうか？ （少し眺めてみたのですが、どういう風にコンバートしているのか判りませんでした。）
Instance24を各Roster毎Highsで解いてみました。
Instance24の例えばStaff BOは、次のような基数制約が記述されています。
これに対して、Highsで解いた結果が次です。
この結果は、例えば、Days１年後、a1というシフトは、最大で222であることです。optimalが1になっているので、最適解です。この結果は、他のRosterは我関せず、ですので、これ以上は、どんなことがあってもあり得ない、ということを示しています。
で、シフトa6に関してみると、最大値71に対して制約値も71最大になっています。この場合、a6に関して、制約値とHIGHS最適値が一致しているので、制約が効いていることを示しており、制約を削減することはできない、ということを示しています。
同様に殆どの制約で一致しており、制約を削減することは出来ません。唯一シフトs2だけが、制約値より小さくなっており、この制約だけは、なくても支障ない、と言うことが分かります。
つまり制約が効いていないことが分かります。instance21の場合、他のスタッフについても、同様な結果となっており、要するに全てのSecondary Cardinalsは削除しても全く問題ありません。世界記録を提出したときも、このことを別な方法で分かっていたので、グラフ合成は全く行っていなくてPrimary CardinalsのみのGraphで計算した解を提出しました。今回、Highsでも検証したのですが、Highsによっても裏付けが取れました。
このようにインスタンス毎、スタッフ毎に様相は、異なりますが、縮約の効果は期待できる場面もある、ということです。
なお、グラフだけの演算で解くことが出来ればそれに越したことはありません。今回HIGHSで最適解を解いていますが、instance21規模にしても結構な時間がかかっています。しかし、合成したグラフには、あらゆる最適解情報が詰まっており、一旦グラフ化が出来たならば、任意Daysの最適解は、経路探索によりほぼ瞬時に求まる、ということです。RCSPPの最適解は、グラフが出来たら即完了です。問題は、メモリにそのグラフを納めることが出来るか？の一点にあります。
■Scheduling Benchmarksのinstance22では、PrimaryCardinals制約は、コンパイルできるが、他のCardinals制約と合成コンパイルが出来ない （96GBメモリ）
■instance23では、PrimaryCardinals単体でも、コンパイルが出来ない
という問題があります。これに対処する案の検討を行いました。
Scheduling Benchmarksは、全て同じ形態であり、
業務時間累計に対して最大・最小を規定しています。(Primary Cardinals制約）
さらに、最大連続勤務日数、または、最小連続勤務日数が既定されています。これらは、スタッフ固有の規定です。
Q.
続行を押しても、何をしても5分経ってもソルバは動き出しません。
＜原因＞
恐らく、別なアカウントで起動させた状態でのソルバプロセスが残っていると思われます。
そのソルバを起動したアカウントとは別なアカウントのスケジュールナースでは、残っているソルバプロセスは消せません。（OSの仕様。同じアカウント・同じ管理権限であれば、消せる筈です。）
＜対処方法＞
タスクマネージャを起動して、ソルバプロセスを強制終了させます。
１）タスクマネージャを起動します。
２）ユーザ→詳細で maxsat.exe(ソルバプロセス）を強制終了させます。
万が一それでもダメな場合は、PCをシャットダウン・再起動してください。
⇒
別なアカウントで起動させた状態でのソルバプロセスは残っていませんでした。
使用しているタスクマネージャにもありませんでした。
PC再起動で再使用できました。
Q.
突然、以下のメッセージが出てスケジュールナースの計算が走らなくなりました。
いただいたVer.12に予定入力し、計算させた後、解が出ました。
タスクロックを行い、シフトの調整を行おうとしたところ以下のメッセージです。
メッセージの通りで、求解エンジン（ソルバ）が計算中ですので、「はい」を押して終了させてください。
Interior point methods in the year 2025 - ScienceDirect
で近年のIPMソルバについて解説されていました。Highsの前処理についても解説があり参考になりました。
現在は、次のPhase1に在ると思います。
Highs IPMソルバについては、Phase2で、コルスキー分解によるdirect factoringで並列化がなされるはずで、これの実装待ち、ということになります。
これを待つか、自前で実装するか悩ましいところですが、とりあえずは、Highs1.11 IPMをベースとして、LPソルバ以外の実装を行うこととしました。Scheduling Benchmarksは、時間制限がないので、いくら時間がかかっても問題ありません。
Feasibility Jump等のヒューリスティクスが追加され、かなりＭＩＰソルバの性能が上がっています。（部分的には低下しているベンチもありますが、総じて上がっています。）
下図が、SchedulingBenchmarksの結果になります。この性能だと、CBCの数倍の性能と言ってもよいと思います。
HIGHSの1.11、PDLP版をテストしてみました。
＜PDLP版のコンパイル＞
### Build HiGHS with GPU support
HiGHS must be built, from the root directory, with
cmake -S. -Bbuild -DCUPDLP_GPU=ON
cmake --build build --parallel
＜結果＞
下表がその結果になります。GPUは、4060TISuperです。
COPT版PDLP-Cとの比較では、1e-4でみると、COPT版の方が速いですが、実用的な精度である1e-7でみると、COPT版では、収束しませんでした。従い、速度的には遅いもののHIGHS版の方が、安定的と見ます。MIPソルバでは、1e-7位の精度がないと使い物にならないという事情があると思いますので、恐らくは、HIGHSチームの意図的な設計によるものと見ます。
HIGHS IPM版のとの比較
内点法ソルバが更新された模様で、以前のものより速くなっています。内点法ソルバは、WarmStartが出来ないものの、Analytic Centreを使えば、安定度はSimplexよりも良い、との報告もあります。一方、PDLP版では、インスタンス規模とSpeedとの関係が不明確で、必ずしも規模と速度の相関がありません。（規模の小さいinstance19が最も遅くなっている）
これに対して、Highs IPM版では、規模と速度の相関が安定的であるとも言えます。精度に対するSensibityも殆どなく、PDLPと比較すると、遥かに安定していると言えます。
Highs IPM版は、未だSPARSE行列演算のマルチスレッド化が出来るところもやっていないので、未だ速度向上の余地はあります。何よりGPUを必要としないので、ライブラリの切り替えの手間等がなく実装が楽です。速度もそれなりに期待できるので、未解決残り2問題用のソルバ実装検討には、HIGHS IPM版で行うことにしました。
