BCV-4.13.1による各社比較

 

各社とも厳密解に到達しています。MIPソルバは、ほぼ瞬時に最適解証明が終わりますが、RosteringSolverの方(SchedulueNurse3/AutoRoster)の方が時間がかかっています。

ikegami-2Shift-DATA社比較

 各社共問題ありません。

GPOST-Bによる各社比較

 

これも、全社共、厳密解が求まっています。ScheduleNurse３は、厳密解に到達するのは、2.5秒しかかかっていませんが、その後証明するのに30秒を要しています。求解パラメータを調整すれば数秒以下にすることは可能ですが、あくまでdefault parameterでの値を載せています。

GPOSTによる各社比較

 

GPOSTは、各社とも厳密解5が求まっています。ScheduleNurse3は、ほぼ瞬時に求まって終了となりました。

Valouxis-1による各社比較

 

各社共、全て厳密解には到達しています。しかしながらScheduleNurseⅢ3以外は、1万sec行っても求解を止めません。LB==UBとなっていないためです。ScheduleNurseⅢは、4秒でBestKnownに到達したあと、40秒程度で厳密解であることを認識し、探索終了となりました。

BCDT-Sepによる各社比較

これも二桁のオーダの速度の違いが観測されています。厳密解100に到達したのは、ScheduleNurseⅢのみです。Reasonableな時間内に到達しています。Optimum(黒線)を検出した後140secで終了となります。

 

WHPPでの各社比較

Gurobi Optimizer version 9.5.0 build v9.5.0rc5

RosterViewerDemo4.3.5

IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 20.1.0.0

ScheduleNurse3　(Algorithm3　Feb.2022　to be released.)

でマシンは、Gurobi/CplexがNEOSサーバ。AutoRosterとScheduleNurse3がRythen5800X　64GB 8cores 16threads です。オレンジ色がついているのは、厳密解に到達しなおかつ厳密解証明が完了したことを示しています。

スケジュールナースⅢは、4秒で厳密解証明まで完了、AutoRosterは17秒、Gurobiは、4800秒でようやく厳密解に到達したことを示しています。Cplexは、厳密解に到達することなくタイムアウト(約8時間)でした。

このWHPPは、２Weeks　30Staffsで規模的には、小規模の部類に入ると思いますが、MIPソルバが苦戦していることが分かると思います。(マシンの違いはありますが、3桁求解速度が違います。) このインスタンスは、数理的な精度の問題を内在していて、解くのは難しいと思います。（実際、NearOptimalなソルバでやってみると、厳密解に到達出来ず、厳密解ソルバに設計変更を余儀なくされました。）

後でまとめますが、このようにMIPソルバが苦戦する例は、意外に沢山見つかります。ナーススケジューリング一つとっても一つのアルゴリズムだけで解くのは難しい、ということではないかと思います。

これらのベンチマークは、ノッティンガム大学のスピンアウトカンパニーが昔から提供しているもので、NSPにおける古典的ベンチマークと言ってよいでしょう。歴史のあるベンチマーク郡で、それぞれアカデミックなPaperがあります。現在のMIPソルバではかなりの部分を解けますが、当時は問題を一つ解くとPaperが一つ書ける位だったのです。（逆に言うと昨今のMIPソルバの進歩が著しい。）当時はメタヒューリスティクスが主流でした。

現在地は、小さいインスタンスではMIPソルバ、中規模でSAT系、大規模で再び数理的ソルバ、超大規模でメタヒューリスティクスといった風に、大まかにその得意領域を捉えることが出来ますが、上述のようにその範疇に必ずしもあてはまらないものあることが難しいところです。（結局何を選べばよいかユーザからすると良く分からない）こういった事情を背景として、NSPに限っての話ですがワンストップのソルバを目指してきました。それがスケジュールナースⅢアルゴリズム３になります。

厳密解は全てKnownですが、古典的リニア重みベンチマーク郡について、全ての厳密解を求められる世界初唯一無二のソルバ、それがスケジュールナースⅢです。

AppInstallerやはり廃止になっていた

 https://docs.microsoft.com/en-us/windows/msix/app-installer/installing-windows10-apps-web

によれば、廃止になっていました。それにしても「こう書いておけ！」と書いておいてその通りにしていたらいつの間にか廃止して、一旦ダウンロードしないとインストールできない仕様に勝手に変更する..怒りがこみあげてくるのをじっと我慢するしかありません。

