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

2019/11/14 by Matthias Köppe, Yuan Zhou, Köppe, Matthias +1 · 1 voice
Mathematics · #90C10 #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:90C10

paper · pdf · doi:10.48550/arxiv.1911.06199

25+32 pages, 5 figures. Journal version of published extended abstract arXiv:1611.06626

arxiv created 2019/11/14 · arxiv published 2019/11/14 · arxiv updated 2019/11/15

Abstract

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 prove an if-and-only-if version of the Gomory-Johnson Facet Theorem. Finally, we separate the three notions using discontinuous examples.

Citations

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

Discussions

• In https://arxiv.org/abs/1911.06199, an extended version of an IPCO 2017 paper w/ Yuan Zhou @universityofky (http://www.ms.uky.edu/~yzh392/), we investigate 3 generalizations of the notion of a facet [bsky, 0 points, 1 comments]

Related

• All Cyclic Group Facets Inject
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The curious case of two-sided discontinuous minimal valid functions
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations
• An Electronic Compendium of Extreme Functions for the Gomory--Johnson Infinite Group Problem