Steiner Problem Application (Branch-and-cut): Problem description and solving approach

The Steiner tree problem in graphs (SPG) can be described as follows: Given an undirected connected graph $ G=(V,E)$ , costs

$c: E \rightarrow \mathcal{Q}^+$

and a set $T \subset V$ of terminals, the problem is to find a minimum-weight tree $S\subseteq G$ that spans $ T $ . Each tree $ S $ that spans $ T $ , called Steiner tree, is a feasible solution to the problem. The following picture shows an SPG instance with the terminals given as squares:

The solving approach of SCIP-Jack can be dissected into three major components:

First, problem specific preprocessing is extremely important. Apart from some pathological instances specifically constructed to defy presolving techniques, preprocessing is often able to significantly reduce instances or even solve them.

Second, heuristics are needed, especially for hard instances, to find good or even optimal solutions.

Finally, the core of our approach is constituted by a branch-and-cut procedure used to compute lower bounds and prove optimality.

The problem can be formulated using the directed equivalent of the SPG, the Steiner arborescence problem (SAP): Given a directed graph $ D=(V,A) $ , a root $r \in V$ , costs $c: A \rightarrow \mathcal{Q}^+$ and a set $T \subset V$ of terminals, a subgraph $S\subseteq D$ such that for all $t \in T$ , $ S $ contains exactly one directed path from $ r $ to $ t $ is called Steiner arborescence. Thereupon, a Steiner arborescence $ S = (V_S, A_S) $ is required that minimizes $\sum_{a \in A_S} c_a$ . An SPG can be transformed to an SAP by replacing each edge with two anti-parallel arcs of the same cost and distinguishing an arbitrary terminal as the root. This transformation results in a one-to-one correspondence between the respective solution sets. Introducing variables $y_a$ for $a\in A$ with the interpretation that $y_a:=1$ if and only if $a$ is in the Steiner arborecence, and $y_a:=0$ otherwise, we obtain the integer program:

$\begin{array}[t]{rll} \min {c}^T y\\ \\ y(\delta^+(W))&\geq& 1, ~~~ \forall , W\subset V, r\in W, (V\setminus W)\cap T\neq \emptyset\\ y(\delta^-(v))& \left\{{\begin{array}{l} = \\ = \\ \leq \end{array}}\right. & {\begin{array}{l} 0, \mbox{if } v=r;\\ 1, \mbox{if } v\in T\setminus{r};\\ 1, \mbox{if } v\in N; \end{array}} \hspace{2.9mm}\forall v \in V \\ y(\delta^-(v))&\leq& y(\delta^+(v)), \hspace{10.5mm}\forall v\in N;\\ y(\delta^-(v))&\geq& y_a, \hspace{20.2mm}\forall a\in\delta^+(v), v\in N;\\ 0\leq y_a&\leq& 1, \hspace{22mm}\forall a\in A;\\ y_a&\in& \{0,1\}, \hspace{15.1mm}\forall a\in A, \end{array}$

where $N=V\setminus T$ , $\delta^+(X):=\{(u,v)\in A| u\in X, v\in V\setminus X\}$ , $\delta^-(X):= \delta^+(V \setminus X)$ for $X\subset V$ i.e., $\delta^+(X)$ is the set of all arcs going out of and $\delta^-(X)$ the set of all arcs going into $X$ .

Since the model potentially contains an exponential number of constraints, a separation approach is employed. Violated constraints are separated during the execution of the branch-and-cut algorithm.

In addition to Steiner problems in graphs there exist several variations. The following Steiner problem variants can be solved by SCIP-JACK, by transforming them to a Steiner arborescence problem, and in some cases introducing additional constraints:

-Steiner arborescence problems,

-rectilinear Steiner minimum tree problems,

-node-weighted Steiner tree problems,

-prize-collecting Steiner tree problems,

-rooted prize-collecting Steiner tree problems,

-maximum-weight connected subgraph problems,

-degree-constrained Steiner tree problems,

-group Steiner tree problems, and

-hop-honstrained directed Steiner tree problems.

A far more intricate description of SCIP-Jack and its various components can be found in "A generic approach to solving the Steiner tree problem and variants" by D. Rehfeldt.