Boyd, Sylvia,Wu, Xiaolin.2009-03-252009-03-2519941994Source: Masters Abstracts International, Volume: 33-05, page: 1583.9780315960077http://hdl.handle.net/10393/9917http://dx.doi.org/10.20381/ruor-8034Polytopes $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.87 p.Engineering, System Science.Thesis