EUVIMEDSkopri EUVIMED
Crossref

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

Robert Hildebrand, Matthias Köppe, Yuan Zhou

Open Journal of Mathematical Optimization · 2022

DOI: 10.5802/ojmo.16 ↗

At a glance

Journal article in Open Journal of Mathematical Optimization, 2022. Written by Robert Hildebrand and 2 co-authors. 23 references.

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

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.

Cite

APA

Hildebrand, R., Köppe, M., & Zhou, Y. (2022). Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations. Open Journal of Mathematical Optimization. https://doi.org/10.5802/ojmo.16

Vancouver

Hildebrand R, Köppe M, Zhou Y. Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations. Open Journal of Mathematical Optimization. 2022. doi:10.5802/ojmo.16

BibTeX
@article{Hildebrand2022,
  author = {Hildebrand, Robert and Köppe, Matthias and Zhou, Yuan},
  title = {Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations},
  journal = {Open Journal of Mathematical Optimization},
  year = {2022},
  doi = {10.5802/ojmo.16}
}
Start for free →