ついに3000秒を切って2700秒となりました。
マルチスレッド方法の改善によるものです。
2021年8月31日火曜日
2021年8月27日金曜日
Instance13速度改善
前回報告よりさらに速度アップしました。(5091sec→3019sec)です。
これは、マルチスレッド方法の見直しによるものです。LpSolverは、CLPのままです。
CPUのUsageをモニタすると下のようになっています。三角の頂点部分は、マルチスレッド化している部分でOPEN_MPにより使用可能なスレッドが全て投入されます。底辺部分は、シングルスレッドで動いている部分です。このCPUは、4threadsなので、シングルスレッドの使用率は25%です。この部分はほぼLPSolverが占有しています。
通常の規模程度（Instance8）では、LPSolverの時間はほぼ無視できる程短いので、下のように、ほぼ、全期間フルスレッドで働いているように見えます。（一方のInstance13は、１monthではありますが、スタッフ数120人と大規模インスタンスですので、LpSolverの計算に食います。）
前記三角頂点部は、大規模になってもスレッド数を増やせば補償できる部分です。ところが、シングルスレッド部である底辺部は、補償できません。よって大規模インスタンスでは、LpSolverの性能がネックになる、ということが言えます。
マルチスレッド数とNSP問題探索速度の関係
一般にインスタンス規模は、指数関数的に増加します。それ故、メタヒューリスティクス系では、マルチスレッド化してもさほど効果は感じられないと思います。
MIPソルバのKeyは、BranchAndBoundですが、Treeの性質を考えると√倍程度の効果（４Threadsで2倍の速度）のように思います。Algorithm4も基本的には、B&Bですので、100%CPUを使い切ったときに、√倍程度の改善と考えられます。
2021年8月20日金曜日
CoinPackedMatrix
OSIをいじっていると必ず出くわすのが、CoinPackedMatrixです。疎行列表現になっていて特殊な形式です。
ソースを見ると、Copyrightは、IBMになっています。これは、CBCが、IBMにいたJohnForrestと言う方が開発者であったことに関係しているらしいです。
それは、ともかくLPに問題を入力するには、CoinPackedMatrixを生成してやって、それを引数としてOSIのLoadProblemをCALLします。
2021年8月18日水曜日
OSI OpenSolverInterface
GitHub - coin-or/Osi: Open Solver Interface
LpSolverの標準インタフェースを提供するWrapperクラスです。LpSolverは、各社・各団体によりインタフェースは異なりますが、OSIで書いておけば、別なLpSolverを使いたくなったとき、最小の手間で移行できるメリットがあります。実装済みであれば、それを呼びばよいのですが、今回使おうとしているLpSolverは、OSIが未だサポートされていないので、自分で書く必要があります。
ともあれ、CLPの実装はそのままに他のLpSolverも使えるように内部をRefactoring中です。
2021年8月17日火曜日
巨大インスタンスは、LP Solverが問題
Instance20-23でのClp時間を見てみます。NEOS Serverに乗っかるぎりぎりのサイズ(16MB程度）で、MPSファイルを生成しています。
この結果から分かる通り、NSP巨大インスタンスでは、LP Solverの性能がボトルネックです。現状CLPでは、最初の整数解が出て来るまでに一週間から一ヶ月程度計算機を廻さないといけません。
この問題に対してStrandmarkさんは、FirstOrder Solverを用いることを提案しています。
https://www.strandmark.net/papers/first-order-scheduling.pdf
しかし私の厳密解に拘るアプローチでは、FirstOrderは、精度の問題があり使えません。Simplexの良い点は、WarmStartできる点にあります。そこで、First Order Solverや、Barrier Solverの結果をSimplex形式に変換するCrossoverという手法があります。
Initial Basis Selection for LP Crossover (cerfacs.fr)
どのように巨大インスタンスに立ち向かうべきか思案中です。
2021年8月16日月曜日
分岐限定の様子
Algorithm4の分岐限定は、ほぼDFS(Depth First Search)です。
下記は、Instance8で、LP解のfractionalなRoster/Dayをドットで表現しています。Branchによって、少なくともその点は、整数化されていきます。
初期Depth0は、
8 : . . .. ... .
19 : . .. ......... ..... ..
8 : . . . . .. . .
9 :. ....... .
22 :.. ..... ..... .... ......
18 :..... ... . .. ..... ..
9 :. . .. ... . .
8 :. ... . ...
13 :..... .. .. . . . .
10 : .. ..... . . .
14 : ....... . . .....
3 :.. .
7 : ... . ...
22 :. . .... .......... ......
12 : .. .... ..... .
5 : ... . .
13 :.. . ... .. .. ...
0 :
6 : ... . ..
1 : .
6 : . . ....
17 :.. ....... ...... ..
14 : . ..... ..... . ..
4 : . . . .
11 :.. . . . . .. .. .
14 :.. ... . .... .. . .
0 :
10 : . . . . .... ..
6 : . . .. . .
5 : . . . . .
psum=294 out of 840 35[%]
Depth22になると、
8 : . . .. ... .
18 : . .. ......... .... ..
6 : . . . . . .
2 : . .
8 :.. . . . ...
14 :..... ... . .. . . .
7 :. . . .. . .
8 :. ... . ...
14 :..... .. .. . .. . .
5 : . .. . .
10 : ....... ...
0 :
8 : .... . ...
14 : . ......... .. ..
4 : .. ..
5 : ... ..
14 : . ....... . .. ...
0 :
7 : ... . ...
1 : .
0 :
12 : ...... ..... .
12 : . .. ..... . ...
3 : . . .
10 :.. .. .. .. ..
10 :.. .... . ...
7 : . . .... .
11 : . . . .... . .. .
4 : . . . .
6 : . . . . ..
psum=228 out of 840 27.1429[%]
Depth42では、
0 :
1 : .
2 : . .
0 :
6 : ... ...
7 : ... . .. .
2 : . .
0 :
0 :
5 : . .. . .
8 : ..... ...
0 :
1 : .
6 : . .. . . .
5 : .....
1 : .
13 : . .. ... .... .. .
0 :
2 : . .
2 : ..
1 : .
2 : . .
9 : ..... . ...
0 :
2 : . .
2 : ..
3 : . . .
0 :
2 : . .
2 : . .
psum=84 out of 840 10[%]
となり、Depthが深まるにつれ、Fractional部分は少なくなることが分かります。限定しているのは、Depth分のみの変数ですので、限定した以外にも付随して整数化される傾向があることが分かります。
しまいには、全て整数化、つまり分岐限定化したところでの整数最適値が見つかります。全ての分岐でこの作業を行えば、そのインスタンス全体の、整数最適値が見つかります。Reasonableな時間内に、走査を終えることができるかは、Treeの大きさにかかっています。Treeの大きさは、TreeNodeの選び方にかかかってきます。
初期Fractionalの具合は、Instanceにもよります。
例えば簡単なInstance2は、
0 :
1 : .
2 : . .
0 :
6 : ... ...
7 : ... . .. .
2 : . .
0 :
0 :
5 : . .. . .
8 : ..... ...
0 :
1 : .
6 : . .. . . .
5 : .....
1 : .
13 : . .. ... .... .. .
0 :
2 : . .
2 : ..
1 : .
2 : . .
9 : ..... . ...
0 :
2 : . .
2 : ..
3 : . . .
0 :
2 : . .
2 : . .
psum=84 out of 840 10[%]
です。初期でも、Fractionalがかなり少なくなっていることが分かります。後一押しという感じです。
重いInstance20は、
77 :..... . .... ... . ..... ..... ... ... . . ......... .......... ... ...... . .. ...... . .. ... ..
89 :..... .. ... ..... .. ..... ..... ..... . . ...... .. ...... . ............. ...... . . ..... ... . .... .. ....
65 : .. . . .. .. . .. ... .. . ..... ... .. . . . . ... .... . . .. .... . .. .... ... .. ... . ...
81 :.... ..... ... . . ..... ..... ... ..... ..... ..... ..... .... ...... .... ..... ... . .. .. . . .. ...
90 :....... .. . .... . . . .... ... . .. ........ . ............ . . . ..... .. .. ..... ............. . . ..........
58 :.. . .. . . .. .. .. .. ... . ... ..... . ... . ..... .. ... .. .. . .. ..... ... .
98 :........ . .. .. ..... . ....... .... ..... ..... . ... . . ..... ... ..... ..... . ... . . ... ........ . ................
80 :. . ...... ...... . .. .... .. . .. .... . ... .. . ......... . ... . .............. ... ... . . .. . . ...
88 :..... ..... ..... ....... .. ... .. .. . . .. ....... .. ..... .... ........ . . . .. ...... ...... . .. .... ...
56 : ... ..... .. . .. .. . . .... . ........ .... .... .... . ... ... .......
107 :... ..... ....... .. .................... . .. .. . . .. ......... . ...... ...... ..... ... . . ... .... .. .... ................
119 :................. ...... ... . ... . ..... . ... .. ....... . .............. .. .. ..... .. ....... ...... .......................... .....
82 :.. .. . .. .. . . ..... .. .... ... . .... .. . .. . .. ..... ..... . . .. . ........ ........ ...... .......
62 :..... .. .. . ... ..... .. . . .. . . . . ..... ..... .. ... ...... . . . . . . ... ... .
98 :. . .. .................... ... . ...... ... . .... ..... ..... . ..... . .. ..... .... . ........ ...... ....... ......
132 :................................. ............ ... ..... ................. ..... .. ............ .................... . ... . ... .. . ............
113 :..... .... ............ ...... ..... ................ .. ........ ...................... ................. .. .... . ... ......
87 :. ..... . . ........... ... ........ .................. .. ..... ........... . . .. ............... ..
91 : .. ......... .... ..... .... ..... . . .... ............................. ......... . . .. .......... ....
70 :.. . . ... . . . . .... ... . .. ....... .. . .. ..... . . .... .... ..... ..... ....... . . . ..
82 :. ... .. .. ... . .. ........ .. . . ... . . ..... .. . . . ... .............. ........ . ... .. ... .......
91 :..... ....... ....... . . ...... .... .. .... .. . . ...... ... ........... ........ ..... . .... .. ..... .. ...
110 :................... ..... . ... . ......... . .. . . . ........ . ......... ..... . ..... ................ ..... . . .. .. ..........
105 : .... .. .. ............... ....... .......... . .. ...................................... . ... .... .. ... . ......... .
89 :.......... . ....... ...... .... . . ........ ....... ...... . . ....... . . . .... . .....................
110 :.......... ....... .... ..... ..... . . ..... .. .. . .... . .................... . ....... ........... .. ... . . .. ..............
120 : . ... . ....................... ... . ... ....... ....... ............ ..... ........................ ..... . ........ . . . .. ......... ..
114 :................. ..... ....................... ........... .. ..... ..... ...... . ... . ................... .. .... .. ..... . ..
103 :..... . .. . ............. . . . ............... . .. ........................... ........... . ...... . . ....... ..... .
90 :.... . ..... ....... . . . .. . . . . ....... . . ..... ..... ..... ....... .. .......... ..... ..... ..... ..... .
97 :. . . ... . .. . . ....... .... ... . .. ... ...... ............ ..... ....... ... ... . . ... . ... ... .. . . . .............
106 :................ ...... . ......... ..... ...... . . . ... ............ ...... ..... . . ........ ....... . ... . . . ... . ... ...
109 :............ ...... . . ................. ...... ....... ....... . . ..... ............ . . ..................... .... ......
90 : . ... . . ....... . .. . . ... .. ..... ... ... . . ... ......... .. ... . ....... ...... ............ .. ..... . ...
128 :... . ................... . .. .. ...... ............. .. . ...................... . . ....... ................ ............ ....... ..... .......
104 : ... .. ........ .... ............. ........ ........ .. . ... . ... .............. .... .. . ..... ... . . .................
102 :.. ..... ...... . .. .......... ..... . . ....... .. ..... .. ..... . . .......... ............................ .... ....
80 :......... ....... . . ........ ............ . ... ... ....... ............ .. . ... . ... . ... ..
67 : . . . ... .... ..... .. .............. .. ... . .. ......... . .... . . .. . ... . . . ...
91 :. . . . ... ... .... . ... .. ..... .. .......... ... . . ............ .. ..................... .......... .. . .
57 : .... .. .. .. ...... . .. . .. ... .. .. ... ............. ....... . ... .
39 : .. .. ... .. .. ..... . . . ....... . .. . . . ... ....
80 : .. ... . ... .... ....... .... . ...... . . ..... .... .. . ....... . ..... ...... .... ... . .. ......
75 : . . .... .... .. ... ..... ....... .. .. .. ..... . ..... .... .. ......... .... ...... ......
52 : .. .. .. .. .. . ..... . ..... .. .. . .... ..... ... ... ... .. .....
69 :... . . .. .. . . ... . . .. ... . ... .. ..... . . . . . ... . .. ... . ... .... .... . . . ... . . .. .
102 :. . . . . ......... .... ... ... . . ......... . .... ...... .......... . ....... .... . ... . . ... ....... . ............... . .
93 : ....... . .. .. .. .... . . ...... ......... ......... . . ... .... .. . . .. ............. .. . ... ........... . . . .
73 : .... . ... ... .... ..... . ........ ...... . . .. . .... . . .. . ... .... . . .. ...... . . . . ...
78 :... . .. . . . ...... . ... ... ... . . ..... . ..... . . . .. .. . .. ... .. . .... ... . .. . .. ... .... . . . .
psum=4449 out of 9100 48.8901[%]
のように、Fractional割合が高くなっています。
確かに、最難度と考えられるINRC2 120W8インスタンスでは、Fractionalsの割合が下のように、もっとも高くなりました。
49 : ........................................ ..... ....
22 : .... .... ...... .. .... ..
48 : ................ ...... ..................... .....
27 : .... .... ...... .... .... .....
40 : ..... ..... ..... ..... ..... ..... ..... .....
34 : ....... ........ ..... ...... .... ....
40 : ....... ....... ..... ........ ........ .....
46 : . ...... ...... ...... .......... ..... ..... .......
49 : . ....... ...... .............................. .....
41 : ..... ..... ..... ..... ... .... .... ..... .....
42 : .......... ..... ..... ..... ... .... ...... ....
40 : ..... ..... ..... ..... ..... ... .... . .. .....
28 : .... ...... ........ ..... .....
35 : .... ...... ..... ....... ........ .....
38 : . .... ... ..... ..... ..... ... .... ..... ...
41 : ..... ..... ..... ..... ... .... .... ..... .....
51 : ... ........................................ ........
44 : ..... ..... ..... ..... ... ........... ...... ....
27 : . ..... ...... .... .... .......
42 : ..... ..... ..... ..... ..... ..... ..... .......
42 : ..... ..... ..... ..... .......... .... ..... ...
40 : ... .... ..... .... .............. ..... .....
35 : .... ....... ..... ....... ....... .....
27 : ..... .... .... ...... .... ....
40 : ... ..... ..... ..... ..... ..... ..... .......
43 : . ........................ ... ..... ..... .....
21 : .... ..... ..... .. .....
26 : ..... .... .... ..... .... ....
37 : ..... ..... .... ... ..... ..... ..... ... ..
47 : .. ........ ..... ..................... .... .......
30 : ..... ..... ..... ..... ..... .....
40 : ... ..... ..... ..... ... ... ..... ...... .....
44 : ........................ ..... ..... ..... ... ..
40 : ..... ..... ..... ..... ..... ..... ..... ... ..
44 : ..... .... .... ................... ..... .......
49 : .......... ...... ........................ .... .....
42 : ..... ..... ..... ..... ... .. . ...... ...... ....
25 : .... .... ..... .... .... ....
42 : ..... ................ ...... .... ... ... .....
23 : .... ....... ....... .....
42 : ..... ..... ..... ..... ..... ..... ..... .......
27 : .... .... ...... .... .... .....
40 : ..... ..... ..... ..... ..... ..... ..... .....
36 : .... ...... ..... ........ ........ .....
17 : .... .... .... .....
38 : .. ..... ..... .. .. .... ... ..... ..... .....
51 : .............................................. .....
36 : ... ..... ..... ........ ..... ..... .....
40 : ..... ..... ..... ..... ..... ..... ..... .....
40 : ..... ..... ..... ..... ..... ... .... ..... ...
42 : ..... .......... ..... ..... ..... ..... .......
40 : . .................. ..... ....... .... .....
41 : ..... ..... ..... ..... ..... ..... ... ..... ...
41 : ..... ..... ..... ..... ... ..... ..... ..... ...
38 : ....... ........ ..... ....... ....... ....
34 : .... ............ ..... ..... ... .....
48 : ..... .......................... ..... ..... .......
27 : ..... .. .. .... .... ..... .....
21 : .... .... ..... .... ....
29 : . ..... ..... ..... ... .. . ..... ..
39 : ..... ..... ...... ..... ... ..... ..... .....
42 : ..... .... ...... ................. ..... .....
17 : .. .... .... .. .....
27 : ... .... .... ...... ........ . .
48 : ..... ....... ................................ ....
27 : ...... .... .... ... .. .... ....
50 : .... ................................... .... .......
23 : .. .... .... ..... .... ... .
34 : . .... . ...... .... . ......... ... .....
44 : ..... ..... ..... ..... ............... ..... ....
44 : .... .......................... ..... .... .....
42 : .. ....... ..... ....................... .....
42 : . ..................... ......... .... ... ....
35 : .. ..... .... ... ..... ..... ...... .....
35 : .... .... ....... ...... ..... ..... ....
43 : ............ ........ ..... ..... ...... .... ...
27 : .... .... ..... .... ..... .....
25 : .... .... ...... .. .... .....
27 : ...... .... .... ..... .... ....
38 : ..... .... .... ...... .... ..... ..... .....
40 : ..... ..... ..... ..... ..... ..... ..... .....
47 : .. .................. ...................... .....
40 : ..... ..... ..... ..... ..... ..... ... ... ....
0 :
38 : ..... ..... .. ..... ..... ..... ... ..... ...
28 : .... ...... ..... ..... .... ....
38 : ..... ..... ..... ..... ..... ..... ..... ...
37 : ........... ..... .... ..... ... . ...... ..
38 : ...... ........ ..... ........ ....... ....
41 : ........ ..... ....... .............. . ... ...
32 : .... .... ........ ....... .........
44 : ..... ... ..... ..... ........................ ..
50 : ......... ........ .................................
24 : .... .... .... .... .... ....
41 : .... ... ..... ..... ..... ... ................
31 : ....... ....... ...... ...... .....
43 : ..................... .... .... .... ..... .....
51 : ......... ............................. ....... ......
47 : .... ..... ................ ..... ..... ............
48 : ...... ............................ ..............
40 : .... ... ..... ..... ..... ..... .......... ...
40 : ........ ....... ....... ........ ..........
39 : ..... ..... ..... ..... ..... ..... ... .... . .
24 : . ..... ..... ..... .... ....
29 : ........ .... ..... ..... .......
45 : .......... ..... ..... ............... ..... .....
35 : .... ... .......... ... ..... ..... .....
40 : .... ......... ...................... .....
53 : . ........ ............................................
27 : ..... ..... ..... ..... .. .....
42 : ..... ..... ..... ..... ..... ..... ..... .......
43 : ..... ..... ..... ..... ... .... ..... ...... .....
51 : . ................. .......................... .......
44 : ..... ..... ..... ..... ..... ..... ..............
43 : ....... ..... ............... ..... .... .......
38 : .... ...... ...... ..... ..... ..... .......
44 : ..... ..... ..... ..... ....... ........ .........
44 : .... ................... ..... ..... ........ ...
54 : ........... ...... .....................................
49 : .... ....... ..... ................ ..... ............
psum=4540 out of 7560 60.0529[%]
一般に初期Fractionalsが多い程、整数化には時間がかかり最適解の難易度は上がると考えています。この位になるとCPLEX/Gurobiでも全く歯が立ちません。
2021年8月14日土曜日
分岐限定法
連続変数によるLPを解いた解は、連続変数解であって整数ではありません。LPを解くと、3.1人とか、4.6人とか、連続変数解が出てきます。人をぶった切る訳にも行かないので、整数化を行うことが必須になります。
LPは、下界を見積もるには重宝します。離散解は、連続変数解より良くなる筈がない、という原理に基づいて、離散解を得る前に、目的関数値の下界を得ることができます。「これ以上良くなることはありません」という値を知って、それなら、離散解を求めることなく制約に変更をかける、といったことも可能になります。
最も困難なのは、整数化です。MIPソルバでは、平面削除(CuttingPlane)、ヒューリスティクスによるReducedCostFixing、そして最後に分岐限定操作により整数化を行っています。CuttingPlaneだけで、整数化が完了するのは、小さいインスタンスのみで、大抵は、分岐限定で問題を分割して整数化を行うことになります。
NSPの分岐限定法は、まさに看護師長さんが、勤務表を作る様子そのものです。分岐限定は、Tree構造になりますが、どのRoster、Day、Shiftから始めればよいか？は、Tree構造の大きさに関係して求解速度に直結しています。
キーとなる重要なノードから選択して分岐限定を始めることがTreeSizeを小さくする上で鍵となります。LPで、Fractionalな数値ちょうど0.5あたりを選べば直感的には、良いようですが、Randomに選んだものと大差ないという結論のようです。ノード選択には、strong branching,pseude-cost 等の方法が知られています。
参考：
2021年8月13日金曜日
Instance規模について
問題の規模については、一概に言えないところがあるのですが、指標はあります。次の計算式です。
規模=Days * Staffs * ShiftTypes
です。例をあげましょう。SchedulingBenchmarks Instance1は
２Weeks,８Staffs, ShiftTypes=1になっています。スケジュールナースの場合は、陽に休みを定義していますので、シフトの状態数は+1になります。
instance規模１＝2*7*8*(1+1)=224
となります。以下同様に、
規模に応じて、所要メモリも増え探索空間増えるので難易度も上がっていきます。昔取ったデータでは、CBCは、インスタンス2程度、SCIPでもインスタンス4程度までしか厳密解は得られなかったと記憶しています。この問題群は、商用MIPソルバの独壇場にありCPLEX/Gurobiで解けます。現実規模のインスタンス郡の中で唯一Instance15だけが、未だに厳密解が知られていません。（このインスタンス上界下界の世界記録はScheduleNurse3が保持しています。）
Instance21以上は、規模が大きくすぎて、MIPソルバでも歯が立たず、未だ厳密解が知られていません。
SchedulingBenchmarksは、行方向のソフト制約がなく、実務的にはほぼ有り得ないインスタンス郡です。
実務インスタンスでは、行方向のソフト制約が入ってきるのが普通です。前々回あたりで言及したように、探索空間がさらに広がる方向になります。ですので、半年や、1年と言ったインスタンスで、厳密解を求めるのは、ほぼ無理です。Instance20は、期間が半年ですが、前述の特殊状況によるところが大です。
2021年8月12日木曜日
Instance13の求解速度改善
マルチスレッドの方法見直しにより速度改善しました。(7368sec→5091sec)
なお、4core/4threads Xeon W3565 3.2GHzの結果です。
2021年8月10日火曜日
Instance13が解けた
SchedulingBenchmarksで、instance13は、Reasonableな時間内に解けていませんでしたが、解けました。Pieter Smet さんが既にCplex/Gurobiで解いています。
What's new? (schedulingbenchmarks.org)
によると12000secかかっています。
Algorithm4では、7368secで解けました。
instance13は、120人19シフトでかなり大規模なインスタンスです。下のように、LB=UB=1348で厳密解が得られています。
2021年8月7日土曜日
many core 対応
安価に使用可能になってきました。
Algorithm4は、前述の最短経路問題解法を使用した数理解法になっています。現在は、ベンチマークテスト専用用途です。これをリニューアル、完全にマルチスレッド化し、実務的なインスタンス用途と、さらなるベンチマーク世界記録更新を目指そうと思います。SimplexやBranch&Bound等、主なMIP解法は、マルチスレッドの恩恵を基本得にくいのですが、NSPに限定すれば、数理解法でも恩恵を得ることができます。（使いどころは、やや限定されており、後で詳述します。）
thread_localとローカルに定義されたstd::vectorの組み合わせ - Qiita
登録:
投稿 (Atom)