OpenMP Task Support for C++ in Visual Studio - C++ Team Blog (microsoft.com)
インテル® Cilk™ Plus アプリケーションを OpenMP* もしくはインテル® TBB へ移行する | iSUS
LLVMのみのようですが、なにが嬉しいかというとNativeにtaskが記述可能になり、TBBを使わなくてもよくなるということです。Barrier Solverのマルチスレッド性能が少しだけ向上するのではないかと期待しています。まだ、Schedule NurseⅢは、VisualStudio2019ベースですので、機会を見て移行しようと思います。
Windowsペイント等で白黒化すると、文字が判読不能な状態になることがあります。
ずっと悩んでいたのですが、以下のサイトで、グレースケール、2色、明るさ調整で、上手く出来ました。
画像や写真を白黒・モノクロ（グレースケール）にする : オンラインイメージエディタ | 無料で画像を加工できるサイト PEKO STEP (peko-step.com)
未だ、解かれていないNSP問題は、
INRC2 8Weeks：殆ど全問題
Scheduling Benchmarks： Instance15,Instance23,Instance24
です。これらの問題が全て解けたら（厳密解が求まったら）ここ数十年来、提出されたNSPベンチマークは、全て解けたことになります。（ただし、ここ2年位、新解の提出は私だけになってしまいました。）そうすると、未解決の問題はなくなり、解が求まらないことが一般的なイメージが、時間をかければ解けるはずという具合にパラダイムがシフトするかもしれません。全部解いたら、まとめて、その方法を発表しようと思います。共著者募集中です。
内容は、 タスクビューの改善とAlgorithm3のSpeedUp改善です。
インスタンスにもよりますが、BCDT－SEPでみると、厳密解Provenまで以前140secかかっていたのが70sec程度になっていました。
04_toukei01.dvi (ism.ac.jp)を読むと、MIPソルバは、極めて大規模なソフトウェアであることが分かります。
”Gurobi は設計の当初から並列実行を前提に設計された” なるほど。
Algorithm3も、当初からマルチコアを前提に設計されています。コア数が多くなればなるほど、高速になるように設計しています。
”商用ソルバで解けないインスタンスを商用ソルバより先に解いたケースは.."については、NSPの場合、沢山あります。
加えて、NSPの場合、長くても数分内に解が欲しいのですが、その時間で判定してしまうと本来Feasibleのはずが、MIPソルバだと、Infeasibleになってしまう例が、沢山あります。
NSPならば、安定的に、一分以内にFeasible解、2-3分内に実用的な解(Near Optimal)、数十分内にOptimality Provenな解を示すことが目標です。こういった指標で、スケジュールナースⅢが世界のトップであることは疑いないと思っています。
数理ソルバ的解法で問題となる現象で、対称性が求解スピードを悪化させたり、最悪の場合、誤収束してしまうことがあります。NSPの場合、無縁だと思っていたのですが、実は、結構な頻度で、その現象が観測されることが分かりました。
具体的には、
（A)ハード予定制約が全くないインスタンス
（B)結構ハード予定制約が詰まったインスタンス
をの求解速度を比較してみます。Algorithm1の場合は、Bが速くなることは殆どありません。このことは、探索空間の減少より解空間の減少が大きいことが原因と考えています。
しかし、Algorithm3の場合、Bの方が速くなることが結構あります。（ただし、Version１５２から、Algorithm3のStabilization方法を変えているので、目だった差にはなりません。）
同じテストインスタンスなのに挙動が反対になるReasonableな説明としては、Symmetry Breakingによる補償効果があったのではないかと思います。
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は無視、というフローが良いように思います。完全自動化は無理にしても、用語定義すればかなり使える印象です。良い時代になりました。
