数理ソルバ的解法で問題となる現象で、対称性が求解スピードを悪化させたり、最悪の場合、誤収束してしまうことがあります。NSPの場合、無縁だと思っていたのですが、実は、結構な頻度で、その現象が観測されることが分かりました。
具体的には、
（A)ハード予定制約が全くないインスタンス
（B)結構ハード予定制約が詰まったインスタンス
をの求解速度を比較してみます。Algorithm1の場合は、Bが速くなることは殆どありません。このことは、探索空間の減少より解空間の減少が大きいことが原因と考えています。
しかし、Algorithm3の場合、Bの方が速くなることが結構あります。（ただし、Version１５２から、Algorithm3のStabilization方法を変えているので、目だった差にはなりません。）
同じテストインスタンスなのに挙動が反対になるReasonableな説明としては、Symmetry Breakingによる補償効果があったのではないかと思います。
（１） 「振替休暇」が「PM業務」日に自動割り当てされることがある。
バグです。これを防ぐには、次のよう変更します。
変更前
変更後
業務シフトで、チェックがされていないフェーズのタスクは、どのようなタスクもアクティブにはなりません。つまり、振り替え休日が設定されることはありません。チェックされているフェーズのみが有効フェーズとして働きます。
また記述されていないシフトは、チェックなし、と解されます。
なお、入力は可能ですが、次のバージョンより入力すべきではないタスクには、シフトの背景色が付くのですぐ気づくと思われます。（解も同様です。）
上のようなシフト入力の場合に、タスク入力は、下のようになります。
解も、背景シフト色で埋められます。
それでも、入力した場合は、タスクの入力は無視されてシフトが生かされた解となります。Python記述を追加して、エラー入力を検出することも可能ですし、また、ハード制約として求解できないようにすることも可能ですが、とりあえずは、上記実装で運用してみていただきたいと思います。
（２）有給休暇「有」と、休暇「休」が「当禁」「遅禁」に入力できない
これは、設計通りで、そのように意図していました。入力可能なように変更するには、（１）の通りとしてください。
（３） 平日の夜禁止はどのようにするのか
既に、夜勤禁として記述済みです。
なお、下のように記述しても、OKです。（意味は同じというよりも完全に同じものを指しています。）
（４） スタッフ定義のスタッフ名 変更したら予定が消失
スタッフプロパティのスタッフ名を変更すると紐づいているデータが
画面から消失するのはわかるのですが、残す方法はないでしょうか？
少し面倒ですが手は二つあります。
一つ目の方法は、ファイルとして保存（CSV）として保存します。CSVファイルはプロジェクトフォルダに出力されます。それをExcelで開いて必要部分をコピペします。
二つ目の方法は、スケジュールナースをもう一つ立ち上げて、同じプロジェクトを読みます。片方は名前を変更します。変更していないもう一つのスケジュールナースから、コピペします。
質問その１）列制約にタブが２つあるのはどのような使い道でしょうか。
単にグループ毎の制約のオンオフを行う、等の管理上の便宜を意図していますが、今回の場合、単に開発時の足跡で意味はありません。
質問その２）求解のソルバ設定 CPU数 はいくつが適当でしょうか。また、アルゴリズムは選択できるようですが、 １，３のどちらがよろしいでしょうか？
前回のブログをご参照ください。
Q.１と３が選択できるようになっていますが、どちらを使用すればよいでしょうか？
明確に目的と用途が異なります。
＜制約設計時＞
Algorithm1を使用して下さい。制約設計時は、デバッグツールとして、解がない場合の原因解析が必須となります。原因解析が効くのは、Algorithm1のみです。
＜普段の求解時＞
多くの場合、Algorithm1が最も速く、かつ安定に動作します。
ーCPU数
１で良いです。２以上でも動作しますが、さして変わりません。
＜厳密解を求めたい場合＞
Algorithm1は、原則的にNear Optimal解を出力します。目的関数値(UB)が０の場合は、Optimalです。時間がかかって、UBが０でない場合は、厳密解ではない可能性があります。特に、多くのエラーがある場合は、もう少し良い値が存在するかもしれません。そのような場合で、厳密解（物理的な限界値）を求めたい場合の選択肢としては、Algorithm２,３,４があります。公式サポートは、１，３のみですが、2,4も設定すると動きます。
アカデミックなベンチマークではこの厳密解に達するまでの時間を指標としていることもあり、スケジュールナースⅢのベンチマークデータは全てAlgorithm3を使用しています。タイムアウトはなく、厳密解を見つけるまで動作し続けます。従って、Algorithm1よりも悪い値で終了することはありません。また、Algorithm１の出力値と比較して、Algorithm1が厳密解目的関数値もしくは、極めて近い値を出力していることも確認できると思います。（途中で求解を止めるには中止ボタンを押してください。）
＜Algorithm3＞
推奨環境：32GB以上のメモリ、CPUコア数8以上の最新のプロセッサ。（全CPUパワーをフルスレッドで使います。）
ほぼ全てのインスタンスで動作しますが、Algorithm1で動作確認した上で御使用ください。
ー威力を発揮する場面
Algorithm1では、時間がかかるとき（特に多くのハード予定またはソフト制約が詰まっている）に有効です。また、LB値（この値に到達する保証はないが、目的関数値でこれ以上より良い値になることも絶対にない）を知りたい場面でも有効です。
ー動かないインスタンス
一部、フェーズ変数を用いた複雑な制約については、動かないものがあることが分かっています。
＜Algorithm2＞
オープンソース MIPソルバHiGHSによる解法になります。小さいインスタンス（スタッフ数10人程度）ならば、動く可能性がありますが、中規模以上では時間がかかり、求まらない可能性が高いです。
<Algorithm4>
Algorithm3は、Algorithm4と１の合体です。インスタンスによってAlgorithm1を走らせる場合がありますが、Algorithm4は、このフェーズがありません。
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 | ||
Machine Learningの世界では、TensorFlow や PyTorch のように優れたソフトがオープンソース化されているのに、OR toolsでは、そうなっていないのはどうして？ という質問です。CLPやHighs,CBCは、商用ツールと比べると大分見劣りする..
確かに、そうなのですが、一つの理由として何十年という歴史の違いが述べられています。また一方で、アルゴリズムそのものが製品の命であるということ、Googleがデータを売っていないことのアナロジーについても述べられていて興味深いです。
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は無視、というフローが良いように思います。完全自動化は無理にしても、用語定義すればかなり使える印象です。良い時代になりました。
ブラジルの大学修士論文のようです。INRC2でMIPソルバが振るわないのは、どの制約か効いているか？という問いに対して minimum_consecutive.. という答えのようです。
この辺の指摘は、Pieter Smetさんも行っていて、ソフトパターン制約が大きいことが分かっています。
ところで、結果の方で気になるのですが、私に対する言及がないのは、極めて残念です。
「Cplexで24hRUNしても最適解が求まらない」とされていますが、スケジュールナースⅢでは、言及している少なくともショートインスタンスでは、数十分以内に厳密解が求まるものが多い・大半？です。そこで、論文中でテストしているインスタンスの厳密解を提示したいと思います。合わせて、INRC2インスタンスの走らせ方についても公開したいと思います。（実はGUIからテスト可能ですが、現在はコンパイルオプションです。）
ナーススケジューリングの研究者は、ほぼいなくなってしまったのですが、海外では修士・博士論文の格好の餌食になっていて時折目にします。厳密解があれば、メタヒューリスティクスの開発にも寄与するでしょう。
準備ができましたならアナウンスします。
