Instance規模について

 問題の規模については、一概に言えないところがあるのですが、指標はあります。次の計算式です。

規模=Days  * Staffs * ShiftTypes

です。例をあげましょう。SchedulingBenchmarks　Instance1は

２Weeks,８Staffs,　ShiftTypes=1になっています。スケジュールナースの場合は、陽に休みを定義していますので、シフトの状態数は+1になります。

instance規模１＝2*7*8*(1+1)=224

となります。以下同様に、

規模に応じて、所要メモリも増え探索空間増えるので難易度も上がっていきます。昔取ったデータでは、CBCは、インスタンス2程度、SCIPでもインスタンス4程度までしか厳密解は得られなかったと記憶しています。この問題群は、商用MIPソルバの独壇場にありCPLEX/Gurobiで解けます。現実規模のインスタンス郡の中で唯一Instance15だけが、未だに厳密解が知られていません。（このインスタンス上界下界の世界記録はScheduleNurse3が保持しています。）

Instance21以上は、規模が大きくすぎて、MIPソルバでも歯が立たず、未だ厳密解が知られていません。

SchedulingBenchmarksは、行方向のソフト制約がなく、実務的にはほぼ有り得ないインスタンス郡です。

実務インスタンスでは、行方向のソフト制約が入ってきるのが普通です。前々回あたりで言及したように、探索空間がさらに広がる方向になります。ですので、半年や、1年と言ったインスタンスで、厳密解を求めるのは、ほぼ無理です。Instance20は、期間が半年ですが、前述の特殊状況によるところが大です。

Instance13の求解速度改善

 マルチスレッドの方法見直しにより速度改善しました。(7368sec→5091sec)

なお、4core/4threads Xeon W3565 3.2GHzの結果です。

Instance13が解けた

 SchedulingBenchmarksで、instance13は、Reasonableな時間内に解けていませんでしたが、解けました。Pieter Smet さんが既にCplex/Gurobiで解いています。

What's new? (schedulingbenchmarks.org)

によると12000secかかっています。

Algorithm4では、7368secで解けました。

instance13は、120人19シフトでかなり大規模なインスタンスです。下のように、LB=UB=1348で厳密解が得られています。

many core 対応

 安価に使用可能になってきました。

最近CPU界隈が面白い、という古参のボヤキ - Qiita

AWS Lambdaのコア数を確認 - Qiita

Algorithm4は、前述の最短経路問題解法を使用した数理解法になっています。現在は、ベンチマークテスト専用用途です。これをリニューアル、完全にマルチスレッド化し、実務的なインスタンス用途と、さらなるベンチマーク世界記録更新を目指そうと思います。SimplexやBranch&Bound等、主なMIP解法は、マルチスレッドの恩恵を基本得にくいのですが、NSPに限定すれば、数理解法でも恩恵を得ることができます。（使いどころは、やや限定されており、後で詳述します。）

thread_localとローカルに定義されたstd::vectorの組み合わせ - Qiita

TTS2

 このサイトは、WEBアプリと思っていたのですが、単にブラウザの音声合成機能を使っているだけのようです。ならばと、Windows１０の音声合成も使ってみたのですが、ブラウザとはなぜか雲泥の差です。IBM　Watsonも使ってみたのですが、WEBデモの質が何故か得られないので止めました。

制約付最短経路問題 離散解法か連続解法か

NSPの部分問題である制約付最短経路問題をできるだけ速く解くというのは、NSP最適化において重要です。 

二つのアプローチがあります。言い換えるとグラフ解法か、分岐限定法かということです。

どちらが速く求まるか？というのは、問題によります。要因として大きいのは、基数制約の個数です。基数制約Σx(i)<=y がないときは、グラフ解法の方が速く、基数制約の個数が多くなるに従って連続解法の方が速く求まる傾向にあります。グラフ解法では、基数制約の個数が増えると指数関数的に保持する状態メモリが増えてきます。そのためインスタンスによっては破綻する可能性があります。基数制約のない問題というのは考えにくいので、連続解法の方が汎用性があります。一方、基数制約が少なければ、グラフ解法速度は、連続解法を圧倒する場合もあるので、インスタンスにより解法を変えることが理想的です。

連続解法の問題は、分岐限定法の速度です。分岐限定法の前にヒューリスティクスでOpt解に近い解を得ることや、削除平面を使いますが、この分野は、商用MIPソルバの独壇場であり、商用MIPソルバには敵いません。また、絶対的な速度の他に、解が出るまでの時間が一定ではない、という問題もあります。グラフ解ならば、解が出て来るまでの時間はほぼ一定ですが、連続解法では、時間が読めないという問題もあります。

参考リンク

https://speakerdeck.com/umepon/mathematical-optimization-in-60-minutes

https://speakerdeck.com/umepon/branch-and-bound-algorithm-and-cutting-plane-algorithm-for-integer-programs

https://speakerdeck.com/umepon/approximation-algorithms-for-combinatorial-optimization-problems

基数制約とソフト許容エラー数との関係

 基数制約とは、数を数える制約のことで、一般に不等式になります。（LP制約としては、基数制約しかないとも言えます。ORから見ると、AND・OR制約は、基数制約の特殊形です。）

Σxi <=Max

Σxi <=Min

単純な例で、30日中休みを8回だけ取る制約を考えます。この場合の探索空間（ありえる状態空間）は、どうなるでしょうか？

計算方法は、30C8-30C7です。30個から、8個取る組み合わせ、つまり

Σxi <=8から

Σxi <=7を引き算すれば、Σxi>=8 && Σxi<=8となります。

これをExcelで計算したのが上のテーブルです。組み合わせ数が、381万程度となります。

ソフト許容を1とした場合は、(8,8)→(9,7)に拡大されます。以下同様です。

ソフト許容を３とした場合は、探索空間が14倍に増えることを意味します。ソフトエラーまで含めれば、それだけ満たす可能性が増えることを意味しますが、同時に探索負荷が重くなる（時間がかかる）ことを意味します。

ちなみに、日数を31にしただけでも結構な違いがあります。これが月ごとの難易度の違いの原因です。

また、それ以上に休み数の違いがドラスティックな違いを生むことが分かります。

基数制約単体に限れば、上のように組み合わせ数は計算できますが、現実の制約は、制約郡であり複雑です。その総数を計算するのは容易ではありませんが、離散解法（グラフ解法）により個々のRoster（個々人）毎に正確に求めることは可能です。しかし、Rosters全体でみたときに、現実時間内に総数を求めることは、小さなインスタンスを除けば大変に難しいです。（出来ないと言った方がよいかもしれません）。

ソフト許容を無限に許せば、探索負荷が重くなるのは、想像できると思います。一方で、全てをハード制約にすれば、簡単に解のない事態になってしまいます。適度なソフト制約化が、Reasonableな時間で解を得る鍵となります。