Friday, May 20, 2022

Symmetry Breaking

 数理ソルバ的解法で問題となる現象で、対称性が求解スピードを悪化させたり、最悪の場合、誤収束してしまうことがあります。NSPの場合、無縁だと思っていたのですが、実は、結構な頻度で、その現象が観測されることが分かりました。

具体的には、

(A)ハード予定制約が全くないインスタンス

(B)結構ハード予定制約が詰まったインスタンス

をの求解速度を比較してみます。Algorithm1の場合は、Bが速くなることは殆どありません。このことは、探索空間の減少より解空間の減少が大きいことが原因と考えています。

しかし、Algorithm3の場合、Bの方が速くなることが結構あります。(ただし、Version152から、Algorithm3のStabilization方法を変えているので、目だった差にはなりません。)

同じテストインスタンスなのに挙動が反対になるReasonableな説明としては、Symmetry Breakingによる補償効果があったのではないかと思います。



Thursday, May 19, 2022

お医者さまの勤務表メンテナンス

 (1) 「振替休暇」が「PM業務」日に自動割り当てされることがある。

バグです。これを防ぐには、次のよう変更します。

変更前



変更後


業務シフトで、チェックがされていないフェーズのタスクは、どのようなタスクもアクティブにはなりません。つまり、振り替え休日が設定されることはありません。チェックされているフェーズのみが有効フェーズとして働きます。

また記述されていないシフトは、チェックなし、と解されます。

なお、入力は可能ですが、次のバージョンより入力すべきではないタスクには、シフトの背景色が付くのですぐ気づくと思われます。(解も同様です。)



上のようなシフト入力の場合に、タスク入力は、下のようになります。


解も、背景シフト色で埋められます。


それでも、入力した場合は、タスクの入力は無視されてシフトが生かされた解となります。Python記述を追加して、エラー入力を検出することも可能ですし、また、ハード制約として求解できないようにすることも可能ですが、とりあえずは、上記実装で運用してみていただきたいと思います。

(2)有給休暇「有」と、休暇「休」が「当禁」「遅禁」に入力できない

これは、設計通りで、そのように意図していました。入力可能なように変更するには、(1)の通りとしてください。

(3) 平日の夜禁止はどのようにするのか

既に、夜勤禁として記述済みです。



なお、下のように記述しても、OKです。(意味は同じというよりも完全に同じものを指しています。)



(4) スタッフ定義のスタッフ名 変更したら予定が消失

   スタッフプロパティのスタッフ名を変更すると紐づいているデータが

 画面から消失するのはわかるのですが、残す方法はないでしょうか?

少し面倒ですが手は二つあります。

一つ目の方法は、ファイルとして保存(CSV)として保存します。CSVファイルはプロジェクトフォルダに出力されます。それをExcelで開いて必要部分をコピペします。

 二つ目の方法は、スケジュールナースをもう一つ立ち上げて、同じプロジェクトを読みます。片方は名前を変更します。変更していないもう一つのスケジュールナースから、コピペします。


質問その1)列制約にタブが2つあるのはどのような使い道でしょうか。

単にグループ毎の制約のオンオフを行う、等の管理上の便宜を意図していますが、今回の場合、単に開発時の足跡で意味はありません。

質問その2)求解のソルバ設定 CPU数 はいくつが適当でしょうか。また、アルゴリズムは選択できるようですが、 1,3のどちらがよろしいでしょうか?

前回のブログをご参照ください。



Wednesday, May 18, 2022

Algorithm 1、3の違いについて

 Q.1と3が選択できるようになっていますが、どちらを使用すればよいでしょうか?

明確に目的と用途が異なります。

<制約設計時>

Algorithm1を使用して下さい。制約設計時は、デバッグツールとして、解がない場合の原因解析が必須となります。原因解析が効くのは、Algorithm1のみです。

<普段の求解時>

多くの場合、Algorithm1が最も速く、かつ安定に動作します。

ーCPU数

1で良いです。2以上でも動作しますが、さして変わりません。

<厳密解を求めたい場合>

