Accession Number : AD0770600

Title :   Facets of the Knapsack Polytope.

Descriptive Note : Management science research rept.,

Corporate Author : CARNEGIE-MELLON 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 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)

Descriptors :   *Mathematical programming, *Convex sets, *Inequalities, Matrices(Mathematics), Theorems

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE