zbMATH — the first resource for mathematics

Generating Fenchel cutting planes for knapsack polyhedra. (English) Zbl 0797.90067
Recently, the author proposed a class of cutting planes for integer programs called Fenchel cuts. This cuts are generated by directly seeking to solve the separation problem rather than by using explicit knowledge of the polyhedral structure of the integer program. This paper is focused on the specific problem of generating Fenchel cuts for knapsack polyhedra. The algorithm described is tested by applying it to a set of 0/1 integer programs studied by Crowder, Johnson, and Padberg.
Reviewer: J.Terno (Dresden)

90C10 Integer programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C09 Boolean programming
PDF BibTeX Cite
Full Text: DOI