Generating Fenchel Cutting Planes for Knapsack Polyhedra

The author recently proposed a class of cutting planes for integer programs called Fenchel cuts which distinguish themselves from more conventional cuts in that they are generated by directly seeking to solve the separation problem rather than by using explicit knowledge of the polyhedral structure of the integer program. An algorithm for generating Fenchel cuts is presented and described in detail for the separation problem associated with knapsack polyhedra. Computational results are presented for a collection of real-world integer programs to demonstrate the effectiveness of the cutting planes.