Brunel University Research Archive (BURA) >
Schools >
School of Information Systems, Computing and Mathematics >
Mathematics Technical 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:Mathematics Technical 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.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan