Facets of the Knapsack Polytope from Minimal Covers.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
In this paper the authors give easily computable best upper and lower bounds on the coefficients of facets of the knapsack polytope associated with minimal covers. For some coefficients the upper bounds are equal to the lower bounds for the others the two bounds differ by 1. A necessary and sufficient condition is given for all lower bounds to be equal to the corresponding upper bounds, i.e. for the facet associated with the given minimal cover to be unique. Also, a partial order is defined on the set of minimal covers and it is shown that all facets associated with minimal covers can be obtained from weak covers but that each facet obtainable from several ordered minimal covers is easiest to compute from the strongest one.
- Operations Research