Real world applications for Steiner Tree Problem?

Question

Are there real-world applications of the Steiner Tree Problem (STP)?

I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that people can suggest of that could be formulated in terms of the STP?

Background: I am beginning my PhD research and I am looking at using hybrid metaheuristics and primal-dual methods for the decomposition and solution of large-scale combinatorial optimisation problems. I find the STP fascinating, and I'm wondering if there is much real-world motivation for studying it, or if it is primarily of theoretical interest.

Answer 1

I am currently writing my PhD proposal, which is about finding ways to apply theory from parameterized complexity, primarily tree decompositions, to realistic network optimization problems. But I mainly plan to work with Steiner Tree, not in the last place because its simple and there are a lot of papers/benchmarks available.

Stumbled on this question because I too have some trouble finding practical motivations for studying it. I think its practical relevance is more easily motivated by the enormous amount of optimization problems that are generalizations of the vanilla STP but are more flexible. There is a nice list here: http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf

I think some of the problems mentioned with phylogenetic trees can be directly formulated as STP but I haven't read the papers thoroughly.

This algorithm for connected facility location and single source rent-or-buy is also interesting: http://sma.epfl.ch/~eisenbra/Publications/jcss08cfl_final.pdf Though not directly modeled as an STP, solutions to these problems have a core that is a Steiner Tree and the algorithm makes use of a STP approximation algo directly to solve that part.

Also regarding heuristics for the STP you might be interested in this page: http://dimacs11.cs.princeton.edu/workshop.html There are quite a few new competitive algorithms that have been presented there.

---

Edit: You might also want to take a look at this book by William Cook:

In Pursuit of the Traveling Salesman

It is about the TSP, but that one is similarly theoretical. Chapter 3 contains really a load of concrete practical uses, not just the trivial tour finding stuff, but unexpected problems that can be solved by solving a TSP, including some biology problems as I mentioned. Part of the reason of the applicability seems to be the fact that there is a very powerful and accessible TSP solver out there, making it convenient to rephrase design problems as TSP's. I found it really inspiring as the same type of applications could be found for the STP I think (but there is no 'industry standard' solver for it so it doesn't happen in reality). Some of the chapter is free on Google books, though I recommend getting you hands on the full version cause some of the best examples are left out.

Answer 2

My apologies up front for not having more detail on my comment here. But I too have considered an approach of using STP in solving routing information. In fact, there are already some applications in the polynomial space where least distant routing adds vertices to direct someone, say off of an inter-state highway to surface streets, to reach shorter distances routes (directions). They may not be faster based on speed or traffic conditions.

The calculations strictly considered distance. It was partially rejected as an application since the trucking industry was not able to utilize residential streets for example, or alleys, for routing. But biking, walking, hiking could. There does seem to be some inclusion of this in Google maps now as you can choose you mode of transportation and I believe, this allows for more refined points on a greater number of qualifying routes. For example, traveling on city bus, bike or by foot, would not normally route to the interstate.

There used to be some info in the Google API, older versions, covering this routing. Not sure if it is still there, this was about 3 years ago. Good Luck.

Answer 3

The classic Steiner tree problem in graphs is for example used for the design of telecommunication networks, see the following link for some real-world instances: https://homepage.univie.ac.at/ivana.ljubic/research/STP/ "the edges of the input graph typically correspond to the local street map, with the edges vertices representing street intersections and the location of potential customers. The cost c associated with an edge is the cost of establishing the connection, i.e., of laying the pipe or cable on the corresponding street segment."

But you also find applications of the classic Steiner tree problem in quite different areas, such as cloud computing: https://dl.acm.org/doi/10.5555/3154580.3154595

If you consider also close relatives of the classic Steiner tree problem, such as the prize-collecting Steiner tree problem, then there are a large number of additional applications, ranging from computational biology to machine learning. See the following paper for some examples: https://onlinelibrary.wiley.com/doi/10.1002/net.22005