INRC2 8Weeks LB 改善構想

 改善方法を構想しました。

一つには、BranchingTreeのパラレル化です。マルチスレッドで、残っているBranchingTreeを潰していきます。ネックは、グラフを解く速度ではなくリニアソルバCLPの速度であることが分かっているので、CLPのマルチスレッド数がその上限の速度向上となります。しかしながら、この方法でも十分ではありません。

そこで、LB改善専門の専用スレッドを立ち上げます。このスレッドは、LB(Lower Bound)が求まったあとに、通常のBranching　Tree　Search（左側）とは独立、かつ並列にLBだけを改善します。

LB改善とは何か？というと、リニアソルバで求めたBranching　Tree　Rootのフラクショナルな値を整数化していくことです。それでは、Branch＆Boundと何が違うか？というと問題を分割しません。Rootのまま行います。なので、そこでフラクショナルを整数に出来たとき、何某かLB改善に寄与するはずです。その問題の目的関数値の最小公約数で決まる値以下にUB-LBギャップまで改善出来た場合、最適値証明が完了します。INRC2の場合は、最小公約数は、５です。（重みが１０，１５，２０，３０）です。必ずしも全てのFractionalを整数化する必要はありません。UB-LBギャップー５>=0となるまで改善出来れば十分です。別な言い方をするなら、全てのFractionalを整数化出来た時、UBが未知だとしてもリニアソルバの値が即最適値UBとなります。

INRC4Weeksのように通常は、左側ループのみで厳密解が求まります。しかし、長時間廻しても求まらない、若しくは求まらない可能性を考えて右側ループも最初から廻します。現在の状況からするとINRC8Weeksの場合は、1時間も廻すともうこれは尋常ではない＝BranchingTree爆発ということが分かるので、その時点で右側に全力投入したほうがよいかもしれません。

これは、INRC8WEEKSに対して8時間以内に厳密解が求めるためのアイデアであり、やむにやまれず、手段を選んでられない状況から考えました。もう意地になっているいうか、これを解くことが自分の使命のように思い込んでしまっている自分が怖いです。

ところで、整数計画創始者ゴモリーの考案した方法は、ゴモリーカットと呼ばれています。

Vol.50_10_719.pdf (orsj.org)

The history of state-of-the-art MIP solvers is fascinating. There are very few p... | Hacker News (ycombinator.com)

CPLEX→CLP/Gruribi→ZIB/Highs→COPT

という最近のCOPTの攻勢をみるにつけ、アカデミックなバックグラウンドは、全て繋がっている、のが面白い、というかそれだけ難しい分野ということが言えると思います。最先端のMIPソルバを開発できる人は、非常に限られており、会社から会社へ移動することによって成長と遂げてきたという歴史があります。COPTの中の人達も、スタンフォード出身だったのですね。

とりあえず、この方法を菅原カットと呼ぼうと思います。平面削除は、アナログをデジタル化する方法です。一方、菅原カットは、デジタルからアナログを改善する方法です。実装してみて、どんなものなのか、今後数週に渡り、実装・評価していきます。

INRC2 8WEEKS LBの改善が必要

 ２００時間廻しても解が得られないのが大半であることが分かりました。正確には、厳密解証明が出来ていません。約１０日計算機を廻しても解が得られないというのは、何か方法論からして間違っているような気がします。

どういう問題かというと、BranchingTreeの爆発という現象が生じて、調べるのが困難になるということです。Branching Treeを全て調べて、現在のUBを下回る解が存在しない、ということを言いたいのですが、調べれば調べる程、調べるべきNodeが増えてくる現象です。つまり、恐らくこの値は最適値であろうが、これより良い解が存在しない、という証明が出来ないのです。

そんなこと、どうだっていいじゃん？ほぼ最適値が分かっているんでしょ？と言われそうですが、アカデミックの世界で重要なのは、厳密解です。これが言えるかどうかで、その価値に雲泥の差が生じます。厳密解が分かれば、その後、高速なヒュリスティクスを開発することも有利になります。しかし、それが分からないと、現在の解がどれだけ最適値に近いのかが分からないということになります。量子アニーリングがどれだけ早くかつ精度よく問題を解けるのかは？最適値が分かっている最も困難な問題分野で、比較評価されるべきでしょう。そういった評価をする上においても重要です。量子アニーリング自体は、厳密解を求めるものではありません。厳密解を得るのは、依然としてクラシカルな方法によります。