インストールできないというご指摘は、複数の方から頂きました。その節はご指摘ありがとうございました。

リンク先は、前のブログ記事でのリンクで参照したページでして、履歴管理として機能していることを実感しました。日々の変更は書き留めておこうと思います。

MIPソルバで解ける規模

 任意の規模が解けるという意味では、スパコンでもバイナリ70変数程度と言われています。これは、１e21程度の探索空間です。（スパコンは、一秒間に一京、1e16程度のオーダで浮動小数演算を行えます）

普通のナーススケジューリングでも、(7shifts+1offstate)**(25staffs*31days)で、

(7+1)**(25*31)=7.8e699 

ですから、スパコンを持ってきても、解けなくて普通のような気がしてきます。それでも、1e15000オーダのナーススケジューリング問題が解ける例が出て来るのは、一体どうしてかというと、「そこに制約があるから」ではないでしょうか？　

任意のというのは、ランダムと言い換えても良いでしょう。私に言わせれば、ランダムの反対語は、偏り、数式、制約だと思います。普通に考えると、制約があると自由を奪われるので、不利なような気がしますが、実際は、そこに制約があると、解けない規模でもなぜか解けるようになるのです。

ΣAi<=RHS[Lower:Upper];

制約は、解空間を減少させます。同時に探索空間も減少させます。

ここでいう制約は、ハード制約の意味です。ソフト制約は、なんら探索空間を減少させないので、嬉しくはないです。

しかし、ハード制約のみだと、しばしば解がない状態を経験します。ですので、度々力説している通り、ハードとソフトを適切に織り交ぜることが良い制約の仕方となります。

この為には、そのインスタンスについての深い理解が必要となります。同じような制約でも、ある職場では、常識的にもハード制約であるのが、別の職場では、ソフト制約的な扱いになることは、よく経験します。そのインスタンス毎にフルカスタマイズ出来ることが理想的です。

ソルバのプロセス解説

エンジンは、下記3つのプロセスから成り立ちます。

■コンパイル　

■求解　

■エラー解析

です。

コンパイルは、求解コードを構築するため処理です。problem.jsonを読み込み、構文解析後に、簡易・自明なエラーは、求解に行くまえに報告・終了となります。自明なエラーとは、例えば、日勤者が3人以下という制約があって、予定入力で4人以上既に割り当てられている場合です。この場合、ソルバに入力しても解がないことは明らかですので、この段階でエラーを報告し終了となります。ただし、予定入力がソフト制約の場合は、この限りではありません。あくまでハード予定入力がされている場合のみエラー報告終了となります。

（現在、この部分の報告は一部英語となっていたので、日本語に書き換えています。）

また、Algorithmによっても、コンパイルコードは、変わるので、前段は、Algorithmに依存しない処理、後段は、Algorithmに依存する処理となり、コンパイル内でも前段・後段があります。

求解は、Algorithmに従って答えを探す処理です。

求解で、答えがタイムアウト等で求められない場合、あるいは、明確に解が存在しないと分かった場合は、エラー解析に行きます。ただし、これは、エラー解析指定がなされた場合のみです。

エラー解析でのアルゴリズムは、私の特許に基づいています。ただし、エラー要因は実は無数にあり、そのこと自体、求解プロセスと同様のNP困難なとても難しい問題です。さらに難しくしているのは、どれが人間にとってのエラー主因か、人間の主観による部分があります。必ずどんぴしゃなエラー主因を導きだせるものではありません。ただし、これなしにはそもそも何の制約が満足していないのかが不明です。制約設計時、これが為にネックになることがあります。制約設計段階での設計支援ツールというのがその主旨であり位置づけになります。