Algorithm1は、原則的にNear Optimal解を出力します。目的関数値(UB)が0の場合は、Optimalです。時間がかかって、UBが0でない場合は、厳密解ではない可能性があります。特に、多くのエラーがある場合は、もう少し良い値が存在するかもしれません。そのような場合で、厳密解(物理的な限界値)を求めたい場合の選択肢としては、Algorithm2,3,4があります。公式サポートは、1,3のみですが、2,4も設定すると動きます。

アカデミックなベンチマークではこの厳密解に達するまでの時間を指標としていることもあり、スケジュールナースⅢのベンチマークデータは全てAlgorithm3を使用しています。タイムアウトはなく、厳密解を見つけるまで動作し続けます。従って、Algorithm1よりも悪い値で終了することはありません。また、Algorithm1の出力値と比較して、Algorithm1が厳密解目的関数値もしくは、極めて近い値を出力していることも確認できると思います。(途中で求解を止めるには中止ボタンを押してください。)

<Algorithm3>

推奨環境:32GB以上のメモリ、CPUコア数8以上の最新のプロセッサ。(全CPUパワーをフルスレッドで使います。)

ほぼ全てのインスタンスで動作しますが、Algorithm1で動作確認した上で御使用ください。

ー威力を発揮する場面

Algorithm1では、時間がかかるとき(特に多くのハード予定またはソフト制約が詰まっている)に有効です。また、LB値(この値に到達する保証はないが、目的関数値でこれ以上より良い値になることも絶対にない)を知りたい場面でも有効です。

ー動かないインスタンス

一部、フェーズ変数を用いた複雑な制約については、動かないものがあることが分かっています。


<Algorithm2>

オープンソース MIPソルバHiGHSによる解法になります。小さいインスタンス(スタッフ数10人程度)ならば、動く可能性がありますが、中規模以上では時間がかかり、求まらない可能性が高いです。

<Algorithm4>

Algorithm3は、Algorithm4と1の合体です。インスタンスによってAlgorithm1を走らせる場合がありますが、Algorithm4は、このフェーズがありません。









Tuesday, May 3, 2022

INRC2 New Best Results

Inspired by the paper, we again took data on all the instances in the paper. It describes CPEX found no exact solution for all the instances even after 24 hours of the run. ScheduleNurse3 obtained an exact solution on almost all instances in the paper. Compared to other academic solvers, the speed is overwhelming for near-optimal data.

