Accession Number:

ADA196237

Title:

On the Set Covering Polytope. 2. Lifting the Facets with Coefficients in (0,1,2). Revision

Descriptive Note:

Management sciences research rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1988-03-01

Pagination or Media Count:

29.0

Abstract:

An earlier paper characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. This paper connects that characterization to the theory of facet lifting. In particular, a family of lower dimensional polytopes and associated inequalities is introduced having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions. Keywords MatricesMathematics.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE