# Degree-Constrained Steiner Problem in Graphs with Capacity Constraints
## 5 Computation of an Exact Solution
### Computation of the Image of the Solution  
In the next step, the valued, directed image of the DCMStH is computed in \(G^{\prime\prime}\). The computation is performed by the ILP described in [29] and modified for the Steiner problem.  
At first, a random node \(s\in M\) is selected as the source of flows following the hierarchy. From \(s\), a set of flows is computed, one flow to each destination node in \(M\setminus\{s\}\).) The integer values associated with the arcs indicate the number of transited flows. The image is composed of arcs with non-zero flows. Note that the number of flows is not equal to the number of occurrences of the arc in the DCMStH.  
ILP variables:  
\(x(m,n):\) Integer variable; equal to the number of occurrences of the arc \((m,n)\) in the resulting hierarchy.  
\(F(m,n):\) Commodity flow variable; denotes the quantity of flows  
transiting on the arc \((m,n)\).  
Objective:  
The cost of the weighted image (the cost of the corresponding hierarchy) must be minimized.  
\[minimize\sum_{m\in V^{\prime\prime}}\sum_{n\in\Gamma_{m}^{+}}x(m,n)*c(m,n) \tag{1}\]  
The values of the variable \(x\) indicate the number of incoming and outgoing arcs (the predecessors and the successors) of the nodes (all occurrences combined) in the DCMStH. In the optimum, each node has a minimal number of occurrences. The number of occurrences of a non-source node is equal to the number of its predecessors. Only the first node occurrence of the source has no predecessor. Moreover, the number of occurrences must be sufficient to connect the outgoing arcs. The degree constraints can be formulated as follows.  
At the source,  
\[\sum_{n\in\Gamma_{s}^{+}}x(s,n)\leq D(s)+(D(s)-1)*\sum_{n\in\Gamma_{s}^{-}}x(n,s) \tag{2}\]  
At the non-source node \(m\),  
\[\sum_{n\in\Gamma_{m}^{+}}x(m,n)\leq(D(m)-1)*\sum_{n\in\Gamma_{m}}x(n,m)\qquad \forall m\in V^{\prime\prime}\setminus\{s\} \tag{3}\]  
The following lower bounds are also true.  
At the source,  
\[\sum_{n\in\Gamma_{s}^{+}}x(s,n)\geq D(s)+(D(s)-1)*(\sum_{n\in\Gamma_{s}}x(n,s) -1) \tag{4}\]  
In a non-source node \(m\) with degree bound \(D(m)>1\),  
\[\sum_{n\in\Gamma_{m}^{+}}x(m,n)\geq(D(m)-1)*(\sum_{n\in\Gamma_{m}^{-}}x(n,m)- 1)\qquad\forall m\in V^{\prime\prime}\setminus\{s\},D(m)\
eq 1 \tag{5}\]  
A node with a degree bound of one cannot be the start point of outgoing arcs.  
\[\sum_{n\in\Gamma_{m}^{+}}x(m,n)=0\qquad\forall m\in V^{\prime\prime}\setminus \{s\},D(m)=1 \tag{6}\]  
Each node in \(M\) except the source has a predecessor in the hierarchy.  
\[\sum_{n\in\Gamma_{m}^{+}}x(n,m)\geq 1\qquad\forall m\in M\setminus\{s\} \tag{7}\]  
Flows can express the connectivity between the nodes in \(M\).  
The arbitrary source \(s\) is the start point of one flow by destination in \(M\setminus\{s\}\).  
\[\sum_{n\in\Gamma_{s}^{+}}F(s,n)=|M|-1 \tag{8}\]  
Each node in \(M\setminus\{s\}\) is the destination of one and only one flow.  
\[\sum_{n\in\Gamma_{m}^{+}}F(m,n)=\sum_{n\in\Gamma_{m}}F(n,m)-1\qquad\forall m \in M\setminus\{s\} \tag{9}\]  
The other nodes conserve the flows.  
\[\sum_{n\in\Gamma_{m}^{+}}F(m,n)=\sum_{n\in\Gamma_{m}}F(n,m)\qquad\forall m\in V ^{\prime\prime}\setminus M \tag{10}\]If an arc does not belong to the solution, it does not carry any flow. Conversely, each arc belonging to the solution carries at least one flow, and the number of flows carried cannot be less than the number of occurrences of the arc.  
\[F(m,n)=0 \forall(m,n)\in A^{\prime\prime}\text{ if }\ x(m,n)=0 \tag{11}\] \[F(m,n)\geq x(m,n) \forall(m,n)\in A^{\prime\prime}\text{ if }\ x(m,n)>0 \tag{12}\]  
The number of occurrences of an arc is limited by the number of the \"destinations\".  
\[x(n,m)<|M|\qquad\forall(m,n)\in A^{\prime\prime} \tag{13}\]  
This linear program computes the directed images of the solution in \(G^{\prime\prime}\). The solution (the DCMStH) must be determined from its image.