Brunel University Research Archive (BURA) >
College of Engineering, Design and Physical Sciences >
Dept of Mathematics >
Dept of Mathematics Research Papers >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/2326

Title: Zero-one IP problems: Polyhedral descriptions & cutting plane procedures
Authors: Abdul-Hamid, F
Mitra, G
Yarrow, L
Publication 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
URI: http://bura.brunel.ac.uk/handle/2438/2326
Appears in Collections:Mathematical Science
Dept of Mathematics Research Papers

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.