Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations

Abstract

In this self-contained paper, we present a theory of the piecewise linear minimal valid functions for the 1-row Gomory-Johnson infinite group problem. The non-extreme minimal valid functions are those that admit effective perturbations. We give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The infinite-dimensional subspaces have partial symmetries; to describe them, we develop a theory of inverse semigroups of partial bijections, interacting with the functional equations satisfied by the perturbations. Our paper 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.

arXiv comment67 pages, 21 figures; v2: changes to sections 10.2-10.3, improved figures; v3: additional figures and minor updates, add reference to IPCO abstract. CC-BY-SA

References in corpus (9)

• 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
• An Electronic Compendium of Extreme Functions for the Gomory--Johnson Infinite Group Problem
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2
• On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem
• Toward computer-assisted discovery and automated proofs of cutting plane theorems
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case

Cited by in corpus (1)

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