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):

Report Date:

1973-09-01

Pagination or Media Count:

28.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE