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は、期間が半年ですが、前述の特殊状況によるところが大です。