Fenchel Cutting Planes for Integer Programs

A technique for generating cutting planes for integer programs is introduced that is based on the ability to optimize a linear function on a polyhedron rather than explicit knowledge of the underlying polyhedral structure of the integer program. The theoretical properties of the cuts and their relationship to Lagrangian relaxation are discussed, the cut generation procedure is described, and computational results are presented.