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 |
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 |
URI: | http://bura.brunel.ac.uk/handle/2438/2326 |
Appears in Collections: | Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
TR_03_94.pdf | 494.97 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.