infinite group relaxation

A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Semi-infinite Programming Tags , , ,

    We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornu\’ejols and Molinaro for k=2. ArticleDownload View PDF

    Two Row Mixed Integer Cuts Via Lifting

  • Santanu S. Dey
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags ,

    Recently, Andersen et al.(2007), Borozan and Cornuejols (2007) and Cornuejols and Margot(2007) characterized extreme inequalities of a system of two rows with two free integer variables and nonnegative continuous variables. These inequalities are either split cuts or intersection cuts (Balas (1971)) derived using maximal lattice-free convex sets. In order to use these inequalities to obtain … Read more