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