下は、CPLEXのログになりますが、Elapsed Timeが表示されるまで、時間の経緯が判りません。
これでは、時間ー目的関数値 の推移グラフが書けません。
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 359195.0000 -370.0000 100.10%
0 0 -64.2187 3315 359195.0000 -64.2187 19 100.02%
* 0+ 0 43470.0000 -64.2187 100.15%
0 0 53.7500 2331 43470.0000 Cuts: 279 18717 99.88%
0 0 110.7778 2628 43470.0000 Cuts: 759 27889 99.75%
0 0 148.0682 2551 43470.0000 Cuts: 703 38963 99.66%
* 0+ 0 29975.0000 148.0682 99.51%
* 0+ 0 29915.0000 148.0682 99.51%
* 0+ 0 29905.0000 148.0682 99.50%
* 0+ 0 29705.0000 148.0682 99.50%
* 0+ 0 28675.0000 148.0682 99.48%
0 0 178.1077 2688 28675.0000 Cuts: 729 48298 99.38%
0 0 216.1885 2671 28675.0000 Cuts: 677 64088 99.25%
0 0 242.7695 2696 28675.0000 Cuts: 647 72639 99.15%
0 0 253.8045 2680 28675.0000 Cuts: 623 81504 99.11%
0 0 270.4266 2508 28675.0000 Cuts: 662 90893 99.06%
0 0 277.8454 2682 28675.0000 Cuts: 569 101580 99.03%
0 0 288.5256 2773 28675.0000 Cuts: 570 112909 98.99%
0 0 294.7174 2735 28675.0000 Cuts: 654 125075 98.97%
0 0 307.0973 2715 28675.0000 Cuts: 574 134680 98.93%
0 0 313.8889 2563 28675.0000 Cuts: 569 144764 98.91%
0 0 318.3333 2735 28675.0000 Cuts: 501 154305 98.89%
0 0 320.6537 2686 28675.0000 Cuts: 428 165201 98.88%
0 0 324.8424 2511 28675.0000 Cuts: 479 176102 98.87%
0 0 328.7166 2701 28675.0000 Cuts: 486 186932 98.85%
0 0 331.1991 2640 28675.0000 Cuts: 467 196434 98.84%
0 0 333.7144 2667 28675.0000 Cuts: 511 206362 98.84%
0 0 335.4018 2422 28675.0000 Cuts: 452 214946 98.83%
* 0+ 0 13650.0000 335.4018 97.54%
0 0 337.7659 2424 13650.0000 Cuts: 446 224872 97.53%
* 0+ 0 4360.0000 337.7659 92.25%
* 0+ 0 4210.0000 337.7659 91.98%
* 0+ 0 4180.0000 337.7659 91.92%
* 0+ 0 4130.0000 337.7659 91.82%
* 0+ 0 4120.0000 337.7659 91.80%
* 0+ 0 4105.0000 337.7659 91.77%
* 0+ 0 4095.0000 337.7659 91.75%
* 0+ 0 4080.0000 337.7659 91.72%
* 0+ 0 4065.0000 337.7659 91.69%
* 0+ 0 2315.0000 337.7659 85.41%
* 0+ 0 2100.0000 337.7659 83.92%
* 0+ 0 2085.0000 337.7659 83.80%
* 0+ 0 2075.0000 337.7659 83.72%
* 0+ 0 2065.0000 337.7659 83.64%
* 0+ 0 2055.0000 337.7659 83.56%
* 0+ 0 1985.0000 337.7659 82.98%
0 0 338.7064 2534 1985.0000 Cuts: 341 233655 82.94%
0 0 338.9290 2501 1985.0000 Cuts: 449 243012 82.93%
0 0 340.3071 2604 1985.0000 Cuts: 400 252547 82.86%
0 0 342.6351 2680 1985.0000 Cuts: 479 262409 82.74%
0 0 345.2399 2705 1985.0000 Cuts: 468 271762 82.61%
0 0 346.5593 2594 1985.0000 Cuts: 392 281214 82.54%
0 0 348.2926 2696 1985.0000 Cuts: 424 291728 82.45%
0 0 348.6862 2780 1985.0000 Cuts: 400 301858 82.43%
0 0 352.1631 2469 1985.0000 Cuts: 466 311631 82.26%
0 0 353.1727 2388 1985.0000 Cuts: 518 322374 82.21%
0 0 354.3967 2365 1985.0000 Cuts: 402 333125 82.15%
0 0 356.1600 2490 1985.0000 Cuts: 409 344215 82.06%
* 0+ 0 1785.0000 356.1600 80.05%
0 0 356.3396 2468 1785.0000 Cuts: 458 354575 80.04%
0 0 358.8643 2531 1785.0000 Cuts: 340 365518 79.90%
0 0 359.0449 2455 1785.0000 Cuts: 499 380153 79.89%
0 0 359.3243 2318 1785.0000 Cuts: 395 410059 79.87%
0 0 360.6046 2354 1785.0000 Cuts: 463 424344 79.80%
0 0 361.3983 2513 1785.0000 Cuts: 445 438669 79.75%
0 0 363.0090 2273 1785.0000 Cuts: 429 450682 79.66%
0 0 364.2676 2379 1785.0000 Cuts: 453 460801 79.59%
0 0 364.5254 2297 1785.0000 Cuts: 453 473808 79.58%
0 0 366.6675 2711 1785.0000 Cuts: 363 487309 79.46%
0 0 369.5115 2678 1785.0000 Cuts: 440 501845 79.30%
0 0 369.6678 2527 1785.0000 Cuts: 447 515283 79.29%
0 0 370.5862 2485 1785.0000 Cuts: 409 526362 79.24%
0 0 372.0121 2644 1785.0000 Cuts: 441 537949 79.16%
0 0 372.7673 2541 1785.0000 Cuts: 417 561352 79.12%
* 0+ 0 1775.0000 372.7673 79.00%
0 0 373.3979 2573 1775.0000 Cuts: 443 571316 78.96%
* 0+ 0 1665.0000 373.3979 77.57%
0 0 374.5699 2491 1665.0000 Cuts: 411 593582 77.50%
0 0 375.9199 2535 1665.0000 Cuts: 411 606301 77.42%
0 0 376.9399 2510 1665.0000 Cuts: 427 618234 77.36%
0 0 377.4003 2617 1665.0000 Cuts: 426 628252 77.33%
0 0 378.4336 2562 1665.0000 Cuts: 413 641045 77.27%
0 0 379.1902 2433 1665.0000 Cuts: 404 651619 77.23%
0 0 381.9274 2640 1665.0000 Cuts: 443 663832 77.06%
0 0 382.7832 2655 1665.0000 Cuts: 449 688911 77.01%
0 0 383.8327 2516 1665.0000 Cuts: 478 700613 76.95%
0 0 384.2792 2581 1665.0000 Cuts: 434 719632 76.92%
0 0 385.4148 2659 1665.0000 Cuts: 305 731989 76.85%
0 0 387.5154 2595 1665.0000 Cuts: 457 741474 76.73%
0 0 390.1512 2554 1665.0000 Cuts: 461 750275 76.57%
0 0 391.2088 2629 1665.0000 Cuts: 366 759972 76.50%
0 0 393.4489 2724 1665.0000 Cuts: 597 768781 76.37%
0 0 394.2833 2650 1665.0000 Cuts: 465 781215 76.32%
0 0 394.7189 2601 1665.0000 Cuts: 404 790527 76.29%
0 0 396.0850 2609 1665.0000 Cuts: 483 802531 76.21%
0 0 396.9782 2520 1665.0000 Cuts: 402 817779 76.16%
0 0 399.2371 2635 1665.0000 Cuts: 443 829483 76.02%
0 0 399.7541 2654 1665.0000 Cuts: 401 838973 75.99%
0 0 400.5069 2506 1665.0000 Cuts: 475 860150 75.95%
0 0 401.0033 2533 1665.0000 Cuts: 541 870828 75.92%
0 0 401.1352 2633 1665.0000 Cuts: 441 880720 75.91%
0 0 401.3362 2377 1665.0000 Cuts: 141 891428 75.90%
0 0 401.6659 2670 1665.0000 Cuts: 610 903345 75.88%
0 0 402.2398 2599 1665.0000 Cuts: 353 915823 75.84%
0 0 402.3160 2585 1665.0000 Cuts: 481 929191 75.84%
Heuristic still looking.
Heuristic still looking.
* 0+ 0 1630.0000 402.3160 75.32%
0 2 402.3160 2585 1630.0000 402.3160 929191 75.32%
Elapsed time = 10455.15 sec. (1830372.98 ticks, tree = 0.02 MB, solutions = 28)
1 3 402.3160 2569 1630.0000 402.3160 930957 75.32%
2 4 402.4682 2570 1630.0000 402.3160 933742 75.32%
3 5 403.9569 2529 1630.0000 402.3160 936012 75.32%
* 4+ 3 1480.0000 402.3160 72.82%
* 4+ 3
一方、GUROBIは、最初にリニアオプティマイザをPrimal・Dual Simplexにして、Simplexを廻した後、最初の整数解が出るまでに、767secかかっていることがわかります。逐次時間のとともに目的関数値が減少していく様子が判るので、グラフ化できます。同じインスタンスについて、SC3 Algorithm1・Algorithm4 と比較すれば、性能比較の可視化を行うことができます。
それにしても、Feasibleな解がでるまでに10分もかかっていたのでは、使い物になりません。
RAMP講演でも、「CPLEXで解が出なかったインスタンスがある」 と報告して、「おかしいんじゃないか？」という指摘を受けたことがありました。その理由は、NEOS SERVERのShort Priority(直ぐにやってくれるが5分でタイムアウト）での実行による結果でした。正しくは、「5分で実行可能解が出てこないインスタンスがある。」に訂正します。手持ちお客さまのインスタンスで説明しましたが、
決して特殊な例ではありません。（5分も何も言ってこないのは、解がない というのが私の感覚でした。）
この例のインスタンスは、INRCⅡの120W4というインスタンスで、規模的には、大きいインスタンスになりますが、超大規模というものではありません。数理的ソルバーの優位性は、厳密解を出せることにありますが、一般のナーススケジューリング問題においては、厳密解を出せるインスタンスというのは、むしろ少ないです。従い実務におけるナーススケジューリング問題では、数理的ソルバーの出番は少なく、主にメタヒューリスティクスによる解法が主になります。決してソルバーのコストによるものではなく、求められる精度と速度が、向いていない、ということに尽きます。
Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 2.3065000e+04 1.830000e+02 6.010239e+08 17s
24989 5.9105058e+04 0.000000e+00 5.427999e+06 20s
39027 1.4139465e+04 0.000000e+00 1.530505e+06 25s
48531 8.4548149e+03 0.000000e+00 8.561291e+05 30s
54075 4.6553869e+03 0.000000e+00 6.203191e+05 35s
57243 4.0333315e+03 0.000000e+00 1.884978e+06 40s
59619 3.2945051e+03 0.000000e+00 2.485297e+07 45s
61995 2.8932136e+03 0.000000e+00 1.937645e+06 50s
63843 2.6364303e+03 0.000000e+00 1.824680e+06 56s
65955 2.4071407e+03 0.000000e+00 1.529677e+06 60s
67803 2.1433875e+03 0.000000e+00 3.572679e+06 66s
69387 2.0198157e+03 0.000000e+00 1.500083e+06 70s
70957 1.8682992e+03 0.000000e+00 5.175105e+06 75s
72527 1.7109733e+03 0.000000e+00 1.534901e+06 80s
74371 1.6059518e+03 0.000000e+00 7.316991e+05 86s
75691 1.4715193e+03 0.000000e+00 8.885731e+05 90s
77275 1.2998909e+03 0.000000e+00 2.408987e+06 96s
79123 1.2171491e+03 0.000000e+00 1.039386e+06 100s
80707 1.1319239e+03 0.000000e+00 7.554920e+06 105s
82555 1.0430034e+03 0.000000e+00 2.797781e+06 111s
83875 9.5441597e+02 0.000000e+00 4.827466e+06 115s
85459 8.9434760e+02 0.000000e+00 2.612262e+05 121s
86779 8.2570058e+02 0.000000e+00 1.466299e+06 125s
88363 6.7444245e+02 0.000000e+00 1.998739e+06 131s
89683 5.7750613e+02 0.000000e+00 1.569387e+06 136s
90999 5.1294778e+02 0.000000e+00 8.648063e+05 141s
92031 4.6633167e+02 0.000000e+00 1.271406e+07 145s
93329 4.1456737e+02 0.000000e+00 4.761322e+06 151s
94349 3.7612396e+02 0.000000e+00 1.849774e+06 155s
95599 3.2109644e+02 0.000000e+00 3.595911e+05 161s
96629 2.6097565e+02 0.000000e+00 5.134349e+05 165s
97893 2.2486428e+02 0.000000e+00 4.157836e+05 171s
98907 1.7423268e+02 0.000000e+00 1.301501e+06 176s
100199 1.2653451e+02 0.000000e+00 1.601937e+06 181s
101199 8.5595718e+01 0.000000e+00 5.010955e+05 186s
102247 4.7167686e+01 0.000000e+00 1.260490e+06 190s
103487 1.2204544e+01 0.000000e+00 4.461667e+05 196s
104407 -1.6047682e+01 0.000000e+00 1.948257e+05 200s
105607 -4.7594571e+01 0.000000e+00 2.135647e+05 206s
106527 -6.6654211e+01 0.000000e+00 1.916288e+05 211s
107407 -8.9912197e+01 0.000000e+00 4.649965e+05 215s
108547 -1.1011925e+02 0.000000e+00 2.579404e+06 221s
109477 -1.2357405e+02 0.000000e+00 1.109971e+05 226s
110437 -1.4304921e+02 0.000000e+00 4.081576e+06 231s
111387 -1.5994959e+02 0.000000e+00 3.459370e+05 235s
112567 -1.7748868e+02 0.000000e+00 4.569213e+05 241s
Concurrent spin time: 0.00s
Solved with dual simplex
Root relaxation: objective -6.890137e+02, 85445 iterations, 227.18 seconds
Total elapsed time = 401.32s
Total elapsed time = 476.00s
Total elapsed time = 579.92s
Total elapsed time = 672.39s
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -689.01374 0 3777 1429275.00 -689.01374 100% - 767s
H 0 0 31485.000000 -689.01374 102% - 768s
H 0 0 27825.000000 -689.01374 102% - 768s
H 0 0 8355.0000000 -689.01374 108% - 769s
0 0 -578.43551 0 5449 8355.00000 -578.43551 107% - 886s
H 0 0 6115.0000000 -578.43551 109% - 888s
0 0 -574.51017 0 5343 6115.00000 -574.51017 109% - 910s
0 0 -574.34337 0 5278 6115.00000 -574.34337 109% - 913s
0 0 -574.34337
0 件のコメント:
コメントを投稿