Schedule Nurse 3 (Ryzen5800X 64GB Win10) Mathematical Models and a Late Acceptance Fix-and-Optimize Approach for a Nurse Rostering Problem (ufrgs.br)
Legrain et al. (2019) Gomes et al. (2017) Ceschia et al. (2020) LAFO
LB=A Validator(SC3) UB Validator(SC3) Optimality Proven Time(sec) UB reached time(sec) GAP( (obj-A)/A*100)[%] UB Time GAP( (obj-A)/A*100)[%] UB Time GAP( (obj-A)/A*100)[%] UB Time GAP( (obj-A)/A*100)[%] UB Time GAP( (obj-A)/A*100)[%]
staff=35 n035w4_2_8-8-7-5 1080 1080 275 275 0 1,145 1,803 6.0 1,085 5,586 0.5 1,151 1,317 6.6 1,237.00 5,160 14.5
n035w4_0_1-7-1-8 1360 1360 471 471 0 1,415 1,803 4.0 1,425 3,269 4.8 1,455 1,317 7.0 1,565.90 5,160 15.1
n035w4_0_4-2-1-6 1605 1605 203 103 0 1,705 1,803 6.2 1,615 5,124 0.6 1,663 1,317 3.6 1,760.50 5,160 9.7
n035w4_0_5-9-5-6 1500 1500 5188 241 0 1,575 1,803 5.0 1,540 6,872 2.7 1,544 1,317 2.9 1,628.30 5,160 8.6
n035w4_0_9-8-7-7 1335 1335 2460 1110 0 1,430 1,803 7.1 1,365 4,475 2.2 1,421 1,317 6.4 1,500.00 5,160 12.4
n035w4_1_0-6-9-2 1300 1300 361 361 0 1,375 1,803 5.8 1,385 5,359 6.5 1,391 1,317 7.0 1,487.00 5,160 14.4
n035w4_2_8-6-7-1 1080 1080 287 287 0 1,425 1,803 31.9 1,335 6,453 23.6 1,340 1,317 24.1 1,455.50 5,160 34.8
n035w4_2_9-2-2-6 1080 1080 294 294 0 1,595 1,803 47.7 1,525 6,204 41.2 1,577 1,317 46.0 1,696.50 5,160 57.1
n035w4_2_9-7-2-2 1080 1080 291 291 0 1,550 1,803 43.5 1,480 12,340 37.0 1,539 1,317 42.5 1,624.00 5,160 50.4
n035w4_2_9-9-2-1 1080 1080 284 284 0 1,540 1,803 42.6 1509 1,317 39.7 1,651.50 5,160 52.9
staff=70 n070w4_0_3-6-5-1 2380 2380 35125 480 0 2,430 3,206 2.1 2,460 3,640 3 2,455.00 2,342 3 2,842.50 5,160 19.4
n070w4_0_4-9-6-7 2115 2115 593 593 0 2,125 3,206 0.5 2,330 4,943 10.2 2,190.00 2,342 3.5 2,535.50 5,160 19.9
n070w4_0_4-9-7-6 2140 2140 914 914 0 2,210 3,206 3.3 2,315 9,465 8.2 2,229.00 2,342 4.2 2,587.00 5,160 20.9
n070w4_0_8-6-0-8 2285 2285 10433 659 0 2,320 3,206 1.5 2,400 1,795 5.0 2,345.50 2,342 2.6 2,668.50 5,160 16.8
n070w4_0_9-1-7-5 2080 2080 425 425 0 2,100 2,342 1.0 2,225 3,395 7.0 2,147.00 2,342 3.2 2,448.30 5,160 17.7
n070w4_1_1-3-8-8 2080 2080 425 425 0 2,530 2,342 21.6 2,615 3,457 25.7 2,582.50 2,342 24.2 2,915.40 5,160 40.2
n070w4_2_0-5-6-8 2270 2280 4665 4665 0 2,360 3,206 4.0 2,415 2,990 6.4 2,365.00 2,342 4.2 2,688.40 5,160 18.4
n070w4_2_3-5-8-2 2325 2335 525 525 0 2,380 2,342 2.4 2,405 5,032 3.4 2,424.50 2,342 4.3 2,690.00 5,160 15.7
n070w4_2_5-8-2-5 2290 2295 513 513 0 2,345 3,206 2.4 2,390 7,580 4.4 2,366.50 2,342 3.3 2,653.40 5,160 15.9
n070w4_2_9-5-6-5 2355 2365 426 426 0 2,465 3,206 4.7 2,480 2,495 5.3 2,416.00 2,342 2.6 2,764.50 5,160 17.4
staff=110 n110w4_0_1-4-2-8 2330 2330 25537 760 0 2,390 4,809 2.6 2,560 13,084 9.9 2,387.50 3,513 2.5 3,020.00 5,160 29.6
n110w4_0_1-9-3-5 2455 2455 402 402 0 2,525 4,809 2.9 2,640 9,624 7.5 2,566.50 3,513 4.5 3,205.50 5,160 30.6
n110w4_1_0-1-6-4 2530 2530(2785) 305 305 0 2,680 4,809 5.9 2,690 24,585 6.3 2,609.00 3,513 3.1 3,241.00 5,160 28.1
n110w4_1_0-5-8-8 2470 2475 415 0.2 2,625 4,809 6.3 2,705 12,838 9.5 2,596.00 3,513 5.1 3,254.00 5,160 31.7
n110w4_1_2-9-2-0 2870 2875 1641 0 2,975 3,513 3.7 3,170 11,570 10.5 3,032.00 3,513 5.6 3,646.00 5,160 27.0
n110w4_1_4-8-7-2 2430 2430 4740 2147 0 2,570 4,809 5.8 2,630 8,350 8.2 2,545.50 3,513 4.8 3,217.50 5,160 32.4
n110w4_2_0-2-7-0 2640 2640 7212 2193 0 2,780 4,809 5.3 2,960 10,882 12.1 2,763.50 3,513 4.7 3,388.50 5,160 28.4
n110w4_2_5-1-3-0 2640 2640 604 604 0 2,700 4,809 2.3 2,770 9,079 4.9 2,719.00 3,513 3.0 3,285.50 5,160 24.5
n110w4_2_8-9-9-2 2855 2860 4454 0.2 2,980 3,513 4.4 3,140 15,184 10.0 3,049.00 3,513 6.8 3,720.90 5,160 30.3
n110w4_2_9-8-4-9 2695 2700 1274 0.2 2,775 3,513 3.0 3,005 11,311 11.5 2,834.00 3,513 5.2 3,449.00 5,160 28.0

