スケジュールナースのブログ: Integer Branch

は、私の造語です。Branching　Treeは、基本的にDFS(Depth First Search)で行います。その際、どのノードかを始点とするかについては、登録された目的関数値が低い順に行います。しかし、UBとのギャップが未だあり、その間にGCDで割り切れる整数値のノードが存在した場合、ある条件下で、そのノードをブランチングの始点としています。これは、GCDで割り切れる整数目的関数値を持つノードは、そのまま解になる可能性が比較的高い、という私の知見に基づいています。比較的というのは、絶対ではなく外れることも多いのですが、他のFractionalなノードに比べれば、比較的高そうだ、ということは言えると思います。なお、これに関する論文は見たことがありません。

Integer　Branchingにより、8時間経っても厳密解証明が出来なかったインスタンスが10分で出来ることもあったので、効果はあるのではないかと思います。

これを適用することにより、INRC2 4WEEKSについては、ほぼ全てのインスタンスについて厳密解証明が完了しました。一応というのは、スケジュールナースⅢ以外で、このインスタンス郡について一インスタンスでも厳密解証明はおろか最適目的関数値に達したソルバは、皆無なので今のところ、他に確かめるすべはなく、自分のプログラムを信じるしかありません。(n005w4という極小さい、例題インスタンスについては、厳密解が各ソルバで得られています。）

適用は、139Aからになっています。次は、終了時のログの例です。この例では、UB=2115が確定しています。残っているノードが次のようになっています。この場合GCD=5なので、整数解が得られたとしても、2115以上となります。残っているノードで、2115-5以下のノードがないので、LB=2115　＆＆UB=2115で厳密解証明完了となります。ですから本来であれば、LB=2115と記すべきですが、最後にLBとなっているのは、初期時のLBを記しているからです。

branch_node_map.size()=54

Remaining objs

2112.5

2113.51

2114.23

2114.57

2115

2116.67

2117.5

2119.74

2122.14

2127.5

Final LB=2105 UB=2115 900.815[sec]

Finished solving process. 902 (sec)

スケジュールナースのブログ

2022年3月4日金曜日

Integer Branch

0 件のコメント:

コメントを投稿