Steiner Network

Problem definition.

In the Steiner Network problem we are given an undirected graph \(G=(V,E)\) with edge costs \(c:E\to R\) and connectivity requirements \(r_{uv}\) for all vertex pairs \(u,v\). A Steiner Network is a subgraph of \(G\) with at least \(r_{uv}\) edge-disjoint paths between each pair of vertices \(u\) and \(v\). The goal is to find a Steiner Network with the minimum cost.

An LP relaxation of the problem is as follows. We introduce a variable \(x_e\) for every edge \(e\in E\). For a set of vertices \(S\), let \(\delta(S)\) denote the set of edges of \(G\) with exactly one endpoint in \(S\). Also, let \(x(A) = \sum_{e\in A} x_e\).

\begin{eqnarray*} \mbox{minimize:} & \sum_{e\in E} \ c_e x_e & \\ \mbox{subject to:} & & \\ & x(\delta(S))\geq\max_{u\in S, v\notin S}r_{uv} & \mbox{ for every } S \subseteq V \\ & 0 \leq x_e \leq 1 & \mbox{ for every } e\in E\\ \end{eqnarray*}

Solution

We solve the problem using Jain's iterative rounding 2-approximation algorithm (using the above LP formulation).

As the LP formulation has an exponential number of constraints, we need to use a separation oracle and the row generation technique to solve it. The implemented separation oracle differs from the one described in [8] . It is easy to prove that, given a clique with edge weights equal \(r_{uv}\), the separation oracle only has to check the minimum cut values between pairs of vertices which are the endpoints of edges of a maximum spanning tree in this clique.

Example

#include "paal/iterative_rounding/steiner_network/steiner_network.hpp"

#include <boost/graph/adjacency_list.hpp>

#include <iostream>
#include <vector>

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
        boost::undirectedS, boost::no_property,
        boost::property<boost::edge_weight_t, int>>;
    using Edge = boost::graph_traits<Graph>::edge_descriptor;

    // sample problem
    std::vector<std::pair<int, int>> edges {{0,1},{0,1},{1,2},{1,2},{2,0}};
    std::vector<int> costs {1,1,1,1,7};
    auto restrictions = [](int i, int j) {return 2;};

    Graph g(edges.begin(), edges.end(), costs.begin(), 3);

    std::vector<Edge> result_network;

    // optional input validity checking
    auto steiner_network = paal::ir::make_steiner_network(
        g, restrictions, std::back_inserter(result_network));
    auto error = steiner_network.check_input_validity();
    if (error) {
        std::cerr << "The input is not valid!" << std::endl;
        std::cerr << *error << std::endl;
        return -1;
    }

    // solve it
    auto result = paal::ir::steiner_network_iterative_rounding(
        g, restrictions, std::back_inserter(result_network));

    // print result
    if (result.first == paal::lp::OPTIMAL) {
        std::cout << "Edges in steiner network" << std::endl;
        for (auto e : result_network) {
            std::cout << "Edge " << e << std::endl;
        }
        std::cout << "Cost of the solution: " << *(result.second) << std::endl;
    } else {
        std::cout << "The instance is infeasible" << std::endl;
    }
    paal::lp::glp::free_env();
    return 0;
}

complete example of the usage can be found in file steiner_network_example.cpp

Approximation Ratio

The approximation ratio of this algorithm equals 2.

Complexity

Todo:

This paragraph is wrong. It doesn't account for the fact that as we generate more rows in the row generation technique, our lp instance gets bigger.

The time complexity of the algorithm is \(O(|E|*(|V|+|E|+LP_{rowgen}))\), where \(|V|\) and \(|E|\) are respectively the numbers of vertices and edges whereas \(LP_{rowgen}\) is the time of solving the LP using row generation technique. \(LP_{rowgen}=O(rows * (|V|^4 + LP_{time}(|E|,|V|)))\), where \(rows\) is the number of generated rows and \(LP_{time}(col, row)\) is the time of solving the LP with \(O(col)\) columns and \(O(row)\) rows.

The memory complexity of the algorithm is \(O(|V|^2+|E|+LP_{mem}(|E|,|V|))\), where \(LP_{mem}(col, row)\) is the memory complexity of solving the LP with \(O(col)\) columns and \(O(row)\) rows.

References

Jain's iterative rounding 2-approximation algorithm is described in [8]. The book [12] contains a nice description of this algorithm (Chapter 10), along with many other iterative algorithms.