A current research trend to find strong cutting planes is to consider certain infinite-dimensional relaxations of finite-dimensional optimization problems, which lead to so-called cut-generating functions, a term introduced by Cornuejols. The classical model in this context is the Gomory–Johnson infinite group problem, introduced by Ralph Gomory and Ellis Johnson in their seminal papers titled "Some continuous functions related to corner polyhedra I, II" [Math. Programming 3 (1972), 23–85, 359–389].
All integer linear programs with a fixed number k of rows and given right-hand side vector f are embedded into one infinite group problem in a function space. One then studies the convex geometry of this infinite-dimensional relaxation.
The goal of standard polyhedral combinatorics in the finite-dimensional case is to classify the facet-defining inequalities, which are the strongest inequalities among all tight valid inequalities. Likewise, in the infinite-dimensional case, we are interested in classifying all extreme functions, which are strongest among all minimal valid functions.
This software implements an automated extremality test for piecewise linear functions (which are allowed to be discontinuous) and contains an electronic compendium of extreme functions (with Yuan Zhou).
In this paper, 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 Cornuejols and Molinaro for k=2.
In this series of papers, we give the first algorithms for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) and establish the precise relation between the infinite group problem and its finite-dimensional restrictions.
Part I gives an algorithm for the case of piecewise linear functions with rational breakpoints and introduces a function with irrational breakpoints whose extremality proof depends on a new principle.
Part II and Part III are about the unimodular two-dimensional case.
Part V: Software for the continuous and discontinuous 1-row case describes our software. (An extended abstract appeared under the title Software for cut generating functions in the Gomory-Johnson model and beyond in Proc. International Congress on Mathematical Software 2016.)
Part VI: The Curious Case of Two-Sided Discontinuous Functions is a step towards a complete grid-free extremality test for the one-dimensional case.
Part VII: Inverse semigroup theory, closures, decomposition of perturbations provides the foundation for grid-free algorithms for the Gomory-Johnson model, in particular for testing extremality of piecewise linear functions whose breakpoints are rational numbers with huge denominators. (An extended abstract of 12 pages appeared in Proc. IPCO 2019, the 20th Conference on Integer Programming and Combinatorial Optimization, Ann Arbor, Michigan.)
In this note we announce the availability of an electronic compendium of extreme functions for Gomory–Johnson's infinite group problem. These functions serve as the strongest cut-generating functions for integer linear optimization problems.
We also close several gaps in the literature.
Data set: polyhedra whose vertices are extreme functions for Gomory's cyclic master group problem
Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting plane theorems in Gomory–Johnson’s model of cut generating functions.
We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing the hypothesis regarding rational breakpoints. We then separate the three notions using discontinuous examples.
We give a variant of Basu-Hildebrand-Molinaro's approximation theorem for continuous minimal valid functions for Gomory-Johnson's infinite group problem by piecewise linear two-slope extreme functions. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/qℤ for some q∈ℕ) and that take rational values at the breakpoints. In contrast to Basu et al.'s construction, our construction preserves all function values on 1/qℤ. As a corollary, we obtain that every extreme function for the finite group problem on 1/qℤ is the restriction of a continuous piecewise linear two-slope extreme function for the infinite group problem with breakpoints on a refinement 1/(Mq)ℤ for some M∈ℕ. In combination with Gomory's master theorem, this shows that the infinite group problem is the correct master problem for facets (extreme functions) of 1-row group relaxations.
