■SATソルバが使えない問題
に対して、構造を見直しメモリダイエットを行いました。およそ1/4程度にはなりました。
結果、instance23については、AL1でコンパイル出来るようになりました。このとき、25GB位の消費です。
SATソルバが使えないと、やはり痛いので、なんとかして使えるような検討を行う必要があります。
PDLPの改善版です。3倍程度、特に高精度領域において、改善が著しいようです。
[2507.14051] cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming
■LPソルバが遅すぎる問題
現状では、全く遅すぎて、10倍以上の速度アップが必要ではないかと見ています。
上記でも足りませんが、とりあえず、
ＨＩＧＨＳまたは、Cuopt で、実装されるのを待ちたいと思います。
これまでの世界記録は、
Instance23 ： LB＝16990 UB＝17428
でした。今回、新たに 17284.3 ⇒LB＝17285
であることを発見しました。
大幅なLB更新は確定的で、これまでの経験上、UBもその直近傍(ex 17285)にあると思われます。
しかし、次の
■RCSSP ソルバが遅すぎる
■LPソルバが遅すぎる
■SATソルバが使えない問題
という問題のため、それ以上前に進められていません。
LPソルバについては、
■GPU置き換え
■PDLPアルゴリズムの改善
■新たなIPMソルバの適用
の可能性を検討しました。
日本から、3チームが出場したようです。
PB25 Pseudo-Boolean Competition 2025
名古屋大の酒井先生と山梨大の鍋島先生のチームが優勝されました。
その他にもPrintempsや今井さんも参加されたようです。
Pseudo boolean competition は、昔からあったように思いますが、しばらくお休みがあって、ここ最近復活したようです。最近の潮流は、MIPソルバの使用にあるように思います。
Maxsat competition については、今年はお休みです。一昨年と去年の解けた問題数の差異は、殆どなく誤差の範囲と言ってよいかもしれません。技術的進展がないと、研究者も敬遠するのかもしれません。
The Results of SAT Competition 2025
今年の優勝者は、AE-Kissat-MABで、
DynamicSAT: Dynamic Configuration Tuning for SAT Solving
ダイナミックにチューニングするソルバのようです。明らかに優位性が見れます。
それから一カ月も経たないのに、それを凌駕するとの報告がありました。
Autonomous Code Evolution Meets NP-Completeness
NVidiaのSaturationというフレームワークを使って人がコーディングしたよりも性能が良いソルバを自動生成する、
とのことのようです。AlphaEvolve
Google: AlphaEvolve - Gemini を活用した次世代アルゴリズム設計について #GoogleCloud - Qiita
よりも、より進歩性のあるということを主張しています。
初期のSATソルバとは違い、最近のSATソルバは、細かな改善の積み重ねの結果としてあり、何のパラメータが支配的な性能向上につながるか？というのは、パラメータ数が多すぎてよく分からないことになっていると思います。 こうしたパラメータが多数ある分野でのチューニングは、人間は、LLMには敵わない、と私も見ています。言うなれば、人間勤務表ースケジュールナース勤務表のような関係性です。
最適化ソルバで、研究者自体が駆逐される可能性も出てきるでしょうか？ こちらは、未だ論文化されていない方法が多数あると思われます。（私が取り組んでいるのも、その一つです。）それらが全部オープンにされない限りは、LLMが支配することはないと思います。
逆に言えば、
■最先端技術が全てオープンになっているSAT技術分野でのLLMとの闘い
今後のSAT Competitionは、LLMが生成したソルバが参戦してくるでしょうから、来年以降、過去の技術資産の組み合わせだけで、LLM生成ソルバに勝つのは、極めて難しいと思います。昨今の革新的進歩がないことを勘案すると、極めて不利な情勢です。しかし、一抹の期待を抱かずにはいられません。
Ans.
「できれば2連休を一回以上」ー 赤部GUI指摘箇所
スタッフ１４が９月１５日以降、全日休みになっているので、上記制約の最大記述と矛盾になっています。（ソフト制約ですが、行制約レベル２は、許容エラーが１になっているので、4+1 ⇒６以上は、ハードエラーとなっています。）
従い、スタッフプロパティ、スタッフ１４の責任者記述を、一時的にブランクにすることで
対応するのが、簡単でしょう。
Ans.
下記記述で、先月部末日（＝制約終了日）に夜勤が来ると、次の日は、夜勤明けが来ることが必然となるためです。この際、パターンがヒットしないことに注意してください。
先月部の記述問題なので、今月部は、如何ともなりません。次月よりの改善となります。
前回、解がない場合の解析を行いました。実務場面で、ここまで詳しく見る必要はありません。単に、「９月１９日、グループAの夜勤明けリソースが足りないのだな」ということだけ分かれば、十分です。
しかしながら、実務場面で、予定を入れるたびに、こうしたことに頭を悩ませるのは、好ましいことではありません。ブランク予定で、UB=0が保証されていれば、機械的手順で、予定が変更される部分は分かりますが、一定のスキルを要するので、出来れば、そういう事態は避けるような、恒久的プロジェクトの改善を行うことが好ましいです。
１）列制約のソフト化
グループAのリソースが足りないので、グループBのリソースに余裕があれば、改善する可能性があります。その月で、もし変えることが可能ならば、カットアンドトライでやってみる価値はあります。
４）グループA/B両方対応できるスタッフがいないか？
スタッフ１は、丁度そのようなスタッフなので、グループ集合を変更して制約を変更します。
＜まとめ＞
夜勤明けリソースが居ない問題について
１）予定変更
２）列制約のソフト化
３）夜勤明け後の休みのソフト化
４）グループバランス
５）グループA/Bの両方に対応可能なスタッフ記述
対応する方法を述べました。列行どちらの選択をするかは、重みの選択によります。
大事な事は、解がない⇒原因は様々ある⇒ソルバは、原因に関するヒントを列挙はしますが、上のどの対応が適切かは分かりません。管理者だけが正解を知っているということです。
そして、その正解は、予めソフト制約や重みによって自動的に選ばれるようにしておくことが、恒久対策となる、ということです。
上のような解析は、開発時だけのもので、稼働時には、常に管理者にとっての正解が示されるようにしておく、ということがポイントです。
Ans.
エラー情報をよく見ます。
赤丸部をダブルクリックして飛ぶと、エラーは、全てグループAで起きている、ことが分かります。
次の青部パターンは、冗長です。
従い、次のように記述した方がよいでしょう。
以下のパターンも、前回と同じ間違いを含んでいます。
何が問題かというと、全ての深夜Gメンバに対してそれを強いている、ということです。必ずそれを満たす保証があれば、問題ない記述ですが、中々それを保証することは難しいのではないでしょうか？
夜勤間隔が長いパターンは、ソフト制約として逃げる弁を付けてやるのが常道です。あるいは、スタッフ毎の夜勤回数制約に応じて、制約パターンを分けるというのも手です。
https://schedule-nurse.blogspot.com/2025/04/4endrelease-3.html
次の記述のどこが「まずい」でしょうか？
＜シフト数が多すぎる＞
シフト数は、25程度を目安としてそれ以下になるように心がけてください。
次は、良くない例です。
■業務外日勤カウントあり
■業務外日勤カウントなし
という二つの非自動化シフトにすれば、十分だと思います。その他は、上の別名にすればOKではないでしょうか？ 勿論、管理を別にする必要がある（例えば、個別に人数を制約する必要がある）場合には、使えませんが、同じ管理でよければ、同じシフトにしてシフトの削減を行うべきです。
別名にすれば、メモリを食いませんので、いくら定義してもソルバの負担にはなりません。このお客さまの場合、こうした感じで50以上のシフトが定義されていました。この状態では、ソルバの負担は、測り知れないことになっていると思います。シフトは出来る限り削減してください。
制約を変更したら、直ぐに動作を確認しない方が多いです。
一つ変更、一つ求解確認が基本です。
一つ一つの制約の中身は、
■Day集合
■グループ集合
■シフト集合
から出来ています。各々制約上で集合を確認してください。
人間は間違えます。制約は、プログラムと違い、書いたその場で、動作を確認できるのですから、一つ一つStep by Step、動作を確認して、積み上げていくことが出来ます。そうした方が、結果として早いと思います。
＜ ブランク予定で、必ず解があることの保証＞
開発段階・デバッグ途中では、ブランク予定で、解がないことはあり得るのですが、本稼働場面で、ブランク予定で解がない事態は、絶対に避けなければなりません。
ブランク予定で必ず解があることが保証されていれば、予定を入れて仮に解がなくても、予定を全部ソフト制約にすれば、解は必ずある筈です。予定変更された部分が問題箇所という特定が直ぐできます。機械的な手順で難しいことはありません。本稼働時は、原因解析をすることなく、機械的に処理します。
ところが、ブランク予定で、解がないということは、その原因の解析をしないといけないということであり、スキルを要する仕事になってしまいます。原因の分析は、制約の中身について知らないと出来ない作業です。
また、毎月の予定に対して制約を弄ることは、完成したプロジェクトでは行いません。制約は予定に関わらず不変であること、が安定稼働の条件と考えます。
もし、予定を全部ソフト化しても解がない、つまり、ブランク予定にしても解がないならば、設計不備です。ブランク予定では、どのような月であっても解が存在することを保証をしておくことは、プロジェクト設計の礎です。
どのような月であっても、必ず解が存在するプロジェクトにするには、どうすればよいでしょうか？施設によりその条件は、異なるので一概には言えませんが、月の公休数や祝日数に関係していることが多いので、敢えてそういう条件の悪い月で試して解があれば、一応安心できるでしょう。（ただし、先月からの条件も絡んでくるので、絶対大丈夫とは言えません。）
いずれにせよ、ブランク予定で、先ず解のある状態にしておくことは、基礎中の基礎です。まずは、ブランク予定で開発を進めて、ブランク予定では、必ず解があるようにしてください。
ハード制約が多すぎるプロジェクトも、よくみかけます。ハード制約が一つでも満たせないなら、解がない状態になってしまいます。「ハード制約は、必ず満たさなければ、いけない制約」という理解は、されていると思いますが、必ず満たせる制約である必要もあるのです。逆に言えば、少しでも満たせない可能性がある制約は、ソフト制約にする必要があります。その意味で、「こんなにハード制約があって満たせるの？」という疑問が沸いてくるプロジェクトを拝見することがあります。
行制約と列制約は、互いに干渉しあうので、以下のA）B）いずれかにするのが基本です。
A）列制約がハード制約主体 ⇒行制約はほぼソフト制約とする
B）行制約がハード制約主体 ⇒列制約は、ほぼソフト制約とする
その中で、どうしても実現したい制約のみ（１個か２個程度）をハード制約とします。
行と列どちらもハード制約主体となっているプロジェクトは、解がない状態となる率が高いです。特にリソースを使い切るプロジェクト、いわゆる「人がいない」職場では、解がない状態となる確率が高いでしょう。
お客さまが開発したプロジェクトを拝見する機会が多いのですが、それを見ていて、思うことがあります。
＜仕様書の存在＞
仕様書がなく、いきなり制約を書き始めていませんか？ プロジェクトを開発する場合は、まずは、日本語で仕様書を書きましょう。
何年もスケジュールナースを使って頂いているのは有難いのですが、恐らくは、月々のスタッフ要求をそのまま制約化して、スパゲッティプログラム状態になっているプロジェクトを見かけます。スタッフの力が強いのだと思いますが、学級崩壊のクラス状態です。コントールが効かない、統制のないプロジェクトは、崩壊します。
制約を書ける管理者が陥り易い現象ですが、それを防ぐには、元々の仕様書に戻ってメンテナンスしているかどうかに尽きます。元々の仕様には、平準化とか、負荷を均一にとか、そういう言葉があったはずですが、それがどこかに置き忘れて、月々の個々のスタッフ要求を満たすための制約記述に成り下がっていないでしょうか？
個々のスタッフ要求は、予定で記述されることが基本です。過渡な要求は、当然解がない事態となりえるので、ソフトレベル化し、全ての予定を満たすことはできない、というスタンスで臨みましょう。それが、上記仕様を満たし、しいては全体の幸せベクトルを最大化すると考えます。
大事な原則は、
固有スタッフ名で制約しない
です。お客さまのプロジェクトファイルを拝見していて、メンテナンス性が良くない例を下に示します。
ペア禁止制約ですが、スタッフ名で制約しています。
以上で、メンテナンス性の良い記述の完成です。
申し訳ありません。対応は行っておりません。
様式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.
考え方は、正しいです。ただし、実装が間違っていました。
以下の制約で「深」は、意図した合成集合「深夜」になっていません。
正しくは、これを用いて、次のように制約すべきです。
