2018年11月7日水曜日

番原先生が名古屋大に

日本で先進的な研究成果を上げているプロジェクトがあります。このプロジェクトもその一つで日本語での論文やチュートリアル解説等で、私に与えた影響は大きく、大変勉強になっています。その中の中核メンバーの番原先生が名古屋大に移られたようです。

野々部先生の新しい論文が興味深いです。これは読まないと。

C++共用体

速いソルバーを構成する上で欠かせないのがC++です。その中でも強力な機能がPlacement newや共用体といった特徴的なC++機能です。あるクラスを書いていて、vectorと配列のunionが出来ないかなと思っていたら、最新C++では、出来るのですね。このサイトが参考になりました。コンストラクタ、デストラクタ、コピーコンストラクタ、代入演算子をしっかりと定義すれば、「削除された関数を参照しました」エラーから開放されます。
アルゴリズムがもっとも重要であることには変わりはないのですが、実装テクニックも僅差の勝負となるCompetitionでは重要です。

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から始まって、徐々に下げている様子が分かります。スレッド数は4のようです。



*************************************************************

   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 (秒)
解が得られました。
 
 
この例は、ScNurseが優れた結果になりましたが、逆の例も沢山あります。

穴を埋めると作業といいますか、どのようなインスタンスでもStateOfArtの性能に近いソルバーが理想な訳です。

そのための第2エンジンの開発です。
現行のScNurseが、どこが強くてどこが弱そうかという話はRAMP講演でした通りですが、
その辺が、第2エンジンを付加することでどのようになるのか、これから検証していきます。
が、未だ全てのインスタンスが走らせることが出来ていません。特に池上先生のインスタンスは数理的には非常に困難なインスタンスです。
ある意味究極のモデリング方法を採っていると言ってよいかと思います。スケジューリングサイトのベンチマーク問題とは対照的に、
非常に汎用的な記述になっています。池上先生にお聞きしたことがあるのですが、欧米のシフトと日本のシフトで違いはあるか?という問いに対して、同じという風におっしゃていました。
確かに、これほど汎用的なモデリングが可能ならどのようなシフト形態も記述可能でしょう。

もう一つ特筆すべきは、この解数は、一つや二つではなく、恐らく何百万もあるということです。CPLEXで最適解を発見するのに10-15分かかかるのですが、
一度発見すると、あれよあれよという間に解の個数は増え、一ヶ月回しても未だ止まらない、という解の出方なんだそうです。
その事自体が、学会でも新鮮な驚きだったようです。宇宙は思ったより広いということでしょうか?

池上先生のベンチマークは、看護師長がつくった制約を丹念にモデリング化したリアルプロジェクトです。人間がつくった制約になります。
ところが、Competitionや公開されているベンチマークは、ある確率空間モデルで生成された計算機が生み出した制約です。特に、スケジューリングサイトの解の個数は、非常に少ないということは、
分かっています。これにより得意不得意の分野が分かれるのがお分かりでしょう。解の個数/探索空間が重要なファクタになっていると思います。