A branch‐and‐cut‐and‐price algorithm for vertex‐biconnectivity augmentation

In this article, the first approach for solving the vertex‐biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge‐weighted graph, we search for the cheapest subset of edges to augment this subgraph to make it vertex‐biconnected. The problem is reduced to augmentation of the corresponding block‐cut tree [Khuller and Thummella, J Algorithms 14 (1993), 214–225], and its connectivity properties are exploited to develop two minimum‐cut‐based ILP formulations: a directed and an undirected one. In contrast to the recently obtained result for the more general vertex‐biconnected Steiner network problem [Chimani et al., Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, Vol. 5165, Springer, 2008, pp. 190–200.], our theoretical comparison shows that orienting the undirected graph does not help in improving the quality of lower bounds. Hence, starting from the undirected cut formulation, we develop a branch‐and‐cut‐and‐price (BCP) algorithm which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of BCP: complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than state‐of‐the‐art metaheuristics and approximation algorithms, for graphs up to 200 vertices. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010