group relaxations

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

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

We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. CitationAn 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 2016ArticleDownload View PDF