Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
arXiv:1206.2079 · doi:10.1287/moor.2014.0660
Abstract
We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We also present an extreme function that is a piecewise linear function with some irrational breakpoints, whose extremality follows from a new principle.
38 pages, 10 figures
References in corpus (5)
- Maximal lattice-free convex sets in linear subspaces
- Minimal inequalities for an infinite relaxation of integer programs
- A Counterexample to a Conjecture of Gomory and Johnson
- On the Relative Strength of Split, Triangle and Quadrilateral Cuts
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two-Dimensional Case
Cited by in corpus (11)
- Light on the Infinite Group Relaxation
- A geometric approach to cut-generating functions
- An Electronic Compendium of Extreme Functions for the Gomory--Johnson Infinite Group Problem
- New computer-based search strategies for extreme functions of the Gomory--Johnson infinite group problem
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2
- Software for cut-generating functions in the Gomory--Johnson model and beyond
- On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem
- Toward computer-assisted discovery and automated proofs of cutting plane theorems
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations
- Structure and Interpretation of Dual-Feasible Functions
- Characterization and Approximation of Strong General Dual Feasible Functions