Journées de l'optimisation 2018

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

Horaire Auteurs Mon horaire

WBP L.A. Wolsey

9 mai 2018 14h00 – 15h00

Salle: Pléniers - Amphithéâtre Banque Nationale

Présidée par Andrea Lodi

1 présentation

  • 14h00 - 15h00

    Cutting planes and simple MIPs

    • Laurence Wolsey, prés., 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.

Retour