Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The curious case of two-sided discontinuous minimal valid functions

2016/05/12 by Matthias Köppe, Yuan Zhou, Köppe, Matthias +1
Computer Science · Mathematics · #Advanced Operator Algebra Research #Geometric and Algebraic Topology #Topological and Geometric Data Analysis #math.OC #msc:90C10

paper · pdf · doi:10.48550/arxiv.1605.03975

28 pages, 5 figures. v3: corrected Thm. 3.1, lemma in App. B, and proof of Thm. 5.1

arxiv created 2018/02/04 · arxiv updated 2018/02/06

Abstract

We construct a two-sided discontinuous piecewise linear minimal valid 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 computations with a restricted class of such perturbations.

Related

• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. IV. The General Unimodular Two-Dimensional Case
• Facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem
• All Cyclic Group Facets Inject