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

2018/11/15 by Robert Hildebrand, Matthias Köppe, Yuan Zhou · 1 voice
Mathematics · #math.OC

paper · pdf · doi:10.5802/ojmo.16

arxiv published 2018/11/15 · arxiv updated 2020/01/03

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.

Discussions

• Posted on https://arxiv.org/abs/1811.06189v3: "Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations" (with @ [bsky, 0 points, 1 comments]

Related

• 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. V. Software for the continuous and discontinuous 1-row case
• All Cyclic Group Facets Inject
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case
• Facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem