« search calendars« CRM/DIMACS Workshop on Mixed-Integer Nonlinear Programming

« Complexity of Branch-and-bound and Cutting Plane Algorithms

Complexity of Branch-and-bound and Cutting Plane Algorithms

October 10, 2019, 2:00 PM - 3:00 PM


Auditorium (Amphitheatre Banque Nationale)

HEC Montreal

Cote-Sainte-Catherine Building

Click here for map.

Amitabh Basu, Johns Hopkins University

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on variable disjunctions. 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.