Please use this identifier to cite or link to this item:
Title: Zero-one IP problems: Polyhedral descriptions & cutting plane procedures
Authors: Abdul-Hamid, F
Mitra, G
Yarrow, L
Issue Date: 1994
Publisher: Brunel University
Citation: Maths Technical Papers (Brunel University). March 1994, pp 1-64
Series/Report no.: TR/03/94
Abstract: A systematic way for tightening an IP formulation is by employing classes of linear inequalities that define facets of the convex hull of the feasible integer points of the respective problems. Describing as well as identifying these inequalities will help in the efficiency of the LP-based cutting plane methods. In this report, we review classes of inequalities that partially described zero-one poly topes such as the 0-1 knapsack polytope, the set packing polytope and the travelling salesman polytope. Facets or valid inequalities derived from the 0-1 knapsack and the set packing polytopes are algorithmically identified
Appears in Collections:Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
TR_03_94.pdf494.97 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.