ハードエラー解析は、厄介ですので、月々の制約では、適切にソフト制約を織り交ぜ予定なしでは、生じないようにします。こうしておけば、後は予定入力追加によるエラーしかありえないので問題を予定に特化・限定させることが出来ます。エラーがあったとき、予定を全てソフト化して、解を求め(予定なしでは解があることが保証されるので解はあります）、予定が移動された場合のところが怪しいということになります。(予定が移動された部分は赤枠で表示出来ます。)

 

シフト勤務のブラック度

色々な勤務表を見てきた私が感じている体感的ブラック度は、

介護業界＞看護業界

です。その定義は、長時間勤務を要求・実施されている度合いです。

例えば、介護業界では、16時間勤務は、普通にあります。私の長女も介護業界で働いていますが、PM3時に出て行って、帰ってくるのが、翌日AM11時を過ぎる、ということはよくあります。看護では、必ずしもそうではありません。国公立病院では、3交代(8時間勤務）のところも未だに多くあります。

が、どうも、勤務医はそれを上回るらしいことが、妻に聞いて分かりました。つまり、

勤務医　＞介護　＞看護

詳しくは、医師の交代勤務で書きたいと思います。

インストーラの問題

インストーラのリンク先が認識されなくなってしまいました。（昨年より何も変更していませんので、原因はOSの更新に伴うと考えております。）

先ほど、リンク先を修正しました。

ダイレクトリンクは以下で、ファイルを開くでインストールすることが出来ます。

https://www.nurse-scheduling-software.com/release/schedule_nurse_137A.appinstaller

ご迷惑をおかけし申しわけございません。

古典アプローチで出来ることは未だある

良質な記事だと思います。 

進化する最適化技術 VOL.2～最適化問題を解決に導くNSSOLの技術と実績 －量子アニーリングは万能ではない－～｜TO THE FUTURE｜日鉄ソリューションズ (nipponsteel.com)

記事から抜粋します。

****

先ほどの巡回セールスマン問題の応用例に「配車計画」というのがあります。配達とか集配とかのスケジュールです。たとえば我々が最初に提示した答えを見ていただいたときに、「このお客さんは午前中に行かなければならない」とか「Aのお客さんのあとにすぐにBのお客さんにいかなければならない」などのより具体的な条件がポロポロと出てきます。

――なるほど。最適化問題は一つひとつ異なるというのはそういうことですね。

山本：そうです。お客様の固有の条件を考慮しないと使えるシステムにならないのですが、最初のヒアリングですぐに出てくるわけではないんですよ。

塩見：最初に大まかな業務の条件をうかがって、その条件で出した答えを見てもらうと当然ダメ出しされます。そこで再度ヒアリングして出た答えを見てもらう、ということを何回も繰り返すんですね。そうするとだんだん使える答えになってきます。

***

これは、お客さまのプロジェクトを私が記述する場合によく似ています。新規のプロジェクトの場合、稼動まで3ヶ月程度は見てください、というのは、こういう背景があります。生産計画みたいなプロジェクトでも同じなんですね。ただし、NSPの難しさは、コストをかけてSEを投入すればよいということではなく、月々の勤務でも制約が刻々と変化するという、コストがらみの独特の問題があります。NSPは、アプリのユーザインタフェースところが大かとは思いますが、最終的にはユーザ自身の教育に行き着くというのが持論です。

また、抜粋です。

***

そうです。ただ、単にアルゴリズムを用いれば解が出るというものではありません。まず、それぞれの最適化問題に向いているアルゴリズムを選定する、その見極めが難しいのです。言い方を変えると、適さないアルゴリズムを使うと、最適な解は出ません。

樋川：私たちの強みのひとつでもあるのですが、どういう問題にどういうアルゴリズムが合うかを知っていることがとても重要です。

――確かに専門家じゃないと選定は難しそうですね。

山本：最適化問題は一つひとつ異なりますし、すべての問題を解ける万能なアルゴリズムはないですからね。

***

私の場合、アイデアからアルゴリズムをひねりだし、実装、評価してみると上手く行かないことが殆どです。失敗の連続と言ってもよいと思います。今まで100を越えるアルゴリズムを考え、試し、没にするということを繰り返してきました。そんな工房の木屑の中でも光るものは、数点あります。ORに取り組んで4年足らずの私がやってもそうなので、未だ未だ古典アプローチで出来ることは沢山あると思います。

＜厳密解に拘る＞

古典的ベンチマーク中、GPOST-Bや、WHPPは、厳密解を得るのが難しい問題です。

Algorithm3は、当初NearOptimalなソルバという設計でしたが、上記を正しく解くには、やはり厳密解ソルバでないと無理という結論に達しました。なので、厳密解ソルバに作り直しました。

これらは、あるNSP特有の特徴を持ったインスタンスであり、実は現実のユーザのインスタンス中にも、希少な事象ではない頻度で出現します。私的には、NSPにおける根源的な問題の一つであると認識していますが、この難しさはまたの機会にお話したいと思います。