Monday, May 2, 2022

なぜOR-TOOLSのオープンソース化は遅れているか?

 https://or.stackexchange.com/questions/7526/why-is-open-source-operations-research-software-so-far-behind-open-source-statis

Machine Learningの世界では、TensorFlow や PyTorch のように優れたソフトがオープンソース化されているのに、OR toolsでは、そうなっていないのはどうして? という質問です。CLPやHighs,CBCは、商用ツールと比べると大分見劣りする.. 

確かに、そうなのですが、一つの理由として何十年という歴史の違いが述べられています。また一方で、アルゴリズムそのものが製品の命であるということ、Googleがデータを売っていないことのアナロジーについても述べられていて興味深いです。


Sunday, May 1, 2022

JAPIO-AIとDEEPL

 JAPIO-AIを試用しています。Excelで訳文を出してくれます。なるほど、こういう風に訳出すると、とても見易いです。

それをDEEPLに通すと、驚くほど、元の日本語に戻ります。元の日本語を知っていたのでは?と思う位のときもあります。でも、それをGrammerlyに通すと、結構直されます。不思議なことに直される前の方が、元の日本語に戻る確率が高いです。ということは、私の日本語自身が曖昧ということであってJAPIO-AIはそれを忠実に訳しているだけ、という見方も出来ます。

相変わらずPASSIVEの指摘が多いですが、それを除くと多分全うな指摘です。ちなみに、PASSIVE VOICE指摘の文章を

This sentence appears to be written in the passive voice 

をGrammerlyに通すとPassive Voiceの指摘が出るのは、ご愛嬌でしょう。

JAPIO-AIは良い雰囲気ですが、同じ名称でも異なる単語に訳出されることが多いです。多分、用語定義すれば、大分良くなると思います。また、時々誤訳も見かけます。が、DEEPLで逆翻訳すれば、簡単に発見できます。DEEPL上で⇔修正しながら確認し、最後にGrammerlyでチェック、Passiveは無視、というフローが良いように思います。完全自動化は無理にしても、用語定義すればかなり使える印象です。良い時代になりました。


Friday, April 29, 2022

新しいINRC2論文

 Mathematical Models and a Late Acceptance Fix-and-Optimize Approach for a Nurse Rostering Problem (ufrgs.br)

ブラジルの大学修士論文のようです。INRC2でMIPソルバが振るわないのは、どの制約か効いているか?という問いに対して minimum_consecutive.. という答えのようです。

この辺の指摘は、Pieter Smetさんも行っていて、ソフトパターン制約が大きいことが分かっています。

ところで、結果の方で気になるのですが、私に対する言及がないのは、極めて残念です。

「Cplexで24hRUNしても最適解が求まらない」とされていますが、スケジュールナースⅢでは、言及している少なくともショートインスタンスでは、数十分以内に厳密解が求まるものが多い・大半?です。そこで、論文中でテストしているインスタンスの厳密解を提示したいと思います。合わせて、INRC2インスタンスの走らせ方についても公開したいと思います。(実はGUIからテスト可能ですが、現在はコンパイルオプションです。)

ナーススケジューリングの研究者は、ほぼいなくなってしまったのですが、海外では修士・博士論文の格好の餌食になっていて時折目にします。厳密解があれば、メタヒューリスティクスの開発にも寄与するでしょう。

準備ができましたならアナウンスします。