Facets of the Knapsack Polytope.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1973
- Accession Number
- AD0770600
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University