NP困難な世界に挑むとは、そういうことだと思います。

この手の問題に対して一般的なMIPの対処方法は次の３つがあります。

■Strong Branch

■Reduced Cost Fixing

■Cut　Generator

です。代表的な組み合わせ最適化問題、例えば、VRP(Vehicle Routing Problem)問題では、Cut　Generatorが有効であることが報告されていますが、NSPに関しては殆どありません。

どのようにするか、するべきか考え中です。

サブスク契約

 Q.スケジュールナースシステムの利用について、サブスク契約するにあたりの、見積り

書とメンテナンスに係る経費の概算を教えてください。

Ans.

サブスクは、マイクロソフトストアによる販売です。菅原システムズは、ソフトの開発元ではありますがサブスクの販売は行っておりません。

従いまして、契約書はありません。

もしかして、勤務表作成サービスの方をご所望でしたら、以下のような内容になります。

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

お勧めしているのは、1年サポートの方です。実績的に見ますと、３カ月＋サブスク版では、ITに明るい方でないと期間的に難しいかな？という感じです。慣れの部分大半ですが、厳しい方が散見されます。

１年版でしたら、買い切りであり、この期間内に学習して頂ければあとはご自分達でメンテナンス出来るので費用負担も発生しない、という算段です。

勿論、独力で可能であれば、買い切り版のみの販売もお受けします。

以上、ご案内させていただきました。

入稿データ作成

 印刷媒体に広告を出すのは初めてなので、以下の通りご教示頂きました。

*****

ご質問いただきました入稿データの件ですが、

添付のpptの黒枠内にモノクロで作成の上、PDF保存お願いします。

その後、以下URLにてグレースケール変換※をお願いします

（※グレースケール変換しないと印刷データとしてNGのため）

https://avepdf.com/ja/convert-pdf-to-grayscale

また、特に最小フォントなどの指定はございませんが、

文字のアウトライン化をお願いします

※アウトライン化の方法は以下URL参照お願いします

https://ppdtp.com/powerpoint/font-outline/

また、貴社HPのURLが記載されておりますが

QRコードは不要でしょうか？

もしご希望でしたら、以下URLにてQRコード作成可能ですので

作成後、広告データ上に配置の上、最後グレースケール変換いただければと存じま

す。

https://barcode-place.azurewebsites.net/Barcode/qr

*****

ということで、本来なら、版下作成にイラストレーターが必要ところ、

１）所定のPPTテンプレート上で作成

２）アウトライン化

３）PDF化

４）PDFをグレースケール化

で、済みました。サポートありがとうございました。

Nursing BUSINESS１０月号に広告を掲載予定

勤務表作成の特集があるようで、その縁で広告を掲載することにしました。

現在Google広告を使用していますが、「看護師」「勤務表」「自動」での広告単価は、時に、＠３５０を超えてます。数年前に比べ、数倍～１０倍に高騰しています。一方、スケジュールナースのサブスクで手元に入ってくるのは、＠３００足らずです。(マイクロソフトは＠１５％ですが、そのほかにUSのTAXが取られます。)　いつの間にか、とんでもないことになっていました。つまり、製品の原価以上に広告費が高い、という異常な状態にあります。

それだけ価値のあるような競合製品群になっている、とも思えないのですが、民生分野からすると、医療分野は、美味しい分野なのかもしれません。そもそも、アプリの志向が違うので競合とも言えないのですが、傍から見ると同じに見えるのでしょう。

スケジュールナースは、簡単ではないしAIも使っていません。

アプリの設定を使うというよりは、アプリにプログラムする、もう少し正確な言い方をすると、制約プログラミングするためのプラットフォームです。ユーザは、アプリの下にあるのではなく、ユーザ自身が制約プログラミングするところが決定的に違います。

ただし、いわゆるプログラミングではありません。プログラムは、問題を解くやりかた、アルゴリズムに沿ってコーデイングしますが、制約プログラミングは、アルゴリズムを解くことではありません。制約プログラミングは、制約を列挙することであって、問題を解くやり方をコンピュータに指示する必要はありません。制約を列挙しさえすれば、後は、制約で決まる解空間上での最適解を求めるのはソルバの仕事です。

