On the 0,1 Facets of the Set Covering Polytope.

Abstract

This paper considers inequalities of a certain form where alpha sub j equals 0 or 1, and beta is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated to a 0,1 constraint matrix A. These conditions are in terms of critical edges and critical cutsets defined in the bipartitie incidence graph associated to A, and are very much in the spirit of the work of Balas and Zemal on the set packing problem where similar notions were defined in the intersection graph of A. Furthermore, we give a polynomial characterization of a class of 0,1 facets defined from chorded cycles induced in the bipartitie indicence graph. This characterization also yields all the 0,1 liftings of odd-hole inequalities for the sample plant location polytope.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1986
Accession Number
ADA174478

Entities

People

  • A. Sassano
  • G. Cornuejols

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Computer Programming
  • Coverings
  • Crossings
  • Inequalities
  • Mathematical Programming
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Polynomials
  • Schools
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.