A polyhedral approach to designing communication networks.

Abstract

Polytopes $Q\sbsp{2E}{n}$ and $Q\sbsp{2N}{n}$, which are associated with the minimum cost 2-edge-connected subgraph problem and the minimum cost 2-node-connected subgraph problem, respectively, are studied in this thesis, and some new classes of facet-inducing inequalities are introduced for these polytopes. These classes of inequalities are related to the so-called clique tree inequalities for the travelling salesman polytope ($Q\sbsp{T}{n}$), and the relationships between $Q\sbsp{T}{n}$ and $Q\sbsp{2E}{n}, Q\sbsp{2N}{n}$ are exploited in obtaining these new classes of facets. Due to the use of problem specific facet-inducing inequalities instead of dominant cutting-planes, the linear programming cutting-plane method has proven to be quite successful for solving some NP-hard combinatorial optimization problems. We believe that our new classes of facet-inducing inequalities can be used to further improve the cutting-plane procedure for designing minimum cost survivable communication networks.