Journal
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2019
Volume 11480, Issue -, Pages 247-260Publisher
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-030-17953-3_19
Keywords
Integer programs; Cutting planes; Group relaxations
Categories
Funding
- National Science Foundation [DMS-0914873, DMS-1320051]
- DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization through NSF [CCF-1740425]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available