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でも全く歯が立ちません。


0 件のコメント:

コメントを投稿