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 is based on three major components:

First, (problem-specific) reduction techniqes are 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. Additionally, reduction techniques are used for domain propagation.

Second, primal heuristics are needed, especially for hard instances, to find good or even optimal solutions. In particular, primal heuristics are important for bound-based reduction methods.

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,

-rooted maximum-weight connected subgraph problems,

-maximum-weight connected subgraph problems with budget constraints,

-partial-terminal node-weighted Steiner tree problems,

-degree-constrained Steiner tree problems,

-group Steiner tree problems, and

-hop-honstrained directed Steiner tree problems.

A more detailed description of SCIP-Jack and its various components can be found in "Faster algorithms for Steiner tree and related problems: From theory to practice" by Daniel Rehfeldt.