とりあえず、どんなものかな～位の気持ちで試してみることにしました。

HighsのHiGHS Newsletter 24.1

 ワークショップがあったようで、結構な参加者がいたようです。資金調達も上手く行っているようで、スポンサーも付いているようです。

トピックは、内点法ソルバのプロトタイプを８月末までにリリースするとのことです。また、開発の議論の場として、Discordを始めるようです。Metisによるパーティションニングを施すとのことなので、恐らくは、マルチスレッド化したものになるでしょう。

なので、それなりの性能アップが期待できます。この性能を見た後に、必要ならCOPTに切り替える作戦でもよいかな？と思いました。とりあえず、厳密解を全て明らかにするという壮大な仕事が終わってから、普及活動に戻りたいと思います。

夜勤ナースと夜勤支援二つのグループに属する夜勤者数の変更の仕方について

 次のような大変丁寧なご質問を頂きました。この質問の優れた点は、問題箇所の説明であることは、勿論ですが、、再質問の余地がなく、必要にして十分な情報が盛り込まれています。しかも、ご自分でトライして、このようにしたけれどもダメだったと、記述されていることです。

このように記述して頂くと、どこで躓いているのかが分かるので、大変ありがたいです。

「夜勤」というシフトを今まで、各Grから一人づつ、計2名確保していたけれども、新しく、どちらのGrにも属せる人が居た場合は、上のように制約したい、とのことですね。これに対する私の一次回答は次です。

夜勤というシフトを二つに分けるのよいかと思います。

夜勤＝夜勤ナース業務　または　夜勤支援業務

とします。

次の3つの制約で、所望の動きになると思います。

１）1<=夜勤ナース業務<=2

２）夜勤支援業務<=1

３）2<=夜勤<=2

３）番目の制約は、夜勤する人は、変わらず2人、という制約です。これは異論ないと思います。１）番目の制約は、ナース夜勤でみると、上の二つのケースでみて、2人のナースの方が夜勤する場合と、1人のナースと1人の支援業務の方の場合があります。どちらのケースでも、最低ナースは一人確保されている必要があります。最大で2名は異論ないと思います。２）番目の制約は、二つのケースで見ると、0名もしくは１名となります。

一つのシフトは、同じ人には二つ割り当てられることはなく、常に一つという性質を利用して制約します。スタッフプロパティ上の集合は、どちらの集合にも属する場合が出てくるので、仕事を分けるには、シフトを分けることが必須になります。（今後、さらに夜勤の種類が増える場合には、タスクを使うことで、シフトとタスクの分離が出来、メンテナンス性がよいものとなりますが、今回の場合は、シフト分割でよいでしょう。）

分かりづらければ、現在のプロジェクトファイルを送って頂ければ、それに上記を追加変更いたします。

ということで、具体的にプロジェクトを変更していきます。

夜勤シフトのチェックを外します。

すると、次のようになります。

勤務者数で参照されているので、勤務者数のチェックを外します。

多くの箇所で参照されているので、グループ毎の設定をオフにします。

行制約も同様です。

削除した「夜勤」を二つにシフトにします。夜勤ナースと、夜勤支援という二つのシフトを追加しました。

シフト集合を追加しました。このとき、「夜勤」は、元の「夜勤」と同じ名前にしておくのがポイントです。

行制約で前の夜勤ラベルは、トでした。元のシフト「夜勤」は無くなりましたが、新しくシフト集合の「夜勤」は、存在しています。ソフトが参照しているのは、ラベルではなく、名前の方です。名前「夜勤」は、変わっていないので、パターンを弄る必要はなく、グループの適用をオンにしていけばよいだけで済みます。

殆ど全てのグループの適用をオフにし、その後オンにしました。中身を弄るのは、唯一列制約部分になります。

グループ集合は新たに次を作成しました。

スタッフプロパティで夜勤支援を追加し、動作を確認します。

何故かナース2人を許容しているのですが、そのケースはありませんでした。試しにナース二人を予定で勤務させましたが、その場合は確かにその通りになりました。原因はよくわかりませんが、ナース勤務が多忙であるとすれば、説明が着くかもしれません。

