Optimization Online


A Branch-and-Cut-and-Price Algorithm for Vertex-Biconnectivity Augmentation

Ivana Ljubic(ivana.ljubic***at***univie.ac.at)

Abstract: In this paper, 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 in order to make it vertex-biconnected. The problem is reduced to the augmentation of the corresponding block-cut tree, whose 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, 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 algorithm (BCP) which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of the BCP: Complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than the state-of-the-art metaheuristics and approximation algorithms, as far as graphs with up to 200 vertices are considered. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported.

Keywords: branch-and-cut; branch-and-cut-and-price; edge-weighted biconnectivity augmentation;

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report Nr. [2009-02], Department of Statistics and Decision Support Systems, Univesity of Vienna, 2009 (submitted to Networks)

Download: [PDF]

Entry Submitted: 06/26/2009
Entry Accepted: 06/27/2009
Entry Last Modified: 06/26/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society