Name
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-17953-3_19 | INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2019 |
Keywords | Field | DocType |
Integer programs, Cutting planes, Group relaxations | Discrete mathematics,Rational number,Infinite group,Equivariant map,Inverse semigroup,Computer science,Direct sum,Pure mathematics,Linear subspace,Piecewise linear function,Functional equation | Conference |
Volume | ISSN | Citations |
11480 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Hildebrand | 1 | 69 | 7.82 |
| Matthias KöPpe | 2 | 191 | 20.95 |
| Yuan Zhou | 3 | 19 | 3.16 |