以上で、実装終了です。基幹となるシフトを変更すると、多数の箇所に影響を及ぼすのは、必然です。多くの制約でそのシフトを参照しているので、制約毎にオフしていくと何がなんだか分からなくなってしまいますが、グループのオフであれば、何とか記憶の範疇ではないでしょうか？　

しかし、上のようにすれば、それほど手間ではありません。

その他にもタスクを用いる方法、Pythonを用いる方法等を思いつきますが、多分、今回の方法が一番分かりやすいと思います。

＝>早速、見て頂き、返信を頂きました。

ブログを拝見させていただき、修正版も確認しました。

こちらの希望通りの仕様となっており感動いたしました。

精読しましたところ私が混乱していたところが理解でき、また新たに勉強になった部

分もあり大変助かりました。

とのことで、安堵しました。これも、また嬉しいのは、どうだったかが記載されていることです。納得行く答えに辿りつくことが出来たかは、こちらも気になっているものです。

このようなお返事を頂くと大変ありがたいです。

してみると、最初の質問の仕方から、Closeに至るまで首尾一貫しているのは、相手に対する気遣いではないか？と思います。他人であり、普段の状況が分からない私に対して、分かりやすいようにご自分の問題を図示を駆使した説明することは、簡単なようで実は、難しいことです。

こうした、日本語能力の高さと言いますか、広く言えばコミュニケーション能力は、「制約を弄る」ということにおいて、重要な能力の指標だとも思います。「制約をする」とは、日本語で５W１Hを規定することに他なりませんから。

図示をするのは、面倒なことです。でもその作業をすることにより自分の考えをまとめることに繋がり、なおかつ、相手にも分かり易い説明になる、結局、一番早い問題FIX方法ではないでしょうか？　と思った次第です。

対照的な例は、

https://schedule-nurse.blogspot.com/2024/06/blog-post_19.html

で述べました。

私は、一次回答をするのに5分もかかっていません。問題を直ぐに理解できたからです。

鋭い方は、一次回答は、図示を言葉にしただけであることに気づくかもしれません。実際、図を見ながら、回答しました。言い換えると、ここまで記述できるなら、制約化できるまであと一歩のところだった、ということが言えます。

プロジェクトを修正するのに30分位、スクショを取りながらブログ文章を書くのに3時間位かかっています。他人に説明するということは、それだけ手間がかかるということです。しかし、その結果として、以降、今回の学習により同様の問題は独力でFIXできるようになる、という成果が得られます。

今回の問題は、比較的高度な、それでいてありそうな問題です。独力でこのレベルを操れるようになったならば、開発者として望外の喜びです。そして、こんなときは、こういう風にすればいいんだ、ということを皆さまには、頭の隅に入れてもらって何かの折に参考にして頂けたら、幸いです。

次のソフト制約で、許容範囲を超えています

 ソフト制約でのハードエラーの解析です。

この場合のソフト制約というのは、数を数える制約、不等式制約または、基数制約と呼んでいる類の制約です。ソフト制約なのにハードエラーとは、何事か？　と思われるかもしれませんが、数を数える制約には、必ずその限界が暗黙のうちに設定されています。その値が、エラー許容量です。この範囲を超えたらハードエラー、解がない状態になります。

いつものように、当該箇所に飛びます。

ちょっと待ってください。エラー箇所は、行制約グループ２と言っているにも関わらず、行制約グループ１が表示されています。これは、同じ名前があるときの問題です。正しくは、次の箇所です。

レベル７に設定されていますから、この範囲が逸脱していたということです。下限が4に設定されていますから、０の人が居ることを想定すると、エラー許容量を４にする必要があるということです。

試しにエラー許容量を３→4にしてみると、解はありました。つまり、0回しかやらない人が必ず存在する、ということを意味しています。

大量のエラーが発生し、時間もかかっています。恐らく何か記述ミスがあるのでしょうが、ここまでくれば、何が起きているは、解を見れば分かると思います。

特休エラーで解がない

 こんな風に出た場合は、解がない状態です。

求解ページには、赤でエラー箇所が表示されています。赤丸部分をダブルクリックして当該箇所に飛びます。

一つは、6連休勤務禁止制約です。

