Facets of the Knapsack Polytope.
Management science research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
A necessary and sufficient condition is given for an inequality with coefficients 0 or 1 to define a facet of the knapsack polytope, i.e., of the convex hull of 0-1 points satisfying a given linear inequality. A sufficient condition is also established for a larger class of inequalities with coefficients not restricted to 0 and 1 to define a facet for the same polytope, and a procedure is given for generating all facets in the above two classes. The procedure can be viewed as a way of generating cutting planes for 0-1 programs. Author
- Operations Research