Design of survivable networks (Q1202193)

The author deals with the mathematical modelling of the design of survivable networks --- a problem of great practical importance, for instance, in telecommunication. The monograph uses methods of polyhedral combinatorics to tackle the (NP-hard) problem of finding 2, or more general, \(k\)-connected networks. Separate chapters deal with decomposition methods if the underlying graph \(G\) is sparse, and the derivation of valid inequalities of the partition and node partition, \(r\)-cover and comb type. A large part of the monograph is concerned with the characterization of some of these inequalities as facet inducing using for instance lifting techniques. Especially nice is the chapter entitled ``How to find valid inequalities'', which is suitable for any combinatorial optimization class, since the techniques described in this chapter go beyond the specific network design application. The paper is concluded by a discussion of computational issues such as the solution of the separation problems associated with the valid inequalities and a report on numerical results.