Yatharth Dubey - Theoretical and Computational Analysis of Strong Branching
305 بار بازدید -
پارسال
-
Part of Discrete Optimization Talks:
Part of Discrete Optimization Talks: https://talks.discreteopt.com
Yatharth Dubey - Carnegie Mellon University / University of Illinois at Urbana-Champaign
Theoretical and Computational Analysis of Strong Branching
Speaker webpage: https://sites.google.com/view/yathart...
Abstract: Strong branching is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side, we identify vertex cover as a class of instances where this rule provably works well. In particular, for vertex cover we present: 1) an upper bound on the size of the branch-and-bound tree using strong-branching as a function of the additive integrality gap; 2) show how the Nemhauser-Trotter property of persistency, which can be used as a pre-solve technique for vertex cover, is being recursively and consistently used throughout the strong-branching tree; 3) and finally provide an example of a vertex cover instance where not using strong-branching leads to a tree that has at least exponentially more nodes than the branch-and-bound tree based on strong-branching. On the negative side for strong-branching, we identify another class of instances where the strong-branching tree is exponentially larger than another branch-and-bound tree for solving these instances. On the computational side, we conduct experiments on various types of instances, like the lot-sizing problem and its variants, packing integer programs (IP), covering IPs, chance constrained IPs, vertex cover, etc., to understand how much larger is the size of the strong-branching based branch-and-bound tree in comparison to the optimal branch-and-bound tree. The main take-away from these experiments (on small instances) is that for all these instances the size of the strong-branching tree is within a factor of two of the size of the optimal branch-and-bound tree.
Yatharth Dubey - Carnegie Mellon University / University of Illinois at Urbana-Champaign
Theoretical and Computational Analysis of Strong Branching
Speaker webpage: https://sites.google.com/view/yathart...
Abstract: Strong branching is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side, we identify vertex cover as a class of instances where this rule provably works well. In particular, for vertex cover we present: 1) an upper bound on the size of the branch-and-bound tree using strong-branching as a function of the additive integrality gap; 2) show how the Nemhauser-Trotter property of persistency, which can be used as a pre-solve technique for vertex cover, is being recursively and consistently used throughout the strong-branching tree; 3) and finally provide an example of a vertex cover instance where not using strong-branching leads to a tree that has at least exponentially more nodes than the branch-and-bound tree based on strong-branching. On the negative side for strong-branching, we identify another class of instances where the strong-branching tree is exponentially larger than another branch-and-bound tree for solving these instances. On the computational side, we conduct experiments on various types of instances, like the lot-sizing problem and its variants, packing integer programs (IP), covering IPs, chance constrained IPs, vertex cover, etc., to understand how much larger is the size of the strong-branching based branch-and-bound tree in comparison to the optimal branch-and-bound tree. The main take-away from these experiments (on small instances) is that for all these instances the size of the strong-branching tree is within a factor of two of the size of the optimal branch-and-bound tree.
پارسال
در تاریخ 1402/02/12 منتشر شده
است.
305
بـار بازدید شده