Refine
Document Type
- ZIB-Report (3)
Language
- English (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- maximum-weight connected subgraph (3) (remove)
Institute
Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver.
The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
(2017)
This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.
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 versatility is achieved by transforming various problem variants into a
general form and solving them by 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.