Light on the Infinite Group Relaxation
arXiv:1410.8584 · doi:10.1007/s10288-015-0292-9 10.1007/s10288-015-0293-8
Abstract
This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled "Some continuous functions related to corner polyhedra I, II" [Math. Programming 3 (1972), 23-85, 359-389]. The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general k >= 1 that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.
45 pages
References in corpus (8)
- 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
- Unique lifting of integer variables in minimal inequalities
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
- An Electronic Compendium of Extreme Functions for the Gomory--Johnson Infinite Group Problem
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two-Dimensional Case
- New computer-based search strategies for extreme functions of the Gomory--Johnson infinite group problem
Cited by in corpus (8)
- 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
- 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