TY - JOUR

T1 - Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations

AU - Hildebrand, Robert

AU - Köppe, Matthias

AU - Zhou, Yuan

N1 - Publisher Copyright:
© Robert Hildebrand & Matthias Köppe & Yuan Zhou.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85143144129&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85143144129&partnerID=8YFLogxK

U2 - 10.5802/ojmo.16

DO - 10.5802/ojmo.16

M3 - Article

AN - SCOPUS:85143144129

VL - 3

JO - Open Journal of Mathematical Optimization

JF - Open Journal of Mathematical Optimization

M1 - 16

ER -