Abstract
We construct a two-sided discontinuous piecewise linear minimal valid cut-generating function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. The new function only admits piecewise microperiodic perturbations. We present an algorithm for verifying certificates of non-extremality in the form of such perturbations.
| Original language | English |
|---|---|
| Pages (from-to) | 51-72 |
| Number of pages | 22 |
| Journal | Discrete Optimization |
| Volume | 30 |
| DOIs | |
| State | Published - Nov 2018 |
Bibliographical note
Publisher Copyright:© 2018 Elsevier B.V.
Funding
The authors gratefully acknowledge partial support from the National Science Foundation through grant DMS-1320051 , awarded to M. Köppe.
| Funders | Funder number |
|---|---|
| National Science Foundation Arctic Social Science Program | DMS-1320051 |
Keywords
- Cut-generating functions
- Cutting planes
- Group relaxations
- Integer programs
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics
- Applied Mathematics
Fingerprint
Dive into the research topics of 'Equivariant perturbation in Gomory and Johnson's infinite group problem. VI. The curious case of two-sided discontinuous minimal valid functions'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver