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

doi:10.5802/ojmo.16

Robert Hildebrand ¹; Matthias Köppe ²; Yuan Zhou ³

¹ Grado Dept. of Industrial and Systems Engineering, Virginia Tech
² Dept. of Mathematics, University of California, Davis
³ Dept. of Mathematics, University of Kentucky

Open Journal of Mathematical Optimization, Volume 3 (2022), article no. 5, 44 p.

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.

Received: 2021-07-24
Revised: 2022-04-22
Accepted: 2022-08-21
Published online: 2022-09-06

DOI: 10.5802/ojmo.16

Author's affiliations:

Robert Hildebrand ¹; Matthias Köppe ²; Yuan Zhou ³

¹ Grado Dept. of Industrial and Systems Engineering, Virginia Tech
² Dept. of Mathematics, University of California, Davis
³ Dept. of Mathematics, University of Kentucky

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{OJMO_2022__3__A5_0,
     author = {Robert Hildebrand and Matthias K\"oppe and Yuan Zhou},
     title = {Equivariant {Perturbation} in {Gomory} and {Johnson{\textquoteright}s} {Infinite} {Group} {Problem.} {VII.} {Inverse} {Semigroup} {Theory,} {Closures,} {Decomposition} of {Perturbations}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {5},
     pages = {1--44},
     publisher = {Universit\'e de Montpellier},
     volume = {3},
     year = {2022},
     doi = {10.5802/ojmo.16},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/}
}

TY  - JOUR
AU  - Robert Hildebrand
AU  - Matthias Köppe
AU  - Yuan Zhou
TI  - Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations
JO  - Open Journal of Mathematical Optimization
PY  - 2022
SP  - 1
EP  - 44
VL  - 3
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/
DO  - 10.5802/ojmo.16
LA  - en
ID  - OJMO_2022__3__A5_0
ER  -

%0 Journal Article
%A Robert Hildebrand
%A Matthias Köppe
%A Yuan Zhou
%T Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations
%J Open Journal of Mathematical Optimization
%D 2022
%P 1-44
%V 3
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/
%R 10.5802/ojmo.16
%G en
%F OJMO_2022__3__A5_0

Robert Hildebrand; Matthias Köppe; Yuan Zhou. Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations. Open Journal of Mathematical Optimization, Volume 3 (2022), article  no. 5, 44 p. doi : 10.5802/ojmo.16. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.16/

References
Cited by

[1] Amitabh Basu; Michele Conforti; Gérard Cornuéjols; Giacomo Zambelli A Counterexample to a Conjecture of Gomory and Johnson, Math. Program., Ser. A, Volume 133 (2012) no. 1–2, pp. 25-38 | DOI | MR | Zbl

[2] Amitabh Basu; Michele Conforti; Marco Di Summa; Joseph Paat Extreme Functions with an Arbitrary Number of Slopes, Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1–3, 2016, Proceedings (Quentin Louveaux; Martin Skutella, eds.), Springer, 2016, pp. 190-201 | DOI | Zbl

[3] Amitabh Basu; Robert Hildebrand; Matthias Köppe Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. I. The One-Dimensional Case, Math. Oper. Res., Volume 40 (2014) no. 1, pp. 105-129 | DOI | MR | Zbl

[4] Amitabh Basu; Robert Hildebrand; Matthias Köppe Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case, 2016 (Manuscript) | Zbl

[5] Amitabh Basu; Robert Hildebrand; Matthias Köppe Light on the infinite group relaxation I: foundations and taxonomy, 4OR, Volume 14 (2016) no. 1, pp. 1-40 | DOI | MR | Zbl

[6] Amitabh Basu; Robert Hildebrand; Matthias Köppe Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms, 4OR, Volume 14 (2016) no. 2, pp. 107-131 | DOI | MR | Zbl

[7] Amitabh Basu; Robert Hildebrand; Matthias Köppe Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem—III: Foundations for the $k$ -Dimensional Case with Applications to $k = 2$ , Math. Program., Volume 163 (2017) no. 1, pp. 301-358 | DOI | MR | Zbl

[8] Santanu S. Dey; Jean-Philippe P. Richard; Yanjun Li; Lisa A. Miller On the extreme inequalities of infinite group problems, Math. Program., Volume 121 (2010) no. 1, pp. 145-170 | DOI | MR | Zbl

[9] Marco Di Summa Piecewise smooth extreme functions are piecewise linear, Math. Program., Volume 179 (2020) no. 1, pp. 265-293 | DOI | MR | Zbl

[10] Ralph E. Gomory Some Polyhedra related to Combinatorial Problems, Linear Algebra Appl., Volume 2 (1969), pp. 451-558 | DOI | MR | Zbl

[11] Ralph E. Gomory; Ellis L. Johnson Some continuous functions related to corner polyhedra, I, Math. Program., Volume 3 (1972), pp. 23-85 | DOI | MR | Zbl

[12] Ralph E. Gomory; Ellis L. Johnson Some continuous functions related to corner polyhedra, II, Math. Program., Volume 3 (1972), pp. 359-389 | DOI | MR | Zbl

[13] Robert Hildebrand On Polyhedral Subdivisions Closed Under Group Operations (2013) (Manuscript)

[14] Robert Hildebrand; Matthias Köppe; Yuan Zhou On perturbation spaces of minimal valid functions: Inverse semigroup theory and equivariant decomposition theorem, Integer Programming and Combinatorial Optimization. IPCO 2019 (Andrea Lodi; Viswanath Nagarajan, eds.) (Lecture Notes in Computer Science), Volume 11480, Springer, 2019, pp. 247-260 | DOI | MR | Zbl

[15] Robert Hildebrand; Matthias Köppe; Yuan Zhou Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VIII. Grid-free Extremality Test—General Algorithm and Implementation (2021) (Manuscript)

[16] Chun Yu Hong; Matthias Köppe; Yuan Zhou Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem (V). Software for the continuous and discontinuous 1-row case, Optim. Methods Softw., Volume 33 (2018) no. 3, pp. 475-498 | DOI | MR | Zbl

[17] Matthias Köppe; Yuan Zhou An electronic compendium of extreme functions for the Gomory–Johnson infinite group problem, Oper. Res. Lett., Volume 43 (2015) no. 4, pp. 438-444 | DOI | MR | Zbl

[18] Matthias Köppe; Yuan Zhou Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems, Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16–18, 2016, Revised Selected Papers (Raffaele Cerulli; Satoru Fujishige; A. Ridha Mahjoub, eds.), Springer, 2016, pp. 332-344 | DOI | Zbl

[20] Matthias Köppe; Yuan Zhou Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Minimal Valid Functions, Discrete Optim., Volume 30 (2018), pp. 51-72 | DOI | MR | Zbl

[21] Matthias Köppe; Yuan Zhou; Chun Yu Hong; Jiawei Wang cutgeneratingfunctionology: Python code for computation and experimentation with cut-generating functions, https://github.com/mkoeppe/cutgeneratingfunctionology, 2020 (Version 1.5) | DOI

[22] Mark V. Lawson Inverse Semigroups: The Theory of Partial Symmetries, World Scientific, 1998 | DOI

[23] Yuan Zhou Infinite-Dimensional Relaxations of Mixed-Integer Optimization Problems, Ph. D. Thesis, University of California, Davis, Graduate Group in Applied Mathematics (2017) https://search.proquest.com/docview/1950269648

Cited by Sources: