Steiner Tree Problem in Graphs and Mixed Integer
Linear Programming-Based Approach in GAMS
MILOˇ
Sˇ
SEDA
Institute of Automation and Computer Science
Brno University of Technology
Technica 2, 616 69 Brno
CZECH REPUBLIC
Abstract: - The Steiner tree problem in graphs involves finding a minimum cost tree which connects a
defined subset of the vertices. This problem generalises the minimum spanning tree problem, in contrast,
it is NP-complete and is usually solved for large instances by deterministic or stochastic heuristic methods
and approximate algorithms. In this paper, however, we focus on a different approach, based on the
formulation of a mixed integer programming model and its modification for solving in the professional
optimization tool GAMS, which is now capable of solving even large instances of problems of exponential
complexity.
Key-Words: - Steiner tree problem, NP-completeness, heuristic, performance ratio, network flow,
mixed-integer linear programming, GAMS
Received: September 14, 2021. Revised: May 9, 2022. Accepted: June 5, 2022. Published: July 2, 2022.
1 Introduction
In practice, e.g., in telecommunication applica-
tions [7], [9], [2], [18], we frequently solve prob-
lems based on finding minimal networks. The
criterion of minimality can be represented by the
total costs for the implementation of the network
or by the total length of connections. These prob-
lems include, e.g., the problem of finding optimal
location of a source with respect to given sinks.
The Network Steiner tree problem (NSTP) (or
Steiner tree problem in graphs) [10], [14], [22] is
concerned with connecting a subset of vertices at
a minimal cost. More precisely, given an undi-
rected connected graph G= (V, E) with vertex
set V, edge set E, nonnegative weights associ-
ated with the edges, and a subset Bof V(called
terminals or customer vertices), the problem is to
find a subgraph, T, which connects the vertices in
Bso that the sum of the weights of the edges in
Tis minimised. It is obvious that the solution is
always a tree and it is called a Steiner minimum
tree for Bin G.
If |B|= 2 then the problem reduces to the
shortest path problem and can be solved by Dijk-
stra’s algorithm. In the case of B=Vthe NSTP
reduces to the minimum spanning tree (MST)
problem and can be solved by Jarn´ık’s (Prim’s),
Bor˚uvka’s or Kruskal’s algorithm. All these al-
gorithms are polynomial. However, in the gen-
eral case the NSTP is NP-complete [15], [20] and
it cannot therefore be solved exactly for larger
instances, i.e. heuristic or approximate meth-
ods must be used. A Steiner minimum tree is
not a minimum spanning tree only, it can also
span some nonterminals, called Steiner vertices,
as shown in Fig. 1.
Figure 1: An example of the Streiner tree problem
in graphs, = terminals, = Steiner vertices)
2 Approximation algorithms
As was mentioned above, the network Steiner tree
problem is NP-complete. It means that solving
the problem requires a computational time that
grows (in the worst case) exponentially with the
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31
Milos Seda
E-ISSN: 2224-2872
257
Volume 21, 2022
problem size. Therefore we must use approxi-
mation or heuristic approaches for large scaled
instances. Many approaches are based on a re-
formulation of the problem [5], [8] [12], branch
and bound method, dynamic programming, etc.
[11], [19].
Aproximation algorithms are algorithms that
guarantee that the ”distance” of their solutions
from the optimum is in the worst case restricted
by a mathematically proved upper bound. The
quality of an approximation algorithm is mostly
measured by its performance ratio, which is given
by the ratio of then achieved solution and the op-
timum. If a Steiner tree for a set of terminals B
is computed by an approximation algorithm and
has a total length ASMT (B), Steiner minimum
tree for Bis SMT (B), then the Steiner tree prob-
lem performance ratio ϱgraph(B) is given by
ϱgraph(B) = w(ASMT (B))
w(SMT (B))
The simplest approximation algorithms for the
NSTP are distance network approximation [17],
minimum path approximation [24], and contrac-
tion approximation [21]. We will briefly sum-
marise only the first one.
A distance network approximation [3] can be
described as follows:
[To determine a Steiner mimimum tree in a
connected weighted graph G= (V, E)with a set
of terminals B]
1. Construct the complete graph KB= (B, F )
in which the weight of {i, j} Fis the short-
est distance between iand jin G.
2. Obtain a minimum spanning tree MST (KB)
of the graph KB.
3. Replace each edge {i, j}of M ST (KB) by a
shortest path between iand jin G. (The
resulting graph, G, is a Steiner subgraph of
G since it is connected and contains B.)
4. Obtain a minimum spanning tree MST (G)
in G. (MST (G) is a Steiner tree.)
5. If vis a Steiner vertex of degree 1 in
MST (G), delete vfrom the tree MST (G)
with its incident edge. Continue this process
by deleting one Steiner vertex at a time.
Theorem 2.1 The distance network approxima-
tion algorithm runs in O(|B||V|2)time.
Proof. Running times of the steps are:
1. If the distance graph is not known, Step 1 re-
quires time O(|B||V|2) to compute the short-
est paths from each of the |B|vertices.
2. Kruskal’s minimum spanning tree algorithm
requires time O(|B|log |B|).
3. Each of the |B| 1 edges of MST (KB)
may correspond to a path in Gof up to
|V| 1 edges. Hence, Step 3 requires time
O(|B||V|).
4. O(|B||V|log(|B||V|)) time using Kruskal’s
algorithm again.
5. The final step is done in time O(|V|).
Step 1 is the most expensive and gives the dis-
tance network approximation algorithm a time
complexity of O(|B||V|2).
Unfortunately, the performance ratio of the
above algorithm is equal to 2, and thus in the
worst case the length of the obtained Steiner tree
is 2 times longer than the length of the minimum
Steiner tree.
The approximation ratios of other determin-
istic heuristic algorithms for solving the Steiner
problem in graphs are only slightly better, so we
will not discuss them further and move on to the
formulation of the mathematical model and its
solution in the optimization tool GAMS.
3 Mathematical formulation
Let V={1,2, . . . , n}and Sbe a set of Steiner
vertices. For every edge (i, j), cij ,cij 0 is a
weight of the edge. The aim is to find a connected
graph G= (BS, E) (Steiner tree), EE, so
that the sum of weights to be minimal.
In other words, the Steiner minimum tree
problem can be described as a problem of finding
a set of edges that connects terminals. There-
fore we can define a bivalent variable xij for each
edge (i, j)Eindicating whether the edge (i, j)
is included into the Steiner tree (xij = 1) or not
(xij = 0) and similarly a bivalent variable fiindi-
cating whether vertex iis included in the Steiner
tree (fi= 1) or not (fi= 0). For terminals,
iB, it is satisfied fi= 1, and fi {0,1}for
the other vertices, i(VB).
Each vertex of BSmust be reachable via
edges of Efrom any other vertex of BS. There-
fore, it must be an endpoint of at least one edge
in E. For the sake of mathematical formulation,
we select a vertex r, called root, with the orienta-
tion of edges to r, and by this way we get a rooted
tree. Due to the selected orientation the root has
no output edges, and thus xrj = 0 for jV{r}.
So as the final graph Gwould be a tree, i.e. it
does not contain a cycle, just one path must lead
to the root from the vertices included into the
Steiner tree, and thus exactly one edge must leave
these vertices. If a vertex is not included into the
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31
Milos Seda
E-ISSN: 2224-2872
258
Volume 21, 2022
Steiner tree, then no edge leaves it. The number
of edges leaving vertex i(V {r}) is defined
by Pn
j=1 xij , i.e. it corresponds to fi.
Finally, we must provide the connectedness of
G, that means the edges of Ein the selected ori-
entation must enable a connection of any vertex
with the root. For this reason we define a net-
work flow with respect to Eso that all vertices
of (BS) {r}are sources of 1 unit of flow [1],
and the root is a sink, supplied by flows of all
vertices from the set (BS) {r}of G.
Let yij be a flow through the edge (i, j)E.
If iis a source of 1 unit of flow, then the dif-
ference between the total flow leaving iand the
total flow entering imust be equal to 1. As
vertices unselected into the Steiner tree have
no incident edges, their flows are equal to 0,
and for all vertices i(V {r}) the equation
Pn
j=1 yij Pn
j=1,j=ryji =fiis satisfied.
For each edge (i, j)∈ E, i.e. edge unselected
into the Steiner tree (xij = 0), the flow yij = 0.
On the other hand, if the edge is selected (xij =
1), then since this edge is in the rooted tree is
the only output edge of vertex i, the vertex iis
the source of 1 unit of flow and the total inflow
to iis at most equal to the flow from n2 other
vertices (|V| |{i, r}|), it follows that the flow yij
through edge (i, j) is at most equal to (n2) + 1,
i.e., (n1). Both cases can be expressed by a
single relation as follows: 0 yij (n1)xij for
i, j V.
Summarizing all the considerations so far, we
can formulate the Steiner problem in graphs as a
mixed integer linear programming problem of the
following form:
Minimise
n
X
i=1
n
X
j=1
cij xij
subject to
j(V {r}) : xrj = 0
i(V {r}) :
n
X
j=1
xij =fi
i(V {r}) :
n
X
j=1
yij
n
X
j=1,j=r
yji =fi
i, j V: 0 yij (n1)xij
i, j V:xij {0,1}
iB:fi= 1
i(VB) : fi {0,1}
Another formulation can be found in [16]. A
survey of Steiner tree problem formulations is
presented in [13].
4 Modification of the model
and computing in GAMS
The mathematical model derived in the previous
section can be used for computing Steiner trees by
means of the optimisation package GAMS (Gen-
eral Algebraic Modelling System) [6] developed by
Alexander Meeraus and Anthony Brooke at the
World Bank in the 80s especially for the tasks of
linear, nonlinear and mixed integer programming.
The question is how to choose the root from
the given terminals. Since it can be any terminal,
we can choose the first terminal in the list of ter-
minals, or the smallest terminal number, as the
root without loss of generality.
From the input data we need to create a ma-
trix with edge lengths C=(cij ), that is, to some-
how define the weights of the nonexisting edges.
The usual approach, if it is a minimization prob-
lem, is to set these weights equal to . How-
ever, this value is not defined in the computer,
and it is not advisable to choose the largest dis-
playable number in the computer either, as this
may be dependent on the software used and, in
addition, the sum in the objective function could
cause overflow of the range. For these reasons, we
assign zero weights to non-existing edges. With-
out further modification, however, this setting
would lead to erroneous results, because the min-
imum Steiner tree would be constructed from
zero-ranked edges, i.e., edges that in the specified
graph do not exist at all. However, this short-
coming is easily remedied by adding constraints
to ensure that for those pairs of vertices that are
not connected by an edge, the values of xij and
yij are zero.
In order to speed up the calculation, it will
also be useful to limit the range of values of the
yij variables. The model is based on the fact that
all vertices except the root are sources of flow of
size 1, and hence those vertices of the root graph
where no edges enter are also sources of flow of
size 1. It follows that all flows must be equal to
integer values.
If we denote the root by r, then the model can
be written as follows:
Minimise
n
X
i=1
n
X
j=1
cij xij
subject to
r:= min{k|kB}
j(V {r}) : xrj = 0
i(V {r}) :
n
X
j=1
xij =fi
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31
Milos Seda
E-ISSN: 2224-2872
259
Volume 21, 2022
i(V {r}) :
n
X
j=1
yij
n
X
j=1,j=r
yji =fi
i, j V:yij (n1)xij
i, j V:yij Z+
i, j V, cij =0: xij := 0
i, j V:xij {0,1}
iB:fi= 1
i(VB) : fi {0,1}
where Z+denotes the set of nonnegative integers.
GAMS is a high level language for formulat-
ing models with concise algebraic statements that
are easily read by modellers and computers alike,
easily modified, and easily moved from one com-
puter environment to another - it is independent
on the solution algorithms of specific solvers. The
basic components of a GAMS model are:
SETS statement declares sets of indices of ar-
rays and assigns values to them.
In input data section, parameters are de-
clared and values are assigned to them
(SCALAR statement is defined for constants,
PARAMETERS statement for arrays, TA-
BLE statement simplifies matrix declara-
tions). PARAMETERS statement can also
be used for a definition of a data object by
a formula which expresses how to calculate
object values from the values of the other al-
ready defined objects.
VARIABLES statement declares decision
variables and objective function and enables
to specify the type of variables (BINARY,
INTEGER, POSITIVE, NEGATIVE, FREE
(default)).
EQUATIONS section describes constraints of
the optimisation problem. MODEL state-
ment builds a model of the task and assigns
a name to the list of constraints.
SOLVE statement calls the solver and speci-
fies the way of optimisation (MINIMIZING
or MAXIMIZING), variable optimised and
runs calculations.
DISPLAY statement is determined to output
of results.
The source code in GAMS for data from Fig.
1 can be expressed by the following way:
$TITLE Network Steiner tree problem
$OFFSYMXREF
$OFFUELLIST
$OFFUELXREF
OPTION ITERLIM=200000
* ITERLIM maximal number of iterations
* Section defining index sets
SETS
K indices of terminals /1*4/
I start vertices of edges /1*13/;
ALIAS(I,J);
* J - end vertices of edges
*****************************************
* Input data section
PARAMETERS
B(K) indices and numbers of terminals
/1 2, 2 4, 3 7, 4 12/;
PARAMETERS
N,R;
N=CARD(I);
R=B("1");
TABLE C(I,J) edge weights
* (0 = corresponding edge does not exist)
1 2 3 4 5 6 7 8 9 10 11 12 13
109000014000000
29080060000000
30807300000000
400704000001000
50034020004000
60600207280000
7140000701300000
800000213000003
90000080001031
100000400010500
1100010000005080
120000000030801
130000000310010;
*****************************************
* Variable section (decision variables
* and objective function)
VARIABLES
X(I,J) equals to 1 if the edge ij is
included into Steiner tree, 0 otherwise
Y(I,J) edge flow
F(I) equals to 1 if the vertex i is
included into Steiner tree, 0 otherwise
St total sum of edge weights in
Steiner tree;
BINARY VARIABLE X;
INTEGER VARIABLE Y;
BINARY VARIABLE F;
* Equation section
EQUATIONS
EQ1(I,J)
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31
Milos Seda
E-ISSN: 2224-2872
260
Volume 21, 2022
EQ2(I)
EQ3(I)
EQ4(I,J)
EQ5(I,J)
EQ6(I,K)
EQ7(I,J)
DELKA;
EQ1(I,J)$((ORD(I) EQ R)
AND (ORD(J) NE R)) .. X(I,J) =E= 0;
EQ2(I)$(ORD(I) NE R)
.. SUM(J,X(I,J)) =E= F(I);
EQ3(I)$(ORD(I) NE R)
.. SUM(J,Y(I,J))
-SUM(J$(ORD(J) NE R),Y(J,I))
=E= F(I);
EQ4(I,J) .. Y(I,J) =G= 0;
EQ5(I,J) .. Y(I,J) =L= (N-1)*X(I,J);
EQ6(I,K)$(ORD(I) EQ B(K)) .. F(I) =E= 1;
EQ7(I,J) .. X(I,J)$(C(I,J) EQ 0) =E= 0;
DELKA .. St =E= SUM((I,J),C(I,J)*X(I,J));
* Model description, solver execution
* and display of results
MODEL STEINER /ALL/;
SOLVE STEINER USING MIP MINIMIZING St;
DISPLAY X.L, F.L, Y.L, St.L;
Since INTEGER in GAMS is restricted
only for nonnegative integers the declaration
of INTEGER VARIABLE Y; is sufficient to specify
constraint assigning yij to Z+domain.
The relational operator =G= has the meaning
of and =E= corresponds to =.
To avoid large changes of GAMS program ac-
cording input data structures, it is more efficient
to prepare the data structures in a separate text
file and include it in GAMS program by $INCLUDE
directive, e.g. as follows:
$INCLUDE "B1.TXT"
Since more complex instances have (cij ) tables
with hundreds of columns and the line width is
limited, the tables must be expressed in a contin-
ued form. Similarly long sequences of terminals
must be written into several lines. Both these
modifications were provided by a special conver-
sion program.
5 Statistics and computational
results
Traditional approaches to calculations by heuris-
tic methods use statistical tests, which examine
at a certain significance level (e.g. α= 0.05),
to what extent the mean value of the results ob-
tained by different methods and different settings
of their parameters at a larger number of runs is
the same or different (and therefore one of the
methods gives better results). For the t-test, we
assume that the sets of values have a normal dis-
tribution. However, this assumption may not be
met and then one of the non-parametric tests,
such as the Wilcoxon test, must be used.
However, given the validity of the No Free
Lunch Theorem [25], [26], one should not expect
a general conclusion that any of the heuristics for
each problem instance gives better results than
other heuristics.
Here, we do not explore heuristics in this pa-
per and instead use a mixed integer programming
model using the CPLEX software tool built as a
solver in the GAMS environment to find an exact
solution by deterministic computation. Statis-
tical evaluations are therefore meaningless here.
What can be said, however, is that the power
of this software today is considerably greater
than it was 20 years ago, when in our expe-
rience for a problem with complexity O(20!)
the system ended up with a runtime error and
the message insufficient space to update
U-factor ...”; today it computes an exact so-
lution on a laptop with a 2.4 GHz processor in
about 4.5 minutes.
Table 1 summarizes the results of computing
Steiner minimum trees for test problems with ver-
tex counts of 50 and 100, defined sets of terminals
and computation times, with all tree lengths cor-
responding to the optimal solutions. It can be
seen that even for such large instances GAMS is
able to obtain an accurate solution in a time of a
few seconds at most.
test |V| |B|time [sec] length
B1 50 9 0.11 82
B2 50 13 0.56 84
B3 50 25 0.39 142
B7 75 13 1.14 116
B8 75 19 1.64 105
B9 75 38 0.51 225
B13 100 17 2.00 173
B14 100 25 1.88 244
B15 100 50 1.53 335
Table 1: Computational results
6 Conclusions
The paper proposed a general mathematical
model of the network Steiner tree and its modifi-
cation to use it in GAMS. According to our expe-
rience from another application area, presented in
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31
Milos Seda
E-ISSN: 2224-2872
261
Volume 21, 2022
[27], this tool is already able to successfully solve
exponentially complex problems with data struc-
tures with thousands of rows and columns. Here,
we verified that it is able to find exact solutions
for graphs with up to 100 vertices.
However, more tests will need to be performed
in the future to compare the results with bench-
mark data from combinatorial optimization li-
braries as [4], [23].
,
,
,
,
,
References:
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network
Flows. Theory, Algorithms and Applications. Prentice Hall,
Englewood Cliffs, New Jersey, 1993. ISBN 0-13-617549- X.
[2] S. Balaji, K. Kannan, and Y. B. Venkatakrishnan. Total
Dominating Set Based Algorithm for Connected Dominating
Set in Ad hoc Wireless Networks. WSEAS Transactions on
Mathematics, 12:11641172, 2013.
[3] V. K. Balakrishnan. Network Optimization. Chapman &
Hall Mathematics, London, 1995.
[4] J. E. Beasley. OR-Library. Report, The Management School
Imperial College, London, 1996.
http://mscmga.ms.ic.ac.uk/info.html.
[5] C. Bentz, M.-C. Costa, and A. Herty. On the Edge
Capacitated Steiner Tree Problem. Discrete Optimization,
38:125, 2020.
[6] A. Brooke, D. Kendrick, and A. Meeraus. GAMS Release
2.25. A User’s Guide. The Scientific Press. Boyd & Fraser
Publishing Company, Massachussets, 1992.
[7] J.-F. Camacho-Vallejo and C. Garcia-Reyes. Co-
Evolutionary Algorithms to Solve Hierarchized Steiner Tree
Problems in Telecommunication Nnetworks. Applied Soft
Computing Journal, 84:112, 2019.
[8] C.-Y. Chen and S.-Y. Hsieh. An Improved Algorithm for
the Steiner Tree Problem with Bounded Edge-Length. Journal
of Computer and System Sciences, 123:2036, 2022.
[9] D. Du and X. Hu. Steiner Tree Problems in Computer
Communication Networks. World Scientific, Singapore, 2008.
[10] D.-Z. Du, J. M. Smith, and J. H. Rubinstein. Advances in
Steiner Trees. Kluwer Academic Publishers, Dordrecht, 2000.
ISBN 0-7923- 6110-5.
[11] C. W. Duin and A. Volgenant. The Partial Sum Criterion
for Steiner Trees in Graphs and Shortest Paths. European
Journal of Operational Research, 97:172182, 1997.
[12] D. Gaul and D. R. Schmidt. Chv´atal–Gomory Cuts for the
Steiner Tree Problem. Discrete Applied Mathematics,
291:188200, 2021.
[13] M.X. Goemans and Y. Myung. A Catalog of Steiner Tree
Formulations. Networks, 23:19 28, 1993.
[14] F. K. Hwang, D. S. Richards, and P. Winter. The Steiner
Tree Problem. North-Holland, Amsterdam, 1992.
[15] S. Khuller. Design and Analysis of Algorithms. Lecture
Notes, University of Maryland, Department of Computer
Science, 1994. 112 pp.
[16] T. Koch and A. Martin. Solving Steiner Tree Problems in
Graphs to Optimality. Networks, 32:207232, 1998.
[17] L. Kou, G. Markowsky, and L. Berman. A Fast Algorithms
for Steiner Trees. Acta Informatica, 15:141145, 1981.
[18] Y.-C. Lin, H.-A. Chien, C.-C. Shih, and H.- M. Chen. A
Multi-layer Obstacles-Avoiding Router Using X-Architecture.
WSEAS Transactions on Circuits and Systems, 7:879888,
2008.
[19] A. Lucena and J. E. Beasley. A Branch and Cut Algorithm
for the Steiner Problem in Graphs. Networks, 31:3959, 1998.
[20] J. Plesn´ık. Grafov´e algoritmy. VEDA, vydavate´lstvo
Slovenskej akad´emie vied, Bratislava, 1983.
[21] J. Plesn´ık. Heuristics for the Steiner Problem in Graphs.
Discrete Applied Mathematics, 37/38:451463, 1992.
[22] H. J. Pr¨omel and A. Steger. The Steiner Tree Problem. A
Tour through Graphs, Algorithms, and Complexity. Vieweg
Verlag, Braunschweig, 2002.
[23] G. Skorobohatyj. Testsets. Report, Konrad-Zuse-Zentrum
f¨ur Informationstechnik, Berlin, 2000.
ftp://ftp.zib.de/pub/Packages /mp-testdata/index.html.
[24] H. Takahashi and A. Matsuyama. An Approximate
Solution for the Steiner Problem in Graphs. Mathematica
Japonica, 24(6):573577, 1980.
[25] D. H. Wolpert and W. G. McReady. No Free Lunch
Theorems for Optimization. IEEE Transactions on
Evolutionary Computation, 1(1):6782, 1997.
[26] D. H. Wolpert and W. G. McReady. Coevolutionary Free
Lunches. IEEE Transactions on Evolutionary Computation,
9(6):721735, 2005.
[27] P. ˇSeda, M. ˇSeda, and J. Hoˇsek. On Mathematical
Modelling of Automated Coverage Optimization in Wireless
5G and beyond Deployments. Applied Sciences, 10(24):125,
2020.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the Creative
Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en_US
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31
Milos Seda
E-ISSN: 2224-2872
262
Volume 21, 2022