Optimization Online


Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2

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

Abstract: We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy's additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain additivity relations. (2) We study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. (3) We give a theory of non-extremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under the assumption of a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function.

Keywords: Group relaxation, infinite group problem, extreme functions

Category 1: Integer Programming (Cutting Plane Approaches )

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


Download: [PDF]

Entry Submitted: 03/18/2014
Entry Accepted: 03/18/2014
Entry Last Modified: 03/18/2014

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