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

Robert Hildebrand; Matthias K&#x00F6;ppe; Yuan Zhou

doi:10.1007/978-3-030-17953-3_19

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

Robert Hildebrand, Matthias Köppe, Yuan Zhou

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 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	https://doi.org/10.1007/978-3-030-17953-3_19
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)

Access to Document

10.1007/978-3-030-17953-3_19

Cite this

Hildebrand, R., Köppe, M., & Zhou, Y. (2019). On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem. In A. Lodi, & V. Nagarajan (Eds.), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings (pp. 247-260). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS). https://doi.org/10.1007/978-3-030-17953-3_19

Hildebrand, Robert ; Köppe, Matthias ; Zhou, Yuan. / On Perturbation Spaces of Minimal Valid Functions : Inverse Semigroup Theory and Equivariant Decomposition Theorem. Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. editor / Andrea Lodi ; Viswanath Nagarajan. 2019. pp. 247-260 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{027c68cb912947de92a57a64e09fb95d,

title = "On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem",

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.",

keywords = "Cutting planes, Group relaxations, Integer programs",

author = "Robert Hildebrand and Matthias Köppe and Yuan Zhou",

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.{\textquoteright}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: {\textcopyright} 2019, Springer Nature Switzerland AG.; null ; Conference date: 22-05-2019 Through 24-05-2019",

year = "2019",

doi = "10.1007/978-3-030-17953-3_19",

language = "English",

isbn = "9783030179526",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "247--260",

editor = "Andrea Lodi and Viswanath Nagarajan",

booktitle = "Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings",

}

Hildebrand, R, Köppe, M & Zhou, Y 2019, On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem. in A Lodi & V Nagarajan (eds), Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11480 LNCS, pp. 247-260, 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019, Ann Arbor, United States, 5/22/19. https://doi.org/10.1007/978-3-030-17953-3_19

On Perturbation Spaces of Minimal Valid Functions : Inverse Semigroup Theory and Equivariant Decomposition Theorem. / Hildebrand, Robert; Köppe, Matthias; Zhou, Yuan.

Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. ed. / Andrea Lodi; Viswanath Nagarajan. 2019. p. 247-260 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11480 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On Perturbation Spaces of Minimal Valid Functions

AU - Hildebrand, Robert

AU - Köppe, Matthias

AU - Zhou, Yuan

N1 - 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.

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Cutting planes

KW - Group relaxations

KW - Integer programs

UR - http://www.scopus.com/inward/record.url?scp=85065882795&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065882795&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-17953-3_19

DO - 10.1007/978-3-030-17953-3_19

M3 - Conference contribution

AN - SCOPUS:85065882795

SN - 9783030179526

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 247

EP - 260

BT - Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings

A2 - Lodi, Andrea

A2 - Nagarajan, Viswanath

Y2 - 22 May 2019 through 24 May 2019

ER -

Hildebrand R, Köppe M, Zhou Y. On Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup Theory and Equivariant Decomposition Theorem. In Lodi A, Nagarajan V, editors, Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings. 2019. p. 247-260. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17953-3_19

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this