2019年1月2日水曜日

INRC-IIは、超難問

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

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

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

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

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

LBは、これ以上良い値はないが、値が存在する保証ないという性質を持ちます。重みは、10,15,20,30,45,60,90 なので、そのGCDは、5です。例えば、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 
 LBUBGAP(%)LBUBGAP(%)
n030w4 1 6-2-9-1161516854.2 166016750.9
n030w4 1 6-7-5-3174018405.4  1820#VALUE!
n035w4 0 1-7-1-81250141511.7 133813702.3
n035w4 2 8-8-7-5104511458.7 107610850.8
n040w4 0 2-0-6-11335164018.6  1625100.0
n040w4 2 6-1-0-61570186515.8 174217651.3
n050w4 0 0-4-8-71195144517.3 129613252.2
n050w4 0 7-2-7-21200140514.6 130313352.4
n060w4 1 6-1-1-5238024653.4  2460100.0
n060w4 1 9-6-3-8261527304.2 266526750.4
n070w4 0 3-6-5-1228024306.2  2395100.0
n070w4 0 4-9-6-7199021256.4 210521200.7
n080w4 2 4-3-3-3314033205.4 329233000.2
n080w4 2 6-0-4-8304532406.0 317831900.4
n100w4 0 1-1-0-81055123014.2 116811750.6
n100w4 2 0-6-4-61470185520.8  1785100.0
n110w4 0 1-4-2-8221023907.5 232223300.3
n110w4 0 1-9-3-52255252510.7 245524550.0
n120w4 1 4-6-2-61790216517.3  201220200.4
n120w4 1 5-6-9-81820222018.0  205020500.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サイトよりは、現実的なベンチマークになっているような気もします。

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

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

0 件のコメント:

コメントを投稿