Optimization Online


Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

Matthias Köppe (mkoeppe***at***math.ucdavis.edu)
Yuan Zhou (yzh***at***math.ucdavis.edu)

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. This anomalous behavior results from combining features of Hildebrand's two-sided discontinuous extreme functions and Basu--Hildebrand--Koeppe's piecewise linear extreme function with irrational breakpoints. The new function only admits piecewise microperiodic perturbations. We present an algorithm for computations with a restricted class of such perturbations.

Keywords: Integer programming, cutting planes, group relaxations

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 05/13/2016
Entry Accepted: 05/13/2016
Entry Last Modified: 02/05/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society