非商用、つまり無料の最適化ソルバで、ナーススケジューリング問題は、どこまで解けるか？
下図は、オープンソース(非商用)では、最高性能とされているHighs による結果です。 ベンチマークは、池上先生のikegami-3shift-Data1.1を使用しました。
スケジュールナースのアルゴリズム１は、5秒程度で、最適解証明(目的関数値3)まで済んでいます。ところが、アルゴリズム２(Highs)の方は、2時間経っても最適解に到達することは、出来ませんでした。2時間経った後の目的関数値は、厳密解の3倍以上になっています。結局24時間経っても最適化値に到達することはありませんでした。
ということで、精度、品質、時間いずれを取ってもあまり期待できない、という結果となりました。シフト勤務表として、この性能差がどのような影響を生むか、は次の通りです。
- 1. スケジュールナースで、全ての休み希望が通せても、非商用ソルバでは、通せない可能性がある
- 2. スケジュールナースで、全ての要求割りあて人数が確保出来ても、非商用ソルバでは、通せない可能性がある
- 3. トレードオフ等、さらに良くするための調整に非商用ソルバでは、時間がかかる
もしも、潤沢な人的リソースがある職場でしたら、無料の自動勤務表ソフトも良いかもしれません。
それは、希望休みを通すのに苦労するとか、毎日の夜勤者、早番、遅番、日勤者の確保に苦労する、という経験がないということですから。
問題は、
- 1．答えが見つからないのが、ソフトの能力の問題なのか？
- 2．物理限界によるものなのか？
ユーザからは、区別がつかない、ということです。
普通、市販されているスケジューリングソフトは、最適化ソルバではありません。「最適である」と言うためには、それより良い解がない ということを言わなくてはいけません。最適化ソルバなら、
「今よりも良い解がない」ということを把握したとき、探索は直ぐに打ち切り終了となります。それ以上時間を掛けても無駄、ということが自身で分かっているからです。
最適化ソルバでないときの基本戦略は、ずっと探し続けること です。どんなに時間をかけても、自身で今の解が最適かどうか分かっていないからです。挙動の違いは明らかなのですが、今、お使いのソフトが最適化ソルバかどうかは、多分ユーザには、分かりません。それは、現実規模のナーススケジューリング問題そのものが、難しい問題だからです。
Highs、SCIP、CBC 性能比較
比較結果 です。
これ によると、SCIPのソースコード量は、45万行を超えCPLEXのそれは、60万行を超えているということです。最適化ソフトウェアは、数理学的・学術的バックグランドを持ちます。非商用と、商用の性能差は10倍程度あるというのが一般的な認識です。しかし、非商用とは言ってもCBCを起点とする長い歴史の 中で、弛まぬ努力による改善が、多くの研究者達によってなされてきました。HighsのMIPソルバの設計者は、SCIP出身です。CBCは、 IBMをリタイアされた John forrestさんによる設計です。そして、商用ソルバの開発者の多くは、SCIPをバックグランドに持ちます。最近、Highs MIPソルバの設計者は、商用ソルバFICOに移動 しました。 最適化ソフトウェアというのは、長い歴史の中で育まれてきた、人類の英知の結晶と言ってもよいと思います。おいそれと出来る代物ではないことは確かです。
世界最高の、汎用最適化ソルバ(MIPソルバ）なら、ナーススケジューリング問題は、解けるのか？
世界最高とされているのは、Gurobi
です。MIPソルバの進歩は、凄まじく、PC性能向上込みで考えると、1991年時のMIPソルバの性能を1としたとき、2015年の性能比は、4500億倍になっている、という報告もあります。
で、結果は、こちらをご覧
頂きたいのですが、スケジュールナースに比べて残念な結果となっていますが、それでもかなり解けていることが分かります。
最高性能の商用MIPソルバを使えば、ナーススケジューリング問題はかなり解けるので、それをクラウドで利用して、ナーススケジューリング問題を解いている業者さんもいらっしゃると思います。私もお金に余裕があったら使いたいアプローチ(例えばアルゴリズム５として搭載）ですが、残念ながら、現在の料金月額480円の10倍を頂いたとしても、ペイするのは、難しいでしょう。
それでは、非商用の出番はないのか？
ナーススケジューリング問題でなければ、可能性はあります。ナーススケジューリング問題の特徴は、縦横に制約が絡んでいる、ということにあります。
横方向の制約がない、もしくは、規模が小さい、または横方向の制約が殆どないのならば、解ける可能性はあります。Excelのソルバでも解ける可能性はあります。
つまり、看護師・介護士の勤務表の類でなければ、解ける可能性は大きいと言えると思います。また、潤沢な人的リソースを持つ職場ならば、性能の良いソルバは、必要ないかもしれません。