Abstract
The non-extreme minimal valid functions for the Gomory–Johnson infinite group problem are those that admit effective perturbations. For a class of piecewise linear functions for the 1-row problem 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 testing extremality and for computing liftings of non-extreme functions. The grid-freeness makes the algorithms suitable for piecewise linear functions whose breakpoints are rational numbers with huge denominators.
Original language | English |
---|---|
Title of host publication | Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings |
Editors | Andrea Lodi, Viswanath Nagarajan |
Pages | 247-260 |
Number of pages | 14 |
DOIs | |
State | Published - 2019 |
Event | 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States Duration: May 22 2019 → May 24 2019 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11480 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 |
---|---|
Country/Territory | United States |
City | Ann Arbor |
Period | 5/22/19 → 5/24/19 |
Bibliographical note
Funding Information:The authors wish to thank C.Y. Hong, who worked on a first grid-free implementation in 2013, and Q. Louveaux and R. La Haye for valuable discussions during 2013/14. A preliminary version of the development in this paper appeared in Y.Z.’s 2017 Ph.D. thesis [14]. The authors gratefully acknowledge partial support from the National Science Foundation through grants DMS-0914873 (R.H., M.K.) and DMS-1320051 (M.K., Y.Z.) Part of this work was done while R.H. and M.K. were visiting the Simons Institute for the Theory of Computing in Fall 2017. It was partially supported by the DIMACS/Si-mons Collaboration on Bridging Continuous and Discrete Optimization through NSF grant CCF-1740425.
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
Keywords
- Cutting planes
- Group relaxations
- Integer programs
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)