The Lagrangian and Other Primal Cutting Planes for Linear Integer Programming Problems
Cutting plane methods and Lagrangian relaxation have both proven to be powerful methods in the solution of integer programs. The purpose of this paper is to interpret Lagrangian relaxation as a cutting plane technique and to develop a related cutting plane technique that generates cuts with very different characteristics than those generated by the Lagrangian. Both classes of cuts differ from more conventional cuts in that they are based on optimization rather than explicit knowledge of the underlying polyhedral structure of the integer program. The theoretical strength of each type of cut is developed in detail, the computational efficiency of the two techniques is discussed, and computational results are presented.
Citable link to this pagehttps://hdl.handle.net/1911/101669
MetadataShow full item record
- CAAM Technical Reports