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

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: Matrices(Mathematics).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1988
Accession Number
ADA196237

Entities

People

  • Egon Balas
  • Shu M. Ng

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Air Force
  • California
  • Coefficients
  • Coverings
  • Governments
  • Guarantees
  • Identities
  • Inequalities
  • Mathematics
  • Optimization
  • Permutations
  • Schools
  • Scientific Research
  • Sequences
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.