Computing low-capacity 0–1 knapsack polytopes |
| |
| Authors: | P L Hammer U N Peled |
| |
| Institution: | (1) Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada;(2) Computer Science Department, Columbia University, 10027 New York, NY, USA |
| |
| Abstract: | A procedure is proposed that, given a linear inequalityL having positive integral coefficients in 0–1 variables, finds all the facets of the convex hull of the solutions ofL. This is done for allL by doing once and for all the computations for a particular sequenceM
1,M
2,... of such linear inequalities, called master knapsack problems. To find the facets for a givenL, it is enough to know the facets for the master knapsack problemM
b, whereb is the free term inL (no matter how many variablesL might have). ThisM
b has no more than order ofb logb variables. The procedure is based on polarity. All the facets forM
1,...,M
7 are tabulated.
Zusammenfassung Es wird ein Verfahren vorgestellt, das für eine lineare UngleichungL in binären Variablen mit positiven ganzzahligen Koeffizienten alle Facetten der konvexen Hülle der Lösungen vonL bestimmt. Um diese Facetten für irgendeine UngleichungL mit rechter Seiteb zu erhalten, braucht man nur die Facetten des sogenannten Master-Knapsack-ProblemsM
b zu kennen, dasO (b log b) Variablen besitzt. Fürb=1,..., 7 werden alle Facetten vonM
b angegeben. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
