1 Presentation

• 
  02:00 PM - 03:00 PM

  Cutting planes and simple MIPs

  • Laurence Wolsey, presenter, Université catholique de Louvain

  Motivated by the problem of finding strong cutting planes and tight descriptions of the convex hulls of certain simple MIPs, we discuss two approaches to the analysis and/or solution of LPs and MIPs in which extended formulations and their projection into the original space of variables play a crucial role. First we show how some recent work on "facet" separation by a single LP is potentially relevant to the solution of the linear programs arising in Benders' algorithm and also in Dantzig-Wolfe decomposition. Secondly we consider a family of simple mixed-sets generalizing single-node flow models with constant capacities and show how one can derive explicit descriptions of the convex hull of solutions by i) deriving an extended formulation for the convex hull, ii) showing that the formulation is tight and iii) projecting back into the original space of variables using Fourier-Motzkin and induction to eliminate the variables.