Optimization Online


Light on the Infinite Group Relaxation

Amitabh Basu (basu.amitabh***at***jhu.edu)
Robert Hildebrand (robert.hildebrand***at***ifor.math.ethz.ch)
Matthias Koeppe (mkoeppe***at***math.ucdavis.edu)

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.

Keywords: cutting planes; cut-generating functions; minimal and extreme functions; integer programming; infinite group problem

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

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


Download: [PDF]

Entry Submitted: 10/30/2014
Entry Accepted: 10/31/2014
Entry Last Modified: 06/04/2015

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