Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations
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 perturbatio...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2022-09-01
|
| Series: | Open Journal of Mathematical Optimization |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2777-5860 |