We give an overview of new and existing cut- and flow-based ILP formulations for the two-stage stochastic Steiner tree problem and compare the strength of the LP relaxations.
Last but not least, fixed parameter tractable algorithms are described for the stochastic problems with parameter overall number of terminals @cite_16 and on partial 2-trees with parameter number of scenarios @cite_20 .
@cite_16 @cite_20
75217549 137798462
We consider the Steiner tree problem in graphs under uncertainty, the so-called two-stage stochastic Steiner tree problem (SSTP). The problem consists of two stages: In the first stage, we do not know which nodes need to be connected. Instead, we know costs at which we may buy edges, and a set of possible scenarios one of which will arise in the second stage. Each scenario consists of its own terminal set, a probability, and second-stage edge costs. We want to find a selection of first-stage edges and second-stage edges for each scenario that minimizes the expected costs and satisfies all connectivity requirements. We show that SSTP is in the class of fixed-parameter tractable problems (FPT), parameterized by the number of terminals. Additionally, we transfer our results to the directed and the prize-collecting variant of SSTP. Given an undirected graph G = (V, E) and a node set (T V ), a Steiner tree for T in G is a set of edges (S E ) such that the graph (V(S), S) contains a path between every pair of nodes in T, where V(S) is the set of nodes incident to the edges in S. Given costs (or weights) on edges and nodes, the Steiner tree problem on a graph (STP) is to find a minimum weight Steiner tree. The problem is known to be ( N P )-hard even for planar graphs, bipartite graphs, and grid graphs.