シフト予定で、特が並んでいます。恐らくこれが原因でしょう。

「特」は、何かを見ます。特休のようです。

有公休ラベルで、特休が漏れているようですので、特休を追加しました。

これで、ハードエラーを解消することが出来ました。

解がない場合は、原因箇所に飛び、何が起きているか？　何と何が矛盾しているか？を観察しましょう。

INRC2 8WEEKS 全く歯が立たない

 全く歯が立ちません。一筋縄ではいかないことが判明しました。何か、イノベーションがないと厳密解を得るのは、とても難しいです。3日間廻しても厳密解である証明は、一つも得られませんでした。

気を取り直して、新しい手法を投入して解くことを考えます。そのための第一歩は、サブプロブレンに分割することです。

次のTraineeは、TR集合の人だけが、そのタスクを実行でき、その他のスタッフは出来ないことが分かります。

制約があるのは、Traineeに関して制約があるのは、次の列制約だけです。

言語制約では、そのスタッフのみで閉じており、TR集合以外との演算がありません。

なので、問題をTR集合とそれ以外で分割できます。分割した問題内の最適値が全体集合での最適値になります。このためには、TR集合内だけの演算で閉じていることが要件です。全ての演算をチェックして、このチェックがOKになったときだけ問題を分割できます。

問題を分割したとき、解きやすいのは、小さい方です。6人しかいなければ、例えばMIPソルバでも解ける規模です。なので、大きい方の問題に注力して解けばよい、ということになります。

言葉で仕様は言えないけれども、良くない解であるのは言える

 ヘルスORでの池上先生の話で、「何度も師長に解を見せに行っては其のたびに指摘され、何度も、何度も、何度もそれを繰り返した」　というお話がありました。

通常の勤務表作成においても、全く同様のプロセスを辿り、その通りだと思います。

A) ■頂いた仕様以外に仕様がある

ということです。言葉では言えないけれども、良くない解であることは分かる訳です。私は、これを脳内仕様と称しています。

対策は、簡単で、納得いくまで、良くない解の特殊例を一般化して、それを仕様として追加して行けばよいのです。脳内仕様は、普段隠れています。しかし、解という特殊例を見ると、途端に脳内から外界に向けて「こうではない」と言えるのです。問題はその先で、その特殊例を、言葉としてまとめられるか？にあります。これを言える人とそうでない人の両方が存在することは確かで、ここに能力差、スキル差が存在すると思います。自動勤務表作成において最も大事なスキルは、プログラミングスキルでもIT能力でも集合の理解でもなく、この部分にある、と思っています。言葉として提示頂けなければ、制約として落とし込むことは決して出来ません。

B）■頂いた仕様と実績とがかけ離れている

もう一つ、人間の特性として特筆すべきことは、脳内仕様と、実績とはかけ離れている、ということです。上のプロセスで全てを仕様化しそれをハード制約とすると、絶対と言って良いくらい解がありません。人間が普段思っていることは、完璧に出来ている筈という思い混みがあるようです。が、実は、完璧というのは、殆どなくて実態は穴がある、否、むしろ穴だらけが普通、ということです。脳内で思っているだけで、きちんと計測管理されたものではないためです。これまで色々な実績勤務表を見ていますが、殆どの仕様をソフト制約にしておかないと、人力解勤務表では解がないのが普通です。自動勤務表では、ここに第一のバリアが存在します。

これを認めて前に進める人と、どうしても納得できない人がいます。別に師長を責めているのではなく、単にデータがそうなっているという客観的事実だけなのですが、自己防衛に終始して前に進めない方がいます。こちらが求めているのは、A)スキルで、「それを言葉としてどのように表現できますか？」ということです。欲しいいのは、仕様とその実現優先度だけなのです。どれを取りどれを捨てるべきかは、管理者にしか分かりません。特にここは絶対に外せないというところは、ハード制約化しますので、ご指示頂きたいのです。でも、ハード制約指示であっても実態勤務表は出来ていない、というのはよくあります。

C)　■解について納得できない方がいる

トレードオフについて、ご納得いただけない方がいらっしゃいます。特に自分で勤務表を作った経験がない、または少ないとトレードオフについて理解が難しいかもしれません。この意味で、これよりも良い解はない、ということを常に示せるのが理想である、ということは変わりがありません。ソルバの仕事であり、開発者としての責務だと思っています。

