INRC-IIは、超難問

スタッフ数5人のインスタンスでさえ、CPLEXで5分近くかかりました。

n005w4_1_6-2-9-1　LB=UB=1520

Antoine Legrainさんの論文では、厳密解が求まるのは、21人以下の4Weeksのみのようですが、私のところでは、個別に厳密解が得られる場面もありそうです。

４Weeksの全てのインスタンスにおいて、未踏の解(新しい解)を発見しました。（解は、Validatorで確認済みです。） Antoine Legrainさんのデータは、24hRun、私のところは、数時間のRunです。

全てのインスタンスにおいて、優れた結果となっています。

LBは、これ以上良い値はないが、値が存在する保証ないという性質を持ちます。重みは、１０,１５，２０，３０，４５，６０，９０　なので、そのGCDは、５です。例えば、LB=1338のときにありえる整数解の最小値は、GCD値を利用すると1340ということになります。この場合、UB=1340を発見した時点で探索終了とすることができます。極小さいインスタンスを覗いて、こんな風に上手くいく例はあまりありません。LBーUB間には、GAPあるのが普通であり、この値が大きいとき、これ以上解がないという証明をするためには、より広大な探索空間をスキャンせざるを得ず、それだけ、UBの最小値を得てから長い時間を要するのが普通です。

UBは、実際にValidatorが確認した値です。GAP＝(UB-LB)/LB として算出しています。
GAP=0 となったとき、UB=LBですから、これ以上良い値はありえないという証明になります。つまり厳密解が求まったことを示しています。黄色部がGAP=0となっています。GAP値で比較してみると性能差が分かります。
GAPが1%未満というインスタンスが結構あるので、時間をかければ厳密解が求まるインスタンスもありそうです。最新結果はhttps://english.nurse-scheduling-software.com/benchmarks/benchmarks.html

	Known Best Result			New Result
	LB	UB	GAP(%)	LB	UB	GAP(%)
n030w4 1 6-2-9-1	1615	1685	4.2	1660	1675	0.9
n030w4 1 6-7-5-3	1740	1840	5.4		1820	#VALUE!
n035w4 0 1-7-1-8	1250	1415	11.7	1338	1370	2.3
n035w4 2 8-8-7-5	1045	1145	8.7	1076	1085	0.8
n040w4 0 2-0-6-1	1335	1640	18.6		1625	100.0
n040w4 2 6-1-0-6	1570	1865	15.8	1742	1765	1.3
n050w4 0 0-4-8-7	1195	1445	17.3	1296	1325	2.2
n050w4 0 7-2-7-2	1200	1405	14.6	1303	1335	2.4
n060w4 1 6-1-1-5	2380	2465	3.4		2460	100.0
n060w4 1 9-6-3-8	2615	2730	4.2	2665	2675	0.4
n070w4 0 3-6-5-1	2280	2430	6.2		2395	100.0
n070w4 0 4-9-6-7	1990	2125	6.4	2105	2120	0.7
n080w4 2 4-3-3-3	3140	3320	5.4	3292	3300	0.2
n080w4 2 6-0-4-8	3045	3240	6.0	3178	3190	0.4
n100w4 0 1-1-0-8	1055	1230	14.2	1168	1175	0.6
n100w4 2 0-6-4-6	1470	1855	20.8		1785	100.0
n110w4 0 1-4-2-8	2210	2390	7.5	2322	2330	0.3
n110w4 0 1-9-3-5	2255	2525	10.7	2455	2455	0.0
n120w4 1 4-6-2-6	1790	2165	17.3	2012	2020	0.4
n120w4 1 5-6-9-8	1820	2220	18.0	2050	2050	0.0

Santosさんとの結果を比較しても優秀な結果となっています。
https://www.gerad.ca/colloques/ColumnGeneration2016/PDF/HaroldoSantos.pdf

António Ramadasさんとの比較でも同様です。
https://github.com/antonio-ramadas/nurse-rostering-solution/blob/master/A%20GRASP%20Approach%20using%20a%20Constructive%20Heuristic%20Approach%20to%20the%20Nurse%20Scheduling%20Problem.pdf

その他INRC-II関係の論文です。ttp://www.patatconference.org/patat2016/files/proceedings/paper_56.pdf
http://www.patatconference.org/patat2016/files/proceedings/paper_21.pdf
http://patatconference.org/patat2018/files/proceedings/paper46.pdf
https://lib.ugent.be/fulltxt/RUG01/002/273/956/RUG01-002273956_2016_0001_AC.pdf
http://www.scs-europe.net/dlib/2016/ecms2016acceptedpapers/0502-simo_ECMS_0113.pdf
http://www.cs.nott.ac.uk/~pszjds/research/files/dls_mod2017.pdf
 http://ds-o.org/images/FAIM_papers/Kumar_V2.pdf
ということで、サーベイした中では、圧倒的な結果となりました。

＊Sara Ceschiaさんの論文で一部私のより良い値が出ていますが、恐らく誤りです。その理由は、私のLB値よりも小さいこと、なおかつValidatorの値も論文中の値と一致していないこと　の2点によります。


このインスタンスの特徴としては、SchedulingBenchmarkサイトで皆無だった横方向のソフト制約が多いことが挙げられます。ただし、日本的な制約ではなく、RealProjectからは逸脱している感が否めません。それでも、横方向のソフト制約がこれでもか、という位入っているので、SchedulingBenchmarkサイトよりは、現実的なベンチマークになっているような気もします。

シフト数は、４ですが、少ない代わりにスキルという概念が導入され、シフト数で表現すると最大16シフト位には相当します。このスキルの実装がまた難しく、苦労しました。（SC2では、スキルをタスクとして扱う予定です。）

もう一つの特徴は、混沌としたソフト制約の海の中に解が存在する、とでもいいましょうか、とにかく難しいインスタンスになっています。