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

Santanu Dey (sdeypurdue.edu)
Jean-Philippe Richard (jpricharecn.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 )

Citation:

Download:

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

Modify/Update this entry