Optimization Online


Linear Programming Based Lifting and its Application to Primal Cutting Plane Algorithms

Santanu Dey (sdey***at***purdue.edu)
Jean-Philippe Richard (jprichar***at***ecn.purdue.edu)

Abstract: We propose an approximate lifting procedure for general integer programs. This lifting procedure uses information from multiple constraints of the problem formulation and can be used to strengthen formulations and cuts for mixed integer programs. In particular we demonstrate how it can be applied to improve Gomory's fractional cut which is central to Glover's primal cutting plane algorithm. We show that the resulting algorithm is finitely convergent. We also present numerical results that illustrate the computational benefits of the proposed lifting procedure.

Keywords: Integer Programming; Cutting Planes; Primal Algorithm

Category 1: Integer Programming (Cutting Plane Approaches )

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



Entry Submitted: 06/10/2006
Entry Accepted: 06/12/2006
Entry Last Modified: 04/06/2008

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 Programming Society