Fenchel Cutting Planes for Linear Integer Programming Problems
Boyd, E. Andrew
The author recently introduced a new 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 through the use of explicit knowledge of the polyhedral structure of the integer program. The theory of Fenchel cuts is outlined and their polyhedral characteristics are briefly discussed. A general algorithm for generating Fenchel cuts is described and an instantiation of this algorithm is then presented for the separation problem associated with knapsack polyhedra. The paper concludes by provably optimizing a linear function over the intersection of the knapsack polyhedra defined by individual constraints in a collection of integer programs first introduced by Crowder, Johnson, and Padberg.
Citable link to this pagehttps://hdl.handle.net/1911/101685
MetadataShow full item record
- CAAM Technical Reports