Springe direkt zu Inhalt

Lecture by Amitabh Basu (Johns Hopkins University Baltimore): Complexity of cutting plane and branch-and-bound algorithms

Jul 13, 2020 | 02:15 PM

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We focus on variables disjunctions and split disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by showing that there are instances of the stable set problem where CP does exponentially better than BB. We further show that if one moves away from 0/1 polytopes, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). Finally, we show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up). In the second part of the talk, we will discuss the conjecture that the split closure has polynomial complexity in fixed dimension, which has remained open for a while now even in 2 dimensions. We settle it affirmatively in two dimensions, and complement it with a polynomial time pure cutting plane algorithm for 2 dimensional IPs based on split cuts.

Time & Location

Jul 13, 2020 | 02:15 PM

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room MA 041 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)