On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem

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 … Read more

Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more

Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case

We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. Citation An extended abstract of 8 pages appeared under the title “Software for cut-generating functions in the Gomory–Johnson model and beyond” in Proc. International Congress on Mathematical Software 2016 Article Download View Equivariant … Read more

Toward computer-assisted discovery and automated proofs of cutting plane theorems

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. Citation to be presented at ISCO 2016 Article Download View Toward computer-assisted discovery and automated proofs of cutting plane theorems

New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. Article Download View New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

An electronic compendium of extreme functions for the Gomory–Johnson infinite group problem

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. Article Download View An electronic compendium of extreme functions for the Gomory–Johnson infinite group problem