日本で先進的な研究成果を上げているプロジェクトがあります。このプロジェクトもその一つで日本語での論文やチュートリアル解説等で、私に与えた影響は大きく、大変勉強になっています。その中の中核メンバーの番原先生が名古屋大に移られたようです。
野々部先生の新しい論文が興味深いです。これは読まないと。
2018年11月7日水曜日
2018年11月3日土曜日
NEOS ServerでCPLEXデータを採取
NEOS SERVERは、フリーで利用できるサーバです。説明は、こちらが詳しいかと。
私自身は、RAMP発表のときにCPLEXとの比較データを作るのに使いました。CPLEXを走らせるには、MPSファイルという、パンチカードの時代のフォーマットではないかと思いますが、そのファイルを生成しています。
SAT/MAXSATから、変換するツールもなくはない(例えば、こちら）のですが、基数制約（足し算の制約で、例えば、Σai*vi>=LB）をCNF上で展開すると、その性質上CPLEXに不利にしか働かないので、直接MPSファイル生成を行っています。（その機能は、実は現SCNURSEにもありますが公開していません。）
で、CPLEXとの比較の話ですが、インスタンスによって全然違います。私から見て、「これは難しそうだ」 というインスタンスがCPLEXではあっさり解けたり、あるいは、その逆もまたあります。
下は、CPLEXでのNEOSサーバログ例です。
インスタンスは、軽めの2交代です。（スーパ救急）
ヘビーユーザさんの超重いインスタンスで本当は比較したいのですが、MPSファイル16MBという制限があり、走らせることができません。
Shord Periodで起動しているので、5分-6分で打ち切られます。メールアドレスを記しておくとログが
送られてきます。
目的関数値63から始まって、徐々に下げている様子が分かります。スレッド数は４のようです。
コンパイルの準備中ソルバを呼び出し中です。
解探索を開始します。0.626(CPU秒)
穴を埋めると作業といいますか、どのようなインスタンスでもStateOfArtの性能に近いソルバーが理想な訳です。
そのための第2エンジンの開発です。
現行のScNurseが、どこが強くてどこが弱そうかという話はRAMP講演でした通りですが、
その辺が、第2エンジンを付加することでどのようになるのか、これから検証していきます。
が、未だ全てのインスタンスが走らせることが出来ていません。特に池上先生のインスタンスは数理的には非常に困難なインスタンスです。
ある意味究極のモデリング方法を採っていると言ってよいかと思います。スケジューリングサイトのベンチマーク問題とは対照的に、
非常に汎用的な記述になっています。池上先生にお聞きしたことがあるのですが、欧米のシフトと日本のシフトで違いはあるか？という問いに対して、同じという風におっしゃていました。
確かに、これほど汎用的なモデリングが可能ならどのようなシフト形態も記述可能でしょう。
もう一つ特筆すべきは、この解数は、一つや二つではなく、恐らく何百万もあるということです。CPLEXで最適解を発見するのに10-15分かかかるのですが、
一度発見すると、あれよあれよという間に解の個数は増え、一ヶ月回しても未だ止まらない、という解の出方なんだそうです。
その事自体が、学会でも新鮮な驚きだったようです。宇宙は思ったより広いということでしょうか？
池上先生のベンチマークは、看護師長がつくった制約を丹念にモデリング化したリアルプロジェクトです。人間がつくった制約になります。
ところが、Competitionや公開されているベンチマークは、ある確率空間モデルで生成された計算機が生み出した制約です。特に、スケジューリングサイトの解の個数は、非常に少ないということは、
分かっています。これにより得意不得意の分野が分かれるのがお分かりでしょう。解の個数/探索空間が重要なファクタになっていると思います。
私自身は、RAMP発表のときにCPLEXとの比較データを作るのに使いました。CPLEXを走らせるには、MPSファイルという、パンチカードの時代のフォーマットではないかと思いますが、そのファイルを生成しています。
SAT/MAXSATから、変換するツールもなくはない(例えば、こちら）のですが、基数制約（足し算の制約で、例えば、Σai*vi>=LB）をCNF上で展開すると、その性質上CPLEXに不利にしか働かないので、直接MPSファイル生成を行っています。（その機能は、実は現SCNURSEにもありますが公開していません。）
で、CPLEXとの比較の話ですが、インスタンスによって全然違います。私から見て、「これは難しそうだ」 というインスタンスがCPLEXではあっさり解けたり、あるいは、その逆もまたあります。
下は、CPLEXでのNEOSサーバログ例です。
インスタンスは、軽めの2交代です。（スーパ救急）
ヘビーユーザさんの超重いインスタンスで本当は比較したいのですが、MPSファイル16MBという制限があり、走らせることができません。
Shord Periodで起動しているので、5分-6分で打ち切られます。メールアドレスを記しておくとログが
送られてきます。
目的関数値63から始まって、徐々に下げている様子が分かります。スレッド数は４のようです。
*************************************************************
NEOS Server Version 5.0
Job# : 6374879
Password : AXqnFhrD
User : None
Solver : lp:CPLEX:MPS
Start : 2018-11-02 22:55:18
End : 2018-11-02 23:05:27
Host : NEOS HTCondor Pool
Disclaimer:
This information is provided without any express or
implied warranty. In particular, there is no warranty
of any kind concerning the fitness of this
information for any particular purpose.
*************************************************************
Executing on prod-exec-5.neos-server.org
Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.7.0.0
with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2016. All Rights Reserved.
Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.
CPLEX> New value for default parallel thread count: 4
CPLEX> Selected objective sense: MINIMIZE
Selected objective name: OBJROW
Selected RHS name: RHS
Selected bound name: BOUND
Problem 'cplex.mps' read.
Read time = 0.05 sec. (7.24 ticks)
CPLEX> Tried aggregator 2 times.
MIP Presolve eliminated 24438 rows and 3360 columns.
MIP Presolve modified 3630 coefficients.
Aggregator did 6244 substitutions.
Reduced MIP has 11719 rows, 7404 columns, and 53687 nonzeros.
Reduced MIP has 7404 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.14 sec. (92.27 ticks)
Probing time = 0.02 sec. (4.62 ticks)
Cover probing fixed 180 vars, tightened 0 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 2585 rows and 270 columns.
Aggregator did 110 substitutions.
Reduced MIP has 9024 rows, 7024 columns, and 41794 nonzeros.
Reduced MIP has 7024 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.07 sec. (45.62 ticks)
Probing time = 0.01 sec. (4.09 ticks)
Clique table members: 24668.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.49 sec. (336.48 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 0.0000 3710 0.0000 0
* 0+ 0 63.0000 0.0000 100.00%
0 0 0.0000 2504 63.0000 Cuts: 68 6241 100.00%
0 0 0.0000 2519 63.0000 Cuts: 33 13701 100.00%
0 0 0.0000 2523 63.0000 Cuts: 40 21054 100.00%
* 0+ 0 62.0000 0.0000 100.00%
* 0+ 0 57.0000 0.0000 100.00%
0 2 0.0000 2111 57.0000 0.0000 21054 100.00%
Elapsed time = 51.90 sec. (36012.51 ticks, tree = 0.01 MB, solutions = 3)
1 3 0.0000 2498 57.0000 0.0000 35121 100.00%
2 4 0.0000 2592 57.0000 0.0000 42079 100.00%
3 3 0.0000 2471 57.0000 0.0000 35331 100.00%
4 5 0.0000 2691 57.0000 0.0000 48497 100.00%
5 7 0.0000 2817 57.0000 0.0000 65490 100.00%
7 4 0.0000 2647 57.0000 0.0000 43682 100.00%
8 9 0.0000 3312 57.0000 0.0000 67314 100.00%
10 11 0.0000 2851 57.0000 0.0000 67943 100.00%
12 13 0.0000 2960 57.0000 0.0000 68865 100.00%
22 18 0.0000 2950 57.0000 0.0000 72647 100.00%
Elapsed time = 72.21 sec. (50651.13 ticks, tree = 0.01 MB, solutions = 3)
35 25 0.0000 2868 57.0000 0.0000 75956 100.00%
46 11 0.0000 3260 57.0000 0.0000 95067 100.00%
50 14 0.0000 3177 57.0000 0.0000 96943 100.00%
59 18 0.0000 3241 57.0000 0.0000 88485 100.00%
70 42 -0.0000 2791 57.0000 0.0000 109799 100.00%
84 61 0.0000 3073 57.0000 0.0000 130374 100.00%
94 71 0.0000 2875 57.0000 0.0000 134592 100.00%
104 95 0.0000 3158 57.0000 0.0000 156357 100.00%
121 90 0.0000 3250 57.0000 0.0000 147741 100.00%
137 109 -0.0000 2791 57.0000 0.0000 164857 100.00%
Elapsed time = 86.17 sec. (61421.47 ticks, tree = 0.17 MB, solutions = 3)
158 138 0.0000 2861 57.0000 0.0000 180398 100.00%
177 153 0.0000 2776 57.0000 0.0000 188296 100.00%
198 149 0.0000 2843 57.0000 0.0000 185441 100.00%
213 205 -0.0000 2695 57.0000 0.0000 214345 100.00%
225 198 0.0000 2749 57.0000 0.0000 212004 100.00%
238 214 0.0000 2557 57.0000 0.0000 220041 100.00%
246 220 0.0000 2483 57.0000 0.0000 223199 100.00%
251 244 0.0000 2441 57.0000 0.0000 233541 100.00%
256 249 0.0000 1971 57.0000 0.0000 237713 100.00%
266 248 0.0000 2801 57.0000 0.0000 234652 100.00%
Elapsed time = 100.44 sec. (71571.10 ticks, tree = 2.09 MB, solutions = 3)
281 269 0.0000 1764 57.0000 0.0000 248351 100.00%
297 261 -0.0000 2779 57.0000 0.0000 240850 100.00%
305 265 0.0000 2720 57.0000 0.0000 245582 100.00%
317 289 0.0000 2747 57.0000 0.0000 257934 100.00%
334 295 0.0000 2710 57.0000 0.0000 260413 100.00%
351 305 0.0000 2640 57.0000 0.0000 264267 100.00%
357 311 0.0000 2644 57.0000 0.0000 267426 100.00%
365 327 0.0000 2665 57.0000 0.0000 274389 100.00%
389 332 0.0000 2596 57.0000 0.0000 277430 100.00%
410 347 0.0000 2640 57.0000 0.0000 284219 100.00%
Elapsed time = 115.92 sec. (82068.18 ticks, tree = 4.05 MB, solutions = 3)
441 353 0.0000 2678 57.0000 0.0000 287216 100.00%
472 389 2.0000 1430 57.0000 0.0000 308337 100.00%
498 465 2.0000 1419 57.0000 0.0000 349952 100.00%
521 438 0.0000 2437 57.0000 0.0000 330820 100.00%
545 505 -0.0000 1619 57.0000 0.0000 366673 100.00%
573 452 -0.0000 2419 57.0000 0.0000 336334 100.00%
598 533 0.0000 1660 57.0000 0.0000 383628 100.00%
620 544 0.0000 1512 57.0000 0.0000 389020 100.00%
650 594 0.0000 2054 57.0000 0.0000 427826 100.00%
682 621 0.0000 1437 57.0000 0.0000 458065 100.00%
Elapsed time = 133.21 sec. (91876.24 ticks, tree = 7.60 MB, solutions = 3)
717 610 -0.0000 1771 57.0000 0.0000 435109 100.00%
751 686 0.0000 1666 57.0000 0.0000 484184 100.00%
789 740 0.0000 1230 57.0000 0.0000 540359 100.00%
814 745 0.5000 1316 57.0000 0.0000 547075 100.00%
841 749 0.0000 1213 57.0000 0.0000 553594 100.00%
871 835 5.0000 1277 57.0000 0.0000 604783 100.00%
900 782 1.0000 1036 57.0000 0.0000 581817 100.00%
928 858 0.0000 1184 57.0000 0.0000 640764 100.00%
942 860 0.0000 1408 57.0000 0.0000 647897 100.00%
968 868 0.0000 1427 57.0000 0.0000 655572 100.00%
Elapsed time = 151.46 sec. (101703.04 ticks, tree = 12.84 MB, solutions = 3)
996 928 0.0000 1466 57.0000 0.0000 716821 100.00%
1032 926 1.6556 1210 57.0000 0.0000 703682 100.00%
1072 965 6.5000 1116 57.0000 0.0000 738094 100.00%
1104 1024 2.2222 1133 57.0000 0.0000 777349 100.00%
1139 1052 0.1875 1550 57.0000 0.0000 805000 100.00%
1176 1069 4.0000 965 57.0000 0.0000 806816 100.00%
1214 1103 9.6724 1213 57.0000 0.0000 840457 100.00%
1249 1179 5.5185 1034 57.0000 0.0000 896645 100.00%
1275 1135 5.2727 1327 57.0000 0.0000 880917 100.00%
* 1285+ 1242 48.0000 0.0000 100.00%
1289 1286 0.0000 1321 48.0000 0.0000 981106 100.00%
Elapsed time = 170.50 sec. (111445.72 ticks, tree = 19.23 MB, solutions = 5)
* 1303+ 1183 38.0000 0.0000 100.00%
1304 1292 6.6250 896 38.0000 0.0000 989818 100.00%
* 1313+ 1183 37.0000 0.0000 100.00%
1330 1307 7.0000 854 37.0000 0.0000 997594 100.00%
1355 1322 7.0000 962 37.0000 0.0000 1004177 100.00%
* 1364+ 908 35.0000 0.0000 100.00%
* 1364+ 605 30.0000 0.0000 100.00%
* 1364+ 402 24.0000 0.0000 100.00%
1364 403 0.0000 2313 24.0000 0.0000 1121975 100.00%
1367 405 0.0000 2429 24.0000 0.0000 1123681 100.00%
1373 408 -0.0000 2584 24.0000 0.0000 1125307 100.00%
1378 410 -0.0000 2627 24.0000 0.0000 1126943 100.00%
1393 32 0.0000 2220 24.0000 0.0000 1130232 100.00%
1416 51 -0.0000 2755 24.0000 0.0000 1136750 100.00%
1446 73 0.0000 2746 24.0000 0.0000 1142983 100.00%
Elapsed time = 349.35 sec. (230446.01 ticks, tree = 0.10 MB, solutions = 10)
1485 99 -0.0000 2636 24.0000 0.0000 1149392 100.00%
1524 128 -0.0000 2503 24.0000 0.0000 1156073 100.00%
1563 182 0.0000 1845 24.0000 0.0000 1170958 100.00%
1586 196 -0.0000 1585 24.0000 0.0000 1176280 100.00%
1609 224 0.0000 1811 24.0000 0.0000 1181029 100.00%
1628 249 -0.0000 1636 24.0000 0.0000 1188160 100.00%
1647 238 0.0000 1758 24.0000 0.0000 1185442 100.00%
1680 283 0.0000 1696 24.0000 0.0000 1198634 100.00%
1711 304 -0.0000 1314 24.0000 0.0000 1204282 100.00%
1739 352 0.0000 1308 24.0000 0.0000 1219717 100.00%
Elapsed time = 363.61 sec. (240319.46 ticks, tree = 1.03 MB, solutions = 10)
1773 305 0.0000 2590 24.0000 0.0000 1204246 100.00%
1812 396 1.0000 1391 24.0000 0.0000 1234825 100.00%
1844 429 0.0000 1615 24.0000 0.0000 1243729 100.00%
1876 439 -0.0000 2593 24.0000 0.0000 1245060 100.00%
1902 497 1.0000 1735 24.0000 0.0000 1265429 100.00%
1930 521 1.0000 1386 24.0000 0.0000 1275594 100.00%
1971 581 -0.0000 2529 24.0000 0.0000 1294029 100.00%
2002 589 0.0000 2183 24.0000 0.0000 1296354 100.00%
2032 636 3.0000 1492 24.0000 0.0000 1312695 100.00%
2156 759 2.0000 1665 24.0000 0.0000 1359694 100.00%
Elapsed time = 382.78 sec. (252909.19 ticks, tree = 2.94 MB, solutions = 10)
2340 905 9.0000 1026 24.0000 0.0000 1412808 100.00%
2496 1046 2.8000 1635 24.0000 0.0000 1454883 100.00%
* 2648+ 918 22.0000 0.0000 100.00%
* 2666+ 918 19.0000 0.0000 100.00%
2675 1253 8.0000 1169 19.0000 0.0000 1515240 100.00%
27
ERROR: Your job was terminated because it exceeded the maximum allotted time for a job.
Please refer to the NEOS Server FAQ (https://neos-guide.org/content/FAQ) for more information regarding job termination conditions.
382秒以降に、目的関数値19を記録しています。(ちなみに昨年計測したときは、25でした。)
同じインスタンスを現行ScNurseで解かせた様子が、以下です。
45秒で最適解に到達し、最適解の証明に210秒かかっています。
コンパイルの準備中ソルバを呼び出し中です。
解探索を開始します。0.626(CPU秒)
Soft Constraint Row2
o=44 Time=3.517(CPU秒)
o=43 Time=5.221(CPU秒)
o=42 Time=5.251(CPU秒)
o=41 Time=5.291(CPU秒)
o=40 Time=5.380(CPU秒)
o=39 Time=5.435(CPU秒)
o=38 Time=6.661(CPU秒)
o=37 Time=7.328(CPU秒)
o=36 Time=8.091(CPU秒)
o=35 Time=8.274(CPU秒)
o=34 Time=8.319(CPU秒)
o=33 Time=8.719(CPU秒)
o=32 Time=8.780(CPU秒)
o=31 Time=9.570(CPU秒)
o=30 Time=10.249(CPU秒)
o=29 Time=10.458(CPU秒)
o=28 Time=11.530(CPU秒)
o=27 Time=11.861(CPU秒)
o=26 Time=12.806(CPU秒)
o=25 Time=13.280(CPU秒)
o=24 Time=13.323(CPU秒)
o=23 Time=13.374(CPU秒)
o=22 Time=15.202(CPU秒)
o=21 Time=15.828(CPU秒)
o=20 Time=15.872(CPU秒)
o=19 Time=17.112(CPU秒)
o=18 Time=17.155(CPU秒)
o=17 Time=19.845(CPU秒)
o=16 Time=20.198(CPU秒)
o=15 Time=23.251(CPU秒)
o=14 Time=25.785(CPU秒)
o=13 Time=26.337(CPU秒)
o=12 Time=26.400(CPU秒)
o=11 Time=26.451(CPU秒)
o=10 Time=26.529(CPU秒)
o=9 Time=30.737(CPU秒)
o=8 Time=34.266(CPU秒)
o=7 Time=36.242(CPU秒)
o=6 Time=37.967(CPU秒)
o=5 Time=40.058(CPU秒)
o=4 Time=45.633(CPU秒)
f=3 Time=210.848(CPU秒)
Optimum ConUB found
o=4 Time=211.067(CPU秒)
o=4 Time=211.084(CPU秒)
b=4 Time=211.087(CPU秒)
充足解を書き込み中です。C:\Users\sugaw\Documents\Visual Studio 2015\Projects\schedule_nurse_ver2\WindowsFormsApplication1\test\sim_engine32\solution1.txt 211.091(CPU秒)
充足解を書き込みました。C:\Users\sugaw\Documents\Visual Studio 2015\Projects\schedule_nurse_ver2\WindowsFormsApplication1\test\sim_engine32\solution1.txt 211.102(CPU秒)
解探索が終了しました。 211 (秒)
解が得られました。
o=44 Time=3.517(CPU秒)
o=43 Time=5.221(CPU秒)
o=42 Time=5.251(CPU秒)
o=41 Time=5.291(CPU秒)
o=40 Time=5.380(CPU秒)
o=39 Time=5.435(CPU秒)
o=38 Time=6.661(CPU秒)
o=37 Time=7.328(CPU秒)
o=36 Time=8.091(CPU秒)
o=35 Time=8.274(CPU秒)
o=34 Time=8.319(CPU秒)
o=33 Time=8.719(CPU秒)
o=32 Time=8.780(CPU秒)
o=31 Time=9.570(CPU秒)
o=30 Time=10.249(CPU秒)
o=29 Time=10.458(CPU秒)
o=28 Time=11.530(CPU秒)
o=27 Time=11.861(CPU秒)
o=26 Time=12.806(CPU秒)
o=25 Time=13.280(CPU秒)
o=24 Time=13.323(CPU秒)
o=23 Time=13.374(CPU秒)
o=22 Time=15.202(CPU秒)
o=21 Time=15.828(CPU秒)
o=20 Time=15.872(CPU秒)
o=19 Time=17.112(CPU秒)
o=18 Time=17.155(CPU秒)
o=17 Time=19.845(CPU秒)
o=16 Time=20.198(CPU秒)
o=15 Time=23.251(CPU秒)
o=14 Time=25.785(CPU秒)
o=13 Time=26.337(CPU秒)
o=12 Time=26.400(CPU秒)
o=11 Time=26.451(CPU秒)
o=10 Time=26.529(CPU秒)
o=9 Time=30.737(CPU秒)
o=8 Time=34.266(CPU秒)
o=7 Time=36.242(CPU秒)
o=6 Time=37.967(CPU秒)
o=5 Time=40.058(CPU秒)
o=4 Time=45.633(CPU秒)
f=3 Time=210.848(CPU秒)
Optimum ConUB found
o=4 Time=211.067(CPU秒)
o=4 Time=211.084(CPU秒)
b=4 Time=211.087(CPU秒)
充足解を書き込み中です。C:\Users\sugaw\Documents\Visual Studio 2015\Projects\schedule_nurse_ver2\WindowsFormsApplication1\test\sim_engine32\solution1.txt 211.091(CPU秒)
充足解を書き込みました。C:\Users\sugaw\Documents\Visual Studio 2015\Projects\schedule_nurse_ver2\WindowsFormsApplication1\test\sim_engine32\solution1.txt 211.102(CPU秒)
解探索が終了しました。 211 (秒)
解が得られました。
この例は、ScNurseが優れた結果になりましたが、逆の例も沢山あります。
穴を埋めると作業といいますか、どのようなインスタンスでもStateOfArtの性能に近いソルバーが理想な訳です。
そのための第2エンジンの開発です。
現行のScNurseが、どこが強くてどこが弱そうかという話はRAMP講演でした通りですが、
その辺が、第2エンジンを付加することでどのようになるのか、これから検証していきます。
が、未だ全てのインスタンスが走らせることが出来ていません。特に池上先生のインスタンスは数理的には非常に困難なインスタンスです。
ある意味究極のモデリング方法を採っていると言ってよいかと思います。スケジューリングサイトのベンチマーク問題とは対照的に、
非常に汎用的な記述になっています。池上先生にお聞きしたことがあるのですが、欧米のシフトと日本のシフトで違いはあるか？という問いに対して、同じという風におっしゃていました。
確かに、これほど汎用的なモデリングが可能ならどのようなシフト形態も記述可能でしょう。
もう一つ特筆すべきは、この解数は、一つや二つではなく、恐らく何百万もあるということです。CPLEXで最適解を発見するのに10-15分かかかるのですが、
一度発見すると、あれよあれよという間に解の個数は増え、一ヶ月回しても未だ止まらない、という解の出方なんだそうです。
その事自体が、学会でも新鮮な驚きだったようです。宇宙は思ったより広いということでしょうか？
池上先生のベンチマークは、看護師長がつくった制約を丹念にモデリング化したリアルプロジェクトです。人間がつくった制約になります。
ところが、Competitionや公開されているベンチマークは、ある確率空間モデルで生成された計算機が生み出した制約です。特に、スケジューリングサイトの解の個数は、非常に少ないということは、
分かっています。これにより得意不得意の分野が分かれるのがお分かりでしょう。解の個数/探索空間が重要なファクタになっていると思います。
登録:
投稿 (Atom)