Optimization Online


Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem

Amitabh Basu(abasu***at***math.ucdavis.edu)
Robert Hildebrand(rhildebrand***at***ucdavis.edu)
Matthias Koeppe(mkoeppe***at***math.ucdavis.edu)

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.

Keywords: Integer Programming, Infinite Group Problem, Cutting Planes

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

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 06/10/2012
Entry Accepted: 06/11/2012
Entry Last Modified: 06/10/2012

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