{0,1,2}-Survivable Network Design Problems

M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel
last updated on (month/day/year)
home

Problem definition

We are given a graph G=(V,E), a set of customers C&sube V=C₁&cup C₂ of customers and a cost function c on the graph edges. The task of the {0,1,2} is to find a connected subgraph N of G that contains (all) customers and contains two disjoint paths between each pair of the included customers. Depending on the exact definition of the disjointness of the required paths (edge- or node-disjoint) and on the conditions of including a customer into a network we obtain the following problem variants:

Problem description

Problem Type	Edge-Connectivity	Node-Connectivity
Problem Type	Edge-Connectivity	rooted	unrooted
spanning	2ECON	2RSN	2NCON
prize-collecting	2PCECON	2RPCSN	2PCNCON

Exact algorithms

For 2ECON and 2NCON a Branch-and-Cut algorithms was presented by Stoer [7]. Thereby an ILP based on undirected graphs was used. Additional valid inequalities have been introduced and analyzed. For 2ECON Chopra [4] presented and analyzed the structure of the optimal solution and presented an Branch-and-Cut algorithm using an ILP based on directed graphs.

Our conribution

For the {0,1,2}-survivable network design problems with node-connectivity requirements we derive new orientation properties of the optimal solutions and propose strong ILP formulations based on these properties. We then use these formulations to design an fast exact Branch-and-Cut algorithms for these problems. See [2],[3] for our publications. Additionaly, our code is also able to deal with problems with edge-connectivity requirements. Both, theory and experiments show that for all problems discussed above, except for the {0,2}-ECON, it can be advantageous to develop exact algorithms based on ILP's that exploit orientation properties of the optimal solutions. Most of the problems of our benchmark set could be solved to optimality within a few seconds.

2ECON

Requirements for optimal solutions

all customers are included, all C₂ belong to the same 2-edge-connected component

Solution Structure

Solution Properties

For any choice of a root node r, there exists a unique orientation of the solution such that for any C₂ customer v there are directed paths from r to v and from v to r. Furthermore for each C₁ customer v there exists a directed path from r to v.

Special Cases

2-edge-connected Steiner network ({0,2}-ECON)
2-edge-connected spanning network ({2}-ECON)

Known inequalities

Strength of the ILP's

General case: directed (Chopra []) stronger than undirected (Stoer [], Mahjoub(?))
{0,2}-case: directed and undirected are equivalent (Raghavan [])

Further results

	{2}	{0,2}	{0,1,2}
Problem Structure
Approximations
Heuristics
Exact algorithms

2NCON

Requirements for optimal solutions

all customers are included, all C₂ belong to the same 2-node-connected component

Solution Structure

Solution Properties

For any choice of a root node r, there exists a unique orientation of the solution such that for any C₂ customer v there are directed node-disjoint paths from r to v and from v to r Furthermore for each C₁ customer v there exists a directed path from r to v. Furthermore, in this orientation there is only one ingoing edge into the root node.

Special Cases

2-node-connected Steiner network ({0,2}-NCON)
2-node-connected spanning network ({2}-NCON)

Known inequalities

Strength of the ILP's

In all cases directed (Chimani, Kandyba, Mutzel, Ljubic []) stronger than undirected (Stoer [], Mahjoub(?))