ソルバのプロセス解説

エンジンは、下記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における根源的な問題の一つであると認識していますが、この難しさはまたの機会にお話したいと思います。

HIGHSベンチマーク

 http://plato.asu.edu/ftp/milp.html

にHIGHS1.1.1のMILPベンチマーク結果がUpdateされています。このベンチマークでは、240問題を一定時間内に解きます。解けた問題数が一番下のsolvedで分かります。Gurobiが一番解けていますがこれはいつもの事です。

1threadと８threadが載っています。1threadについて見て見ると、scaledは、Gurobiを1としたときの時間比で、CBCは、８．59倍比ということになります。(Dec.30.2021時点のデータ）体感的に、もう少し差があるような気がするのは、解けた問題を対象にした時間比較だからです。解けない問題を何らかの方法で時間に換算すれば、差はさらに広がるでしょう。

8threadでは、HIGHS1.1.1が追加されており、CBCでは、約14.5倍、HIGHSでは、約13倍になっています。ですから、HIGHSの方が少しだけ良いという私のNSPでの計測結果と符合しているのではないかと思います。

＝>https://schedule-nurse.blogspot.com/2022/02/highs.html

Mittlemanベンチマークについては、以下が参考になります。

untitled (orsj.or.jp)

COPTがMILPに参戦してきてそれなりの結果を残しています。こういう最適化領域の基幹的なソルバを設計する能力は、そのまま国力に通じる部分があると思います。（かってLSIを設計していたとき、その基幹的ツールである合成ツールは、Synopsysのデザインコンパイラという米国製が業界を席巻していました。ネーミングセンスがありますね。）

SCIPのソースコード行数は、GCC並みの50万行だったように記憶しています。ですから、一足飛びに商用並みのソルバを期待するのは難しいでしょう。HIGHSは、CBCに比べれば、モダンな筆致で、かなりコンパクトに書けています。MIPソルバについては、ほぼJulianHall教授とLeona Gottwaldさんの二人で開発しているようです。（Leona Gottwaldさんのプリプロセッサは、SCIPでも使えるようです。少し読んでみたのですが、殆ど理解できませんでした。）ちなみCBCは、IBMにいたJohnForrestさんによる開発で、かなりのご高齢のはずですが、未だメンテされているようで頭が下がります。後継の複数の開発者(大学の先生方)もメンテされているので開発が途絶える心配はないと思います。

日本の商用ソルバとしては、NTTDATAのNuOptが有名です。残念ながらGurobi/Cplexと比較データはありません。

クラッシックベンチマークの評価

 下界が分かるということは、素晴らしいことで、これ以上良い解はないことが解く前から分かります。最適化ソフトは、所詮は、探索をするものなのですが、どこまでやればよいのか、誰かが教えてくれないといつまでも探索を続けることになります。ところが、予めこれ以上良い解はないという値が分かっていれば、その値に到達した時点で探索を止めてよい訳です。（逆にそれを知りえないソルバでは、タイムアウトで止めるかユーザが止めるしかありません。）

クラッシックベンチマーク郡を再度評価していて、実は、このベンチマーク全ての厳密解を出せるソフトはGurobi/Cplexを含めて一つもない、ということに気づきました。

正確には、現在のスケジュールナースは出せますが一度の求解では、出力できませんでした。Algorithm3では、これを改善し、クラッシックベンチマークでは、全ての厳密解を一回の求解ボタンで出せる世界初のソフトとなります。これにより、実務的にも大方厳密解を出せるのではないか？と期待しています。

そこで、厳密解インスタンス率という、性能指標を提唱したいと思います。仮想的に世の中にある全てのベンチマークソフト郡、実務インスタンス郡を全て集めてテストしたときに、上界まで到達出来たインスタンス郡の比率を指します。

例えば、30secでは何％、60/300/600secでは何％　という風にプロットしてみたらどうなるか、興味があります。実際それが、体感的な性能に一番フィットするのではないかと思います。

＝＞評価しました。

https://schedule-nurse.blogspot.com/2022/02/blog-post_16.html

HIGHSのMIPソルバ

 JullianHall教授がCBCよりめっちゃ速くなったぜ！と豪語していたので、少し評価してみました。確かに、CBCより速い場合もありました。小さいインスタンス用途には良いのではないでしょうか？

SchedulingBenchmarksでは、Instance4までは解けましたが、それ以上は厳しそうです。確か、CBCが数分で解けるのは、Instance3位までだったので、多少良くなっているような気もします。=>https://schedule-nurse.blogspot.com/2022/02/highs.html

ちなみに、現在スケジュールナースは、Instance6まで厳密解を数秒、Instance8までの厳密解を数十秒以内に出力でき、Instance15/Instance21/Instance22の世界記録を保持しています。またINRC2(Internatial Nurse Scheduling Competition2 )データでは、State Of Art MIPSソルバを圧倒し、全インスタンスのKnownBestValue(これまでの世界記録)を更新しています。また、Classical　Benchmarksでは、全てのリニア重みインスタンスについて厳密解を出力できる世界初のソルバです。現在、他に出来そうなソルバは見当たらないので唯一無二のソルバになります。