Q.バグだと思いますが、宅直からの明けがある

 Ans.ご指摘通りバグです。

正しい設計

Graph縮約方法の検討 その2

 2番目の方法は、期間の中間部に途中ゲートを置く方式です。例えば、Instane15の期間は、6週間ですが、中間あたりの３週間目にゲートを置きます。

ゲートの幅（最大値ー最小値）を小さくすればするほど、グラフ容量は、小さく抑えられていることが分かります。元々が８MBでしたので、幅３６にしても半分以下とすることが出来ます。

この発想を、全週に拡大したのが下図結果になります。

全週に適用すると、狭幅化が、よりグラフ容量削減効果を生むという傾向が分かります。

下図は、制約ゲート数とグラフ容量の関係です。制約箇所が多ければ多いほど、グラフ容量を削減することが出来ます。

いわば、マラソンゲート方式です。途中関門を決められた時間内に通過する、という制約を付加すると、グラフ容量を削減できることが分かりました。（イラストはCopilotで生成）

ゲートを狭くすることは、下図で、幅方向を制限することに繋がります。

状態空間を狭めてしまうということです。幅を狭めれば、グラフ容量をそれだけ削減できることになりますが、同時に、真の最適解を見逃してしまう可能性が増えます。最適解は、見逃さずに、冗長なノードだけを消去することが必要となります。

まとめると問題は、

■最適性を担保する緒元を失わずに、縮約する理論の確立

■途中関門が多ければ多いほど、効果は増大するが、コンパイル時間が増える問題への対処

にあります。

これがこれからの研究課題となります。

Graph縮約方法の検討 その１

 １）Secondary　Cardinalsの削減

SchedulingBenchmarksの制約を見るとメインは、勤務時間制約で両方向から効いています。が、そのほかにも、特定のシフトに対する最大値パターン数制約があります。これをSecondary Cardinalsと呼ぶことにします。今、Secondary　Cardinalsを無視して最適解が求まったとします。その最適解が、（制約していなくとも）最適解を満足するならば、最初から無視しても問題なかった、と言うことが出来ます。

当然のことながら、それは、やってみないと適用できるかどうか分からないのですが、仮に適用できたとして、どれくらいの効果があるか見てみました。

    その結果が下記グラフで、E1を削除したとき8MB→6MBになっているので、2MB約25%の効果が得られます。しかし、E1/E2の両方を削除しても全く同じ結果となりました。

従い、Secondary　Constraints削除が可能ならば、それなりの効果は期待できる、ということになりますが、半分にする程の効果はなさそうだ、という結果となりました。

Instance15 の厳密解が確定

 Ryzon9700X、約一週間廻してようやく確定しました。

LB=3828

UB=3828

です。

十数年に渡り未解決だった問題の最適値が確定しました。

ルートLB=3823.64

で変わりません。

行った改善は、マルチスレッド化がメインです。その他細かい改善として、

■環境の保存で、最大10GB程度DISKを使いました

■ログもGUIの限界を超えていたのでDISKに落とすようにしました。

■その他に、CPU（キャッシュ容量32MB）の能力が大きい。

旧世代のCPUでは、全くマルチスレッド効果は期待できず、恐らく1カ月以上かかったと思います。

Updated Report for Instance15

 

Subject: Updated Report for Instance15

Dear Tim Curtois-san,
I would like to report the exact objective function value for instance15 in the scheduling benchmarks.

Lower Bound (LB): 3828
Upper Bound (UB): 3828

I have also attached an updated UB dataset that differs slightly from the version previously reported.

Thank you for your attention.
Sincerely,
Tak.Sugawara

7月１6日リリース機能その６

 ６）スタッフ毎のシフト・タスクの名前は、見ないのは変わりないのですが、エントリー数のチェックを入れました。スタッフ数と一致していないと読み込まないようにしました。

SchedulingBenchmarks instance15再挑戦

 マルチスレッド化して様子を見てみました。スレッド数は８にしました。下記は、テスト中の様子です。

