2022年3月29日火曜日

数式記述方法

 https://www.hostmath.com/

で記述しています。数式を書いて、Show Embeded CodeをクリックするとHtmlコードが出力されるので、これをでファイルにしてブラウザで表示させます。それをSnapshotする感じです。




投稿者 時刻: 0 件のコメント:

2022年3月21日月曜日

スポット制約が効かない

制約は、ソフトレベルで、たとえば、
 ７：最強のソフトレベル　必ず実現したいが、ハードエラーは嫌だ。 
 ３：できれば実現したいソフトレベル
 １：最弱のソフトレベル。通ればラッキー。

 という具合に重みを持たせる設計にしていると思います。 しかし、今月だけスポット的に、こうしたいという場合もあるかと思います。 その場合は、予定として書き込んでしまうのがもっとも簡便ですが、制約で記述したい場合もあるかと思います。

その場合は、特定Daysを曜日の”特定の日の設定”で作れば、他の月には悪影響を及ぼさずに今月スポットの制約を記述することが出来ます。 効いている全てのソフトレベルを凌駕するソフトレベル、つまりハード制約にして、強制的、有無を言わさぬ戦略を取ります。

 もし、そのようなスポット制約が効かない場合は、他に制約しているハード制約がないかを調べてみてください。たとえば、
●次のソフト制約で、許容範囲を超えています。 
●　週あたりの勤務回数設定2 ｘｘｘ
というエラーは、ハード制約を指しています。SeqErrorのエラー許容量がLimitを超えているということを指しているので、GUIもしくは、Pythonでの修正が必要になります。

スポット制約で　min>=９としても
Python制約で、min=max=6,エラー許容量２の場合、つまり、　6-2<=x<=6+2 の場合は、4<=x<=8の方が先にネックとなります。そのためにエラーメッセージもPython側になります。

