BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We present some results on the theoretical complexity of branc
 h-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimi
 zation. 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 foc
 us 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 example
 s where BB finishes in O(1) time\, but CP takes infinitely long to prove op
 timality\, and exponentially long to get to arbitrarily close to the optima
 l value (for variable disjunctions). Finally\, we show that if the dimensio
 n 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 polyno
 mial complexity in fixed dimension\, which has remained open for a while no
 w even in 2 dimensions. We settle it affirmatively in two dimensions\, and 
 complement it with a polynomial time pure cutting plane algorithm for 2 dim
 ensional IPs based on split cuts. 
DTSTAMP:20200622T161800
DTSTART:20200713T141500
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
 es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Amitabh Basu (Johns Hopkins University Baltimore): Complexity of cu
 tting plane and branch-and-bound algorithms - cancelled
UID:106025411@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200713-L-Basu.html
END:VEVENT
END:VCALENDAR