
Accession Number : AD0770600
Title : Facets of the Knapsack Polytope.
Descriptive Note : Management science research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas,Egon
Report Date : SEP 1973
Pagination or Media Count : 28
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 01 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 01 programs. (Author)
Descriptors : *Mathematical programming, *Convex sets, *Inequalities, Matrices(Mathematics), Theorems
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE