Equivariant perturbation in Gomory and Johnson's infinite group problem. VI. The curious case of two-sided discontinuous minimal valid functions

Matthias Köppe, Yuan Zhou

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 languageEnglish
Pages (from-to)51-72
Number of pages22
JournalDiscrete Optimization
Volume30
DOIs
StatePublished - Nov 2018

Bibliographical note

Funding Information:
The authors gratefully acknowledge partial support from the National Science Foundation through grant DMS-1320051 , awarded to M. Köppe.

Publisher Copyright:
© 2018 Elsevier B.V.

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