Facets of some combinatorial polytopes

Abstract

A proven approach for solving hard combinatorial optimization problems is via polyhedral methods applied to integer programming formulations. Efficient algorithms for such problems are often problem specific and exploit the structure of the problem at hand. This motivates the study of combinatorial polytopes. This thesis is a collection of results on the facial structure of polytopes associated with four problems related to optimal packing and covering. The results we have are; 1 . A characterization of all the facets of the Set Covering Polytope with {0,1} coefficients on the left-hand-side of the corresponding inequalities. 2. A from-scratch proof of the minimal implicit representation of the Edge Cover Polytope. 3. The minimal implicit representation of the Cardinality Constrained Matching Polytope. 4. A characterization of the fractional polytope of the fc-Red Matching Problem.