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でも全く歯が立ちません。
0 件のコメント:
コメントを投稿