約２日走らせて、LB＝３８２６．６　UB＝３８２８となっています。なので、UB＝３８２７が発見されれば、即終了です。後、僅かのように見えますが、実際には、BranchingTreeの爆発状態にあり、終了まで２週間程度かかる見込みです。（大体こういうテストをしているとWindows強制アップデートによりテスト途中終了となってしまうのが常です。）

経験的には、ここまで来て未だUB=3827を発見できないということは、その解は本当に存在しない、すなわちUB=3828こそが厳密解である可能性が非常に高い、ということです。ただし、UB=3827解が存在しないという厳密な証明のためには、LB=3827プラスアルファとなるまでBranchingTreeをスキャニングする必要がある、ということです。たとえば、LB=3827.01となれば、整数解は、3828以上ということになります。LB=3827では、未だ、整数解が3827に存在する可能性が残ります。

CPUの稼働率を見ると、

上のように、稼働率100%とはなっていません。Hyperthreadを加味して最低50%程度稼働しているべきなのがそうなっていないのは、キャッシュヒット率によるものであると推察されます。

A)この稼働率を上げることが出来れば、速度アップとなるはずです。

B）もう一つの問題として、インスタンス23以上では、128GBRAMをもってしてもグラフ規模が大きすぎてコンパイルできない、という問題があります。

A)B)の両方を一挙に完結する方法として、グラフの縮約化があります。要するにメモリのダイエットです。厳密解を得るのに必要な緒元を失うことなしに、ダイエットを行うことは、instance15を解くことは勿論ですが、instance23を解くにも必要なことです。

この方法が実用化出来れば、アルゴリズム３の使用頻度が3%から20%位に上がるかもしれません。というのは、多くの実務インスタンスにおいてもグラフコンパイル速度がネックとなっている為です。

instance15だけを見れば、cutting plane 的なアプローチの方が適しているように思えますが、グラフダイエットこそが本丸であると思います。そしてそれは、アルゴリズム３実用化のために必要でもあります。アルゴリズム３の実用化は、これまで知られていない多くの実務インスタンスの厳密解を知るのに大きく寄与するはずです。

XML converter for Scheduling Benchmarks

 未解決のスケジューリングベンチマーク問題について取り組みを始めました。

未解決なのは、

instance15

instance23

instance24

の3問です｡

検討を始めるにあたって、スケジュールナースのCSV解をAutoRosterのフォーマット（XML）に読み込ませるためのコンバータを制作しました。これまでは、IFDEFコンパイルオプションにより、AutoRosterに読み込ませる解XMLをスケジュールナース内部で生成していましたが、いちいち再コンパイルする手間をなくすのが目的です。

以下使い方です。

とりあえず、求解を中止しました。２時間程走らせてUB=3828 になっています。この値はは、菅原システムズが所持する世界記録に同じです。

解画面で、

CSVファイルで出力すると、プロジェクトファイル名＋_shift.csvで、ファイル出力されます。

次にXMLコンバータ起動、求解し、出力されたファイルを指定します。

同じフォルダに、tak_solution.xml　が出力されます。

AutoRosterを起動して、下記フォルダにtak_solution.xmlファイルを置いて読み込みます。

確かに、解は、Feasibleで、かつUB＝３８２８をAutoRosterでも確認できました。

中身は、PostPythonで書いていて、INRC2用のコンバータcsv.nurse3と同じように、単なるフォーマットコンバータです。

https://github.com/sugawara-system/Schedule_Nurse3_Gallery/tree/main/English/Benchmarks/Scheduling_Benchmarks

7月１6日リリース機能その５

５）Historyのダイエット

