2018 Optimization Days

HEC Montréal, Québec, Canada, May 7 — 9, 2018

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WBP L.A. Wolsey

May 9, 2018 02:00 PM – 03:00 PM

Location: Plenaries - Amphithéâtre Banque Nationale

Chaired by Andrea Lodi

1 Presentation

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.