D）■リニアモデルの最適解が自分の最適解ではない

池上先生のおっしゃっていた通りです。この対策として、スケジュールナースでは、非線形のエラー許容量という概念で、非線形のハード制約を持っています。これ以外にもあるかもしれません。が、それは予定として埋めてしまえばよいし、必要ならそれをソフト制約化すればよいのです。部分解を予定としてコピペすることも出来ます。そうしたことは、単純にソフトの技や、慣れ、使い方の類だと思います。

脳内仕様を変換し終えた自動勤務表においては、、職場の数だけモデルが必要です。そしてそのQOLは、もはや人間では到底なしえない高みに達しています。議論は、その高いレベルでの議論になっていることに注意してください。穴だらけの勤務表とトレードオフについての議論をしている勤務表とでは、次元がそもそも異なるのです。

細かすぎる細部を気にされている方も、どうかと思います。元は穴だらけのQOLだったのです。それに気づかなかっただけですが、それは無視しておいて、非常に細部のところを気にされるのもどうか？という気がします。少なくとも人力解よりは遥かに良くなったのですから、適当なところで打ち切る度量がマネージャとして必要ではないか？とも思います。全部を満足する解はないことは、証明出来ているのですから、後は、どれを選ぶかだけです。

ヘルスケアOR 拝聴しました

ZOOMで拝聴しました。

ゲノム解析のお話は、面白かったです。伊藤真理先生を拝見できなかったのは残念でした。

ここでも、クラウドサーバ力が、医療サービスひいては国力に比例するような感じを持ちました。(国内でもAWSやAuzureに匹敵するクラウドサーバがあれば、少しでもデジタル赤字を減らせると思うのですが。)

本題のNSPですが、同業者の方が少なくとも二人いらっしゃいました。また、スケジュールナースユーザの方もお見受けしました。視聴者の方の数も3講演で一番多く質問も多彩で関心の高さが伺えました。

で、私が考えるNSPの現在の問題は、以下の２点です。

A）■職場の数だけモデルがあり、モデル化をどのように構築しメンテしていくか？です。EUのように専門のコーディネータが居ればよいのですが、日本の現状では、看護・介護師長や、上に立つ医師がそれをやるしかなく非常にハードルが高いです。

B）■アカデミックの興味は、未解決のナーススケジューリングの厳密解がどこにあるか？ということです。NP困難な問題領域ではありますが、組み合わせ最適化問題としてどこまで解けるものなのか？その限界は、今、一体どこにあるか？を明らかにすることです。

＜職場の数だけモデルがある＞

Aについては、スケジュールナース勤務表作成サービスがあります。看護師・介護士・医師当直表、その他あらゆる業種のフルカスタム制約での勤務表が出来ます。月々の勤務表は、変化していきます。メンテナンスのない勤務表は存在しません。大事なことは、自分達でメンテナンス出来るようにすることです。それには、職場のルールに沿ったプロジェクトファイルがあったとして、それを改変・変更できるようにならなければいけません。単に勤務表を作れればよい、というのは誤った見方です。自分達でメンテナンス出来て初めて、使える勤務表になります。そのために必要なのは、まず職場のルールに合った制約ファイルとその変更の仕方を学習することです。

ご利用ください。ZOOMによるレクチャ・勘所の解説付きです。今まで、こちらから実装不可能という理由で依頼をお断りしたことは一度もありません。（無料で開始できるので、気やすく取り掛かれるためか途中で音信普通になる不埒な方が、たまにいらっしゃいます。それを除けば実装成功率１００％です。）

変わったところでは、県立図書館のカウンタ業務にも使われているそうです。また、施設での厨房業務の割り当てでも使われているそうです。私もプロジェクトファイルを見たことがないので、どのような形態かは分かりません。また、古くは、東京Key放送局ののシフト勤務でも使われています。現在は分かりませんが、マニュアルもあまり整備されていない時代によく独力で作れたなあと感心します。

このように力さえあれば、独力で設計記述でき、独力でモデル化できる世界で唯一かつ世界最高性能のプラットフォームです。殆どの場合、プログラミング言語Pythonを使わずに制約化可能です。