スポット制約で　min>=9とするためには、まずPython　SeqErrorのエラー許容量を３に修正後に、スポット制約を記述してください。(min>=10の場合は、４）






投稿者 時刻: 0 件のコメント:

Python中SeqErrorの使い方

下記のような制約文を例に説明します。

s="週あたりの勤務回数設定"+str(week)+' '+"person"+str(person) sc3.AddSoft(sc3.SeqError(min,max,2,VList),s,7) 

 SeqErrorの中身はとりあえず無視して、AddSoftの中身です。 s=は、エラー解析表示用のための文字列です。ハードエラーが出て、その原因表示のときに使われるのみです。空白行でもよいのですが、ハードエラー時に何も表示されなくて手がかりが無くなってしまうので、 付加しています。 

 sc3.AddSoft(sc3.SeqError(..),s,7)

 次に、７ですが、これは、ソフトレベルで、求解画面で、言語:7となっている筈です。 つまり、上記文は、「ソフトレベル７のソフト制約を実行しなさい、」という意味になります。 次に、sc3.SeqErrorの意味ですが、アドバンストユーザマニュアル、エラー許容量の設定が、対応するGUIの説明になります。（GUIの設定ですが、エンジン内部では、SeqErrorが動いています。） 
 SeqError(最小値、最大値、エラー許容量、対象集合) 

となっています。たとえば、min=6,max=6, エラー許容量=2だと、min-2＜＝=x＜＝max+2となって、 ソフト制約の範囲は、4-8までに制約されます。言い換えると暗黙のハード制約 ４＜＝x＜＝８ が制約として入っているということになります。これ以上は、いくらなんでも許容できない、というときのリミッタとすることがその目的です。

 で、私が作成するプロジェクトでは、この辺の設定を大体３位に設定していることが多いと思いますが、 これは、もちろんその制約毎に相応しい値が存在すると思います。これでエラーが出た場合は、調整が必要になる場合もあります。 エラーが出た場合は、見直して、たとえば、上記の場合、 エラー許容量を ２→４ とすれば、 ２＜＝ｘ＜＝１０ に拡大されます。この範囲であれば、ソフト制約として作用し、6からの偏差が目的関数値に加算されます。 しかし、xが１以下または、１１以上しかとり得ないときは、ハードエラーとして報告されます。
投稿者 時刻: 0 件のコメント:

2022年3月11日金曜日

タスクとシフト表記を結びつける

 今回は、高度なTIPSです。

タスクは、一つのフェーズで一つActive状態を持ちます。シフトは、複数のフェーズに跨る概念です。前回の場合、２Phaseで、タスクは、各々DummyDay、とDummyというDefault状態が存在します。これは、タスクも、シフトと同様に各Phaseで、MostOne　LeastOneで記述しなければいけない、というルールに基づいています。Day帯で言えば、振休か、日直か2状態がActiveになりえるBitですが、それ以外という意味のBitがDummyDayになります。

で、ph0=DummyDay,ph1=Dummyだった場合の休日は、”休み”とシフト上表記したくなりました。

もし、”休み”というシフトがない場合、タスク的には、何もないにもかかわらず、休みの日、日勤シフトと表記されるかもしれません。休みシフトと上記タスクを結びつける記述がGUIでは書けないので制御できないのです。

これは避けたい、と個人的に思い次のようなBindingをPythonで記述しています。

If　day in 今月休日:

    予定が入っていないなら:

         [DummyDay,Dummy] => 休みシフト　

としたい訳です。

A=TaskVar[person][day][0][DummyDay] &&　TaskVar[person][day][1][Dummy];

B=ShiftVar[person][day]["休み"]

 何度もやっているようにImplication　A->Bは、!A|Bとなります。

!A=~TaskVar[person][day][0][DummyDay] |　~TaskVar[person][day][1][Dummy];

なので、Python　Programは、以下の通りになります。

for day in 今月休日:#

            if shift_schedules[person][day][0]=='':
                v=sc3.GetShiftVar(person,day,'公休')
                v1=sc3.GetTaskVar(person,day,0,'DummyDay')
                v2=sc3.GetTaskVar(person,day,1,'Dummy')
                s='タスクがない休日は休日シフトにする　'+staffdef[person]+' '+daydef[day]
                sc3.AddHard(v | ~v1 |~v2,s)

投稿者 時刻: 0 件のコメント:

2022年3月4日金曜日

Integer Branch

 は、私の造語です。Branching　Treeは、基本的にDFS(Depth First Search)で行います。その際、どのノードかを始点とするかについては、登録された目的関数値が低い順に行います。しかし、UBとのギャップが未だあり、その間にGCDで割り切れる整数値のノードが存在した場合、ある条件下で、そのノードをブランチングの始点としています。これは、GCDで割り切れる整数目的関数値を持つノードは、そのまま解になる可能性が比較的高い、という私の知見に基づいています。比較的というのは、絶対ではなく外れることも多いのですが、他のFractionalなノードに比べれば、比較的高そうだ、ということは言えると思います。なお、これに関する論文は見たことがありません。

Integer　Branchingにより、8時間経っても厳密解証明が出来なかったインスタンスが10分で出来ることもあったので、効果はあるのではないかと思います。

これを適用することにより、INRC2 4WEEKSについては、ほぼ全てのインスタンスについて厳密解証明が完了しました。一応というのは、スケジュールナースⅢ以外で、このインスタンス郡について一インスタンスでも厳密解証明はおろか最適目的関数値に達したソルバは、皆無なので今のところ、他に確かめるすべはなく、自分のプログラムを信じるしかありません。(n005w4という極小さい、例題インスタンスについては、厳密解が各ソルバで得られています。）

適用は、139Aからになっています。次は、終了時のログの例です。この例では、UB=2115が確定しています。残っているノードが次のようになっています。この場合GCD=5なので、整数解が得られたとしても、2115以上となります。残っているノードで、2115-5以下のノードがないので、LB=2115　＆＆UB=2115で厳密解証明完了となります。ですから本来であれば、LB=2115と記すべきですが、最後にLBとなっているのは、初期時のLBを記しているからです。


branch_node_map.size()=54

Remaining objs

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2112.5

2113.51

2114.23

2114.57

2115

2115

2115

2115

2115

2115

2115

2115

2115

2115

2115

2115

2116.67

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2117.5

2119.74

2119.74

2122.14

2127.5

Final LB=2105 UB=2115 900.815[sec]

Finished solving process. 902 (sec)




投稿者 時刻: 0 件のコメント:

2022年3月2日水曜日

INRC2 8weeks

INRC2_8weeks.md

8weeks

Instance Weeks Employees Best known LB Best known UB Known Best Gap Schedule NurseⅢ LB Schedule NurseⅢ　UB Schedule Nurse Ⅲ　Gap Note
n030w8 1 2-7-0-9-3-6-0-6 8 30 1920 2070 7.81% 1994 2010 0.80%
n030w8 1 6-7-5-3-5-6-2-9 8 30 1620 1735 7.10% 1710 1730 1.17%
n035w8 0 6-2-9-8-7-7-9-8 8 35 2330 2555 9.66% 2408 2445 1.54%
n035w8 1 0-8-1-6-1-7-2-0 8 35 2180 2305 5.73% 2153 2245 4.27%
n040w8 0 0-6-8-9-2-6-6-4 8 40 2340 2620 11.97% 2464 2540 3.08%
n040w8 2 5-0-4-8-7-1-7-2 8 40 2205 2420 9.75% 2285 2315 1.31%
n050w8 1 1-7-8-5-7-4-1-8 8 50 4625 4900 5.95% 4778 4825 0.98%
n050w8 1 9-7-5-3-8-8-3-1 8 50 4530 4925 8.72% 4744 4770 0.55%
n060w8 0 6-2-9-9-0-8-1-3 8 60 1970 2345 19.04% 2099 2155 2.67%
n060w8 2 1-0-3-4-0-3-9-1 8 60 2260 2590 14.60% 2394 2440 1.92%
n070w8 0 3-3-9-2-3-7-5-2 8 70 4400 4595 4.43% 4475 4540 1.45%
n070w8 0 9-3-0-7-2-1-1-0 8 70 4540 4760 4.85% 4637 4675 0.82%
n080w8 1 4-4-9-9-3-6-0-5 8 80 3775 4180 10.73% 3942 4015 1.85%
n080w8 2 0-4-0-9-1-9-6-2 8 80 4125 4450 7.88% 4287 4325 0.89%
n100w8 0 0-1-7-8-9-1-5-4 8 100 2005 2125 5.99% 2026 2045 0.94%
n100w8 1 2-4-7-9-3-9-2-8 8 100 2125 2210 4.00% 2153 2170 0.79%
n110w8 0 2-1-1-7-2-6-4-7 8 110 3870 4010 3.62% 3990 3990 0.00% SC3 shows UB=4050, while Verilator shows UB=3990
n110w8 0 3-2-4-9-4-1-3-7 8 110 3375 3560 5.48% 3450 3450 0.00% SC3 shows UB=3510, while Verilator shows UB=3450
n120w8 0 0-9-9-4-5-1-0-3 8 120 2295 2600 13.29% 2485 2490 0.20%
n120w8 1 7-2-6-4-5-2-0-2 8 120 2535 3095 22.09% 2912 2920 0.27%

Detail Data

投稿者 時刻: 0 件のコメント:

2022年3月1日火曜日

Nurse Rostering Benchmark Instances

new_scheduling.md

Nurse Rostering Benchmark Instances

References

  1. Nurse Rostering Benchmark Instances

  2. computational_results_on_new_staff_scheduling_benchmark_instances

  3. Burke E.K. and T. Curtois. New Approaches to Nurse Rostering Benchmark Instances. European Journal of Operational Research, 2014. 237(1): p. 71-81. pdf.

  4. Strandmark, P., Qu, Y. and Curtois, T. First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem. Computers & Operations Research, 2020. 120, p. 104945. (pdf)

  5. Demirović, E., Musliu, N., and Winter, F. Modeling and solving staff scheduling with partial weighted maxSAT. Annals of Operations Research, 2019. 275(1): p. 79-99.

  6. Smet P. Constraint reformulation for nurse rostering problems, in: PATAT 2018 twelfth international conference on the practice and theory of automated timetabling, Vienna, August, 2018, p. 69-80.

  7. Rahimian, E., Akartunalı, K., and Levine, J. A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems. European Journal of Operational Research, 2017. 258(2): p. 411-423.

Speed Comparison

Optimality Proven Instances

Instance Name Cplex Gurobi AutoRoster ScheduleNurse3
Instance4 4.4/0.6=7.3 4/0.6=6.7 6/0.6=10 0.6/0.6=1
Instance5 29/2.4=12.1 16/2.4=6.7 - 2.4/2.4=1
Instance6 7/1.6=4.4 5/1.6=3.1 - 1.6/1.6=1
Instance7 61/6.2=9.8 20/6.2=3.2 - 6.2/6.2=1
Instance8 4623/50=92.5 931/50=18.6 - 50/50=1
Instance9 - - - -
Instance10 41/13=3.2 20/13=1.5 660/13=50.8 13/13=1
Instance11 45/18=2.5 18/18=1 71/18=3.9 37/18=2.1
Instance12 260/54=4.8 185/54=3.4 660/54=12.2 54/54=1
Instance13 - 12115/572=21.2 - 572/572=1
Instance14 690/4.3=160.5 205/4.3=47.7 - 4.3/4.3=1
Instance15 - - - -
Instance16 937/4.3=217.9 78/4.3=18.1 - 4.3/4.3=1
Instance17 4022/4.8=837.9 143/4.8=29.8 10000/4.8=2083.3 4.8/4.8=1
Instance18 21387/135=158.4 787/135=5.8 - 135/135=1
Instance19 - 3006/3006=1 - 5285/3006=1.8
Instance20 - 3665/678=5.4 - 678/678=1

Optimal Objective Reached Instances

|

Instance Name Cplex Gurobi AutoRoster ScheduleNurse3
Instance4 4.4/0.5=8.8 4/0.5=8 6/0.5=12 0.5/0.5=1
Instance5 29/2.4=12.1 16/2.4=6.7 11/2.4=4.6 2.4/2.4=1
Instance6 7/1.6=4.4 5/1.6=3.1 - 1.6/1.6=1
Instance7 61/6.2=9.8 20/6.2=3.2 - 6.2/6.2=1
Instance8 4623/50=92.5 931/50=18.6 - 50/50=1
Instance9 - - - -
Instance10 41/13=3.2 20/13=1.5 660/13=50.8 13/13=1
Instance11 45/18=2.5 18/18=1 71/18=3.9 37/18=2.1
Instance12 260/54=4.8 185/54=3.4 660/54=12.2 54/54=1
Instance13 - 12115/572=21.2 - 572/572=1
Instance14 690/4.3=160.5 205/4.3=47.7 - 4.3/4.3=1
Instance15 - - - -
Instance16 937/4.3=217.9 78/4.3=18.1 - 4.3/4.3=1
Instance17 4022/4.8=837.9 143/4.8=29.8 10000/4.8=2083.3 4.8/4.8=1
Instance18 21387/135=158.4 787/135=5.8 - 135/135=1
Instance19 - 3006/3006=1 - 5285/3006=1.8
Instance20 - 3665/678=5.4 - 678/678=1

Time - Number of Instances proven optimality

Time - Number of Instances reached optimal objective

Detail Data

投稿者 時刻: 0 件のコメント:
登録: 投稿 (Atom)