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.

Revised:

Accepted:

Published online:

^{1}; Matthias Köppe

^{2}; Yuan Zhou

^{3}

@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/

[1] 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] 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] 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] Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case, 2016 (Manuscript) | Zbl

[5] Light on the infinite group relaxation I: foundations and taxonomy, 4OR, Volume 14 (2016) no. 1, pp. 1-40 | DOI | MR | Zbl

[6] 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] 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] On the extreme inequalities of infinite group problems, Math. Program., Volume 121 (2010) no. 1, pp. 145-170 | DOI | MR | Zbl

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

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

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

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

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

[14] 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] Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VIII. Grid-free Extremality Test—General Algorithm and Implementation (2021) (Manuscript)

[16] 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] 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] 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

[19] On the Notions of Facets, Weak Facets, and Extreme Functions of the Gomory–Johnson Infinite Group Problem, Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26–28, 2017, Proceedings (Friedrich Eisenbrand; Jochen Koenemann, eds.), Springer, 2017, pp. 330-342 | DOI | Zbl

[20] 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] cutgeneratingfunctionology: Python code for computation and experimentation with cut-generating functions, https://github.com/mkoeppe/cutgeneratingfunctionology, 2020 (Version 1.5) | DOI

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

[23] 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: *