今までで、一番難しかったのは、地方都市公立病院の医師当直表があります。こちらは稼働を始めました。「公開してよい」との許可は既に頂いていますので、安定したら公開します。このプロジェクトでは、私でも数日間、どのように実装すべきか悩みました。このように、モデル化の難易度は、その職場依存です。一概にどんな職場でも独力で出来るとは言えません。そんな時でも、この勤務表作成サービスというSafetyネットがあるのは心強いと思います。

＜ナーススケジューリング問題のNP困難限界はどこにあるか？＞

Bについては、今年中に、古今東西、提出された全てベンチマーク問題について厳密解を与えることを計画中です。具体的には、INRC2　8Weeksで11問、SchedulingBenchmarksで2問です。これらが未解決の問題群です。ご期待ください。ヘルスケアORでも科学立国としての国力低下の指摘されていますが、ことナーススケジューリング問題の研究については、世界をリードしているという自負があります。

先月の予定入力 タスク予定も変更が必要

 先月の勤務表が、スケジュールナースでの解ではない場合、あるいは、実態が異なる場合は、先月部の予定を実態に合わせ修正する必要があります。その際、シフト予定を修正した場合は、それに伴うタスク予定も修正する必要があります。

次のようにエラーが出で解がない場合を考えます。

赤丸をダブルクリックして当該制約部に飛びます。

タスク予定では、28日は、整形診療業務になっています。しかしシフト予定では、灰色ラベル（当直勤務なし）になっています。つまりシフト予定とタスク予定が矛盾しています。

この原因は、

シフト予定を実態に合わせ変更したものの、タスク予定は、スケジュールナース解のままになっていた

と思われます。

解がない場合の処方は、「矛盾を解消する」以外ありません。

基本的には、タスク予定も実態に合わせ変更する必要があります。

しかしながら、矛盾を解消することが目的ならば、タスク予定を入力する必要はありません。今回は、タスク予定を全てクリアすることで、余計な手間をかけないことにします。

クリアしました。

これで解がないエラーが解消されました。

ヘルスケアOR ZOOMのURLが届く

 幹事は、神戸大学の伊藤真理先生だったのですね。

是非とも最初から聴講しないと。

SIMD化の結果

 結論から言うと殆ど変わりませんでした。

下が実行中の様子です。Solver2がSIMD化していないアンローリングコード、Solver3がSIMD化しているコードです。8weeksのインスタンスで50万ノード程度の規模になります。どちらも1ms程度で増減していますが、ほぼ同じ結果となりました。

恐らくは、データが不揃いであり、データフェッチの部分で律速しているのだと思います。

AVX2という最近のPCでは、ごく当たり前の機能ですが、それでもSIMD化は、CPUを選ぶので同じ程度であれば、SIMDなしとした方が汎用性のある設計となります。

SIMDの検討

 マニュアルでアンローリングしたコードを逆アセンブルしてみると、SIMD化していないことに気づきました。

モダンなC++では、下記のような書き方が出来るようですが、私のコードはそこまで洗練されていません。

https://proc-cpuinfo.fixstars.com/2022/12/loop-unroll-in-modern-cpp/

AVX2だと、単精度で8演算が同時に可能なので、８WEEKSに取り掛かる前にさらにSIMDによる高速化を検討します。具体的には、以下のような処理をします。

SIMD 演算で if 文の並列化 - その1 - - kawa0810 のブログ (hateblo.jp)

データフェッチが不揃いなので、ネックは、データフェッチ自体にあります。なので、どれだけ効果があるのかは、現時点では不明です。

また、４Weeksに関しては、現時点でも0.3ms位なので、これ以上何かしても、全く寄与しないことは明らかです。が、これから8weeks、さらに巨大なインスタンスに立ち向かうときは、この計算がネックなので、出来る限りのことをやっておいても無駄にはなりません。

INRC2 4Weeksの最適値が全て求まる

開発中のソルバで、INRC2　4weeksの最適値が全て求まりました。以下の通りとなりました。

n030w416-2-9-1  1670

n030w416-7-5-3  1815

n035w401-7-1-8  1360

n035w428-8-7-5  1080

n040w402-0-6-1  1565

n040w426-1-0-6  1750

n050w400-4-8-7  1315

n050w407-2-7-2  1315