５年程お使い頂いたお客さまのプロジェクトファイルのサイズは、12MBになっていました。これは、予定での状態をスタッフ名：予定のmapを過去も記憶しているからです。通常、過去の予定を覚えておく必要はない、と思われるので、消去できるオプションを作成しました。

 以前のヒストリデータを消去：0だと、予定表示開始日より０日以前のデータが消去されます。設定ボタンを押して、スケジュールナースを終了すると、ダイエットが行われます。このお客様の場合、12MB→1.5MB程度とダイエット出来ました。

7月１6日リリース機能その４

 ４）ExcelファイルオープンでNGの場合、ファイルクリエートにしていましたが、既存ファイルを新規ファイルにしてしまう問題がありました。これを改善し、ファイルが存在しない場合のみ、ファイルクリエート方式に変更しました。

この変更により、例えオープン可能でも読み込み不能なシートが含まれる場合（Invalidな外部参照等が含まれる場合）には、読み込みが出来ないメッセージ(Unexpected xml tag)が出て読み込みません。新規ファイルをCreateもしません。

この場合の対処方法としては、Excelファイルに含まれるInvalidリンクを削除してください。

All optimal solutions for the 8-week INRC2

All optimal solutions for the 8-week INRC2 (Second International Nurse Scheduling Competition) have been uploaded using our newly developed solver, which is currently under active development.

These solutions have been verified using the official Validator, and the corresponding validation output is also attached.

For most instances, Schedule Nurse was able to obtain exact solutions within eight hours, although a few required nearly a full day of computation (Ryzen 9700X).

Upon completing all exact solutions for the Scheduling Benchmarks, we plan to write a research paper. Our new solver will conclusively address all instances that have remained without known optimal solutions for many years.

Schedule_Nurse3_Gallery/English/Benchmarks/INRC2/8weeks at main · sugawara-system/Schedule_Nurse3_Gallery · GitHub

7月１6日リリース機能その３

 ３）２０２６年５月２４日以上、カレンダが更新できない問題の対策

カレンダマックスを２１００年以上に更新しました。適用は、スケジュールナースPrivateとスケジュールナースサブスクリプションのみです。その他のエディションの適用は行わないのでご注意ください。

7月１6日リリース機能その２

２） スケジュールナース　のUpdate廃止

現在、３つのversionをメンテナンスしていますが、２つに集約します。

今後、スケジュールナースPrivateと、スケジュールナースサブスクリプションのみが、

今後のメンテナンス対象となります。

「スケジュールナース」は、開発に貢献した方等にも無償配布しておりましたが、スケジュールナースPrivateに移行をお願いします。該当の方は、マイクロソフトアカウントを取得の上、サポートにご連絡頂ければ、引き続き無償で使用できるようにいたします。

後述のように、スケジュールナースは、Updateしないと、２０２６年５月以降のカレンダが効きませんので、該当するバージョンをお持ちの方は、早めに切り替えをお願いいたします。

Q添付のファイルで予定入力のスタッフ4の2日に「希扱」の予定入力を入れた時のエラーの理由がどうしてもわかりません

 Ans.

拘束＊拘束制約がハード制約となっており、先月からの連続で見るとスタッフ４が1日に拘束とならざるを得ないことと矛盾するようです。

30日にスタッフ4が拘束であることは変えようがないので、拘束＊拘束制約をソフト制約化することにより解が出るようにします。

解析：

Ｐｙｔｈｏｎ制約レベル7のエラーが出ています。とりあえず、この原因かどうかを判別したいので当該言語制約の✓を外して求解します。

依然としてハードエラーになりました。根本原因は、Pythonではありません。

スタッフ4関係であることは間違いなさそうなので、関係しそうなハード制約をソフト制約化

し求解の試行錯誤を行います。下記、スタッフ4の下記制約をソフト化するだけで、解が出ることが分かりました。

当該制約をソフト化したときの解です。拘束＊拘束パターンが出現していることが分かります。

スタッフ4の30日勤務をブランクとすれば、ハード制約のままでもOKでした。よって、この制約が原因である、と特定できました。

以上で解析終了です。

最終的な解は、PythonをEnableして以下のように得ました。

考察

