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!
|
| _version_ | 1825205008458579968 |
|---|---|
| author | Hildebrand, Robert Köppe, Matthias Zhou, Yuan |
| author_facet | Hildebrand, Robert Köppe, Matthias Zhou, Yuan |
| author_sort | Hildebrand, Robert |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a860777813a94ca5b0da03a68979eb08 |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2022-09-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-a860777813a94ca5b0da03a68979eb082025-02-07T14:02:43ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602022-09-01314410.5802/ojmo.1610.5802/ojmo.16Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of PerturbationsHildebrand, Robert0Köppe, Matthias1Zhou, Yuan2Grado Dept. of Industrial and Systems Engineering, Virginia TechDept. of Mathematics, University of California, DavisDept. of Mathematics, University of KentuckyIn 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.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/ |
| spellingShingle | Hildebrand, Robert Köppe, Matthias Zhou, Yuan Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations Open Journal of Mathematical Optimization |
| title | Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations |
| title_full | Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations |
| title_fullStr | Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations |
| title_full_unstemmed | Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations |
| title_short | Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations |
| title_sort | equivariant perturbation in gomory and johnson s infinite group problem vii inverse semigroup theory closures decomposition of perturbations |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/ |
| work_keys_str_mv | AT hildebrandrobert equivariantperturbationingomoryandjohnsonsinfinitegroupproblemviiinversesemigrouptheoryclosuresdecompositionofperturbations AT koppematthias equivariantperturbationingomoryandjohnsonsinfinitegroupproblemviiinversesemigrouptheoryclosuresdecompositionofperturbations AT zhouyuan equivariantperturbationingomoryandjohnsonsinfinitegroupproblemviiinversesemigrouptheoryclosuresdecompositionofperturbations |