Refine
Year of publication
- 2015 (2) (remove)
Document Type
- Master's Thesis (1)
- ZIB-Report (1)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
Institute
Spawned by practical applications, numerous variations of the classical Steiner tree problem in graphs have been studied during the last decades. Despite the strong relationship between the different variants, solution approaches employed so far have been prevalently problem-specific.
In contrast, we pursue a general-purpose strategy resulting in a solver able to solve both the classical Steiner tree problem and ten of its variants without modification. These variants include well-known problems such as the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem or the rectilinear minimum Steiner tree problem. Bolstered by a variety of new methods, most notably reduction techniques, our solver is not only of unprecedented versatility, but furthermore competitive or even superior to specialized state-of-the-art programs for several Steiner problem variants.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem specific. In contrast, this paper introduces a general purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This is achieved by transforming various problem variants into a general form and solving them using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.