On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2} |
| |
Authors: | Egon Balas Shu Ming Ng |
| |
Affiliation: | (1) Carnegie Mellon University, 15213 Pittsburgh, PA, USA;(2) University of Southern California, Los Angeles, CA, USA |
| |
Abstract: | In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities 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.The research underlying this report was supported by Grant ECS-8601660 of the National Science Foundation, Contract N00014-85-K-0198 with the Office of Naval Research, and Grant AFOSR-870292 of the Air Force Office of Scientific Research. |
| |
Keywords: | Set covering facet lifting polyhedral combinatorics |
本文献已被 SpringerLink 等数据库收录! |
|