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

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

Keywords

Cutting planes
Group relaxations
Integer programs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

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 = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 ; 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

T2 - 20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019

AU - Hildebrand, Robert

AU - Köppe, Matthias

AU - Zhou, Yuan

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