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.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/9917 |
| Date | January 1994 |
| Creators | Wu, Xiaolin. |
| Contributors | Boyd, Sylvia, |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Detected Language | English |
| Type | Thesis |
| Format | 87 p. |
Page generated in 0.0021 seconds