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.
Révisé le :
Accepté le :
Publié le :
@article{OJMO_2022__3__A5_0,
author = {Hildebrand, Robert and K\"oppe, Matthias and Zhou, Yuan},
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 = {http://www.numdam.org/articles/10.5802/ojmo.16/}
}
TY - JOUR AU - Hildebrand, Robert AU - Köppe, Matthias AU - Zhou, Yuan 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 - http://www.numdam.org/articles/10.5802/ojmo.16/ DO - 10.5802/ojmo.16 LA - en ID - OJMO_2022__3__A5_0 ER -
%0 Journal Article %A Hildebrand, Robert %A Köppe, Matthias %A Zhou, Yuan %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 http://www.numdam.org/articles/10.5802/ojmo.16/ %R 10.5802/ojmo.16 %G en %F OJMO_2022__3__A5_0
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, Tome 3 (2022), article no. 5, 44 p. doi : 10.5802/ojmo.16. http://www.numdam.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 (Louveaux, Quentin; Skutella, Martin, 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 -Dimensional Case with Applications to , 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 (Lodi, Andrea; Nagarajan, Viswanath, 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 (Cerulli, Raffaele; Fujishige, Satoru; Mahjoub, A. Ridha, 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 (Eisenbrand, Friedrich; Koenemann, Jochen, 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
Cité par Sources :