解がないときの解析は、非常に面倒です。簡単には、解がないときは、予定部をソフト化して、予定が変更になった部分に着目します。

しかし、今回、原因がない原因を追究したい、とのことでしたので、上のような手順で解析しました。上のように、具体的原因の追究は手間がかかるのが普通です。特に、ハード制約が多く、解のない原因が複数の要因による場合、真の原因に辿り着くのは容易ではありません。従い、次の指針を推奨します。

基本的には、ハード制約は、必ず実現できるものであるべきです。実現出来ない可能性があるものは、原則的にソフト制約とします。

どうしてもこれだけは実現したいというアイテムは、ハード制約化してもよいですが、その数は出来るだけ抑えるようにするようにした方がよいでしょう。

7月１6日リリース機能その1

 １）スタッフプロパティシートの書き込みは、グループ定義とグループ集合を除く仕様に変更

従い、以下の３つのシートのみになります。通常は、グループ定義とグループ集合は、スケジュールナース上で操作することになると思いますので、その方が汎用性が高いと判断しました。

7月１０日リリース機能その６

 ６）解ラインコピー　動作するようになりました。

7月１０日リリース機能その５

 ５）ユーザの予定原案の赤をロックとして読み込めない問題の対策

下記で、ユーザの予定は、赤フォントで記述されている部分があります。

これをスケジュールナースの予定Excelシートにコピペしました。スケジュールナースの元々のデータ（先月部）は、ロックが掛かっているので赤フォントです。一方ユーザのフォントも赤です。しかし、ARGBで見ると違いがあり、ユーザフォント赤はロックが掛かりませんでした。

ARGBではなく、RGB(255,0,0)をロックと解釈するように変更しました。これにより、赤部は、ロックが掛かります。

7月１０日リリース機能その４

 ４）Ｅｘｃｅｌ取り込み出力設定の列数１０Ｍａｘ→無制限に

多数の列があった場合、描画の段階で１０に制限しておりましたが、この制限を撤廃しました。

これにより、多数のブランク設定があったとしても、問題なく動作するようになりました。

7月１０日リリース機能その3

 3)Excel　ExportファイルオープンモードをCreateからOpenに変更しました。

今まで、常に新しいファイルとして処理していたので、既存の別なシートが失われていましたが、DefaultをOpenに変更したので、別なシートが存在する場合には、消すことなく追加となります。

上は、ユーザフォーマット解の書き込みを行ったファイルに、

■スタッフプロパティの書き出しと、

■予定の書き出しを行ったシート群になります。

Q.男性３人、女性３人配置したいため、列制約で制約タイプを最大―最小スタッフ数とし最大３最小３としたが４人以上配置されてしまう。

 Q.

下図のように女性が3人のところ”入り”に4人配置されてしまっているのは何故？

Ans.

プロジェクトおよび意図および現象の説明、ありがとうございます。

当該制約部分に移動します。

当該制約部分で集合をマウスホイールボタンを押して確認すると、”女性”集合にはなっておらず、別な集合名で記述されているようです。

スタッフプロパティシートを確認すると、次のようになっていました。

意図としては、女性集合で3名にしたいと思いますが、その部分集合で制約していることが分かります。

実際、解で確認すると、制約通りに動いていることが分かります。

従って、

■仕様：女性3人と

いう仕様に対して、制約は、　

■制約：生活介護　休日可女性　3人

になっています。他に”女性”で制約している記述が見当たりません。これが原因と思われます。

Note:

部分集合に対して制約して、全体集合で制約していないことによる問題は、よく遭遇します。（私もよくやらかしてしまいます。）

対策としては、

■スケジュールナースは制約通りに動く

■制約していないところはフリー（何が割り当てられるかは誰も分からない）

ということを常に頭に置くこと。

■制約をしている箇所で、マウスホイールボタンにより、集合（Day集合、グループ集合、シフト集合）をよく確認する。

ということに尽きるかと思います。