n060w416-1-1-5  2450

n060w419-6-3-8  2675

n070w403-6-5-1  2380

n070w404-9-6-7  2115

n080w424-3-3-3  3300

n080w426-0-4-8  3185

n100w401-1-0-8  1170

n100w420-6-4-6  1780

n110w401-4-2-8  2330

n110w401-9-3-5  2455

n120w414-6-2-6  2020

n120w415-6-9-8  2050

未だデバッグモードで検証しながらの段階で、整数化については、なんら考慮していません。これから、本題の８Weeksについてトライ・しながら、整数化について考えていきます。

INTC2 Shift type successions

 H3. Shift type successions: The shift type assignments of one nurse in two consecutive days must belong to the legal successions provided in the scenario

シフトに関するハード制約になります。

基本的には、逆循環を全て禁止にしています。日勤（D）の後に早番（E）は、NG.

遅番の後は、早番・日勤がNG.　夜勤の後は、早番・日勤・遅番がNGです。

これは、ハード制約です。このハード制約の有無でのグラフが次です。

上がハード制約なしで、4842ノード、下がハード制約ありで、2784ノードです。

グラフが大きく変化していることが分かります。ハード制約があると、解空間・探索空間共に減少します。ソルバにとっての負荷は、ノード数に比例しますから、ハード制約があった方がソルバにとっては嬉しい訳です。

実は、上のグラフは、基数制約は入っていません。グラフが大きすぎてGraphvizが描画することが出来ません。基数制約のみならば、可能ですが、全ての組み合わせを合成したグラフでは、巨大すぎて描画できません。ノード数で言うと通常のインスタンスで数万ノード、大きいと数十万になります。再挑戦を予定しているScheduling Benchmarksの未解決問題では、100万ノードを超える規模となります。

INRC2の8Weeksの規模は、数十万ノードになりますが、十分に高速な演算速度(2ms以下)で計算できるようになりました。勿論、世界最速で、現行スケジュールナースも含めて既存のものに対して30－50倍速になると思れます。これを用いて、しばらくは、INRC2に特化した評価と実装改善により全ての厳密解を提示する予定です。これだけ高速だと特別な事をしなくとも普通にBranch＆Boundして厳密解が見つかる可能性は高いと思います。

実装展開は9月以降を予定しています。

一方、Scheduling Benchmarksのネックはそこではなく、バリアソルバです。これについては、HIGHSのGPU版は精度的に期待できないので、COPTのライセンスを得て再挑戦ということになると思います。全ての未解決NSPを解決したのちに、論文化する予定です。提出された全てのベンチマークテストにおいて、厳密解を単一のソルバで実現することが積年の夢でした。どうなるかは、未だ分かりませんが。

INRC2 Minimum Consecutive Assignments

 

連続勤務日数、連続休み数、連続シフト数に関する最小制約になります。どれも同じパターンで記述出来ます。

ＩＮＲＣ２ Maximum consecutive assignments 各シフト

 勤務連続ではなく、シフト連続になります。EはEarlyで早番、Lは、Lateで遅番、Nは、Nightで夜勤です。驚くべきは、EUでは、夜勤の連続５回というのもありえるということで、これが日本との主要な差になります。

最大パターン長６が３個もあるので、グラフは、より大きくなります。

INRC2 Maximum Consecutive Assignments

 S2. Consecutive assignments (15/30): Minimum and maximum number of consecutive assignments, per shift or global, should be respected. Their evaluation involves also the border data. Each extra or missing day is multiplied by the corresponding weight. The weights for consecutive shift constraint and for consecutive working days are respectively 15 and 30

Consecutive　Assignmentsとは、連続勤務日数です。勤務＝休みの否定　なので、休みラベルOを否定（✅）して最大勤務日数＋１のパターンを作ってそれを禁止にします。

これをグラフ化すると

となります。一般にパターン長が長いほど、横に伸びて（太くなる）Node数が増えます。というのは、例えば、６連続パターンを検出するためには、６状態を保持していないと検出できないからです。

短いパターンならばそれほど影響はありませんが、長いパターン（一週間以上）は可能な限り避けるようにしてください。

なお、INRC2は、EUの勤務形態をモデル化していますが、この制約については、日本と同じような感じですね。