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

doi:10.1016/j.disopt.2018.05.003

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

Mathematics

Research output: Contribution to journal › Article › peer-review

4 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 language	English
Pages (from-to)	51-72
Number of pages	22
Journal	Discrete Optimization
Volume	30
DOIs	https://doi.org/10.1016/j.disopt.2018.05.003
State	Published - 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

Access to Document

10.1016/j.disopt.2018.05.003

Cite this

@article{2eb208e273ad4b60a1cb0c59f7b5ba9f,

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

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

keywords = "Cut-generating functions, Cutting planes, Group relaxations, Integer programs",

author = "Matthias K{\"o}ppe and Yuan Zhou",

note = "Funding Information: The authors gratefully acknowledge partial support from the National Science Foundation through grant DMS-1320051 , awarded to M. K{\"o}ppe. Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = nov,

doi = "10.1016/j.disopt.2018.05.003",

language = "English",

volume = "30",

pages = "51--72",

}

TY - JOUR

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

AU - Köppe, Matthias

AU - Zhou, Yuan

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

PY - 2018/11

Y1 - 2018/11

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

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

KW - Cut-generating functions

KW - Cutting planes

KW - Group relaxations

KW - Integer programs

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

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

U2 - 10.1016/j.disopt.2018.05.003

DO - 10.1016/j.disopt.2018.05.003

M3 - Article

AN - SCOPUS:85049354947

SN - 1572-5286

VL - 30

SP - 51

EP - 72

JO - Discrete Optimization

JF - Discrete Optimization

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this