Design of Survivable Networks
The problem of designing a cost-efficient network that survives the failure of one or more nodes or edges of the network is critical to modern telecommunications engineering. The method developed in this book is designed to solve such problems to optimality. In particular, a cutting plane approach is described, based on polyhedral combinatorics, that is ableto solve real-world problems of this type in short computation time. These results are of interest for practitioners in the area of communication network design. The book is addressed especially to the combinatorial optimization community, but also to those who want to learn polyhedral methods. In addition, interesting new research problemsare formulated.
37 pages matching feasible solution in this book
Results 1-3 of 37
What people are saying - Write a review
We haven't found any reviews in the usual places.
Survivable Network Design under Connectivity Constraints
11 other sections not shown
2NCON(G 3-way cut affinely independent articulation node Chapter class of inequalities complete graph components con(W connected graph connected subgraph construct containing nodes convex hull costs cutting plane algorithm cutting plane phase decomposition defines a facet denote directed graph edge set fc-edge connected fcECON fcECON(G;r fcNCON problem fcNCON(G feasible solution Figure fractional solution given graph G heuristics incidence vector inequality aTx inequality induced kNCON Lemma Let G lifted r-cover inequalities low-connectivity Monma node cut constraint node cut inequality node partition inequality node sets node types nodes of type nonempty nonnegative NP-hard number of edges optimal solution pair of nodes parallel edges partition inequality 8.5 polyhedra polyhedron polynomial polytope Prodon inequalities prove r(Wi right-hand side satisfies separating two nodes series-parallel graphs sets Wi solve special comb inequality teeth Theorem 7.5 traveling salesman problem type at least valid inequality W C V