Publication Date:
2020-08-05
Description:
The Steiner tree packing problem (STPP) in graphs is a long studied
problem in combinatorial optimization. In contrast to many other problems,
where there have been tremendous advances in practical problem
solving, STPP remains very difficult. Most heuristics schemes are ineffective
and even finding feasible solutions is already NP-hard. What makes
this problem special is that in order to reach the overall optimal solution
non-optimal solutions to the underlying NP-hard Steiner tree problems
must be used. Any non-global approach to the STPP is likely to fail.
Integer programming is currently the best approach for computing optimal
solutions. In this paper we review some “classical” STPP instances
which model the underlying real world application only in a reduced form.
Through improved modelling, including some new cutting planes, and by
emplyoing recent advances in solver technology we are for the first time
able to solve those instances in the original 3D grid graphs to optimimality.
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/pdf
