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

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 then separate the three notions using discontinuous examples.

arXiv comment18 pages, 2 figures

References in corpus (4)

• Light on the Infinite Group Relaxation
• A Counterexample to a Conjecture of Gomory and Johnson
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2

Cited by in corpus (2)

• New computer-based search strategies for extreme functions of the Gomory--Johnson infinite group problem
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations