On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem

Robert Hildebrand, Matthias Köppe, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

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 languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
EditorsAndrea Lodi, Viswanath Nagarajan
Pages247-260
Number of pages14
DOIs
StatePublished - 2019
Event20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States
Duration: May 22 2019May 24 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11480 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Country/TerritoryUnited States
CityAnn Arbor
Period5/22/195/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)

Fingerprint

Dive into the research topics of 'On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem'. Together they form a unique fingerprint.

Cite this