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 , , , Short URL: https://optimization-online.org/?p=11725

    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.

    Article

    Download

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