2356. On Solving the Stochastic Steiner Tree Problem with a Fast Heuristic
Invited abstract in session WB-4: Network Optimization, stream Discrete and Combinatorial Optimization.
Wednesday, 10:45-12:15Room: H6
Authors (first author is the speaker)
| 1. | Berend Markhorst
|
| Stochastics Group, CWI | |
| 2. | Alessandro Zocca
|
| CMS, California Institute of Technology | |
| 3. | Joost Berkhout
|
| Vrije Universiteit Amsterdam | |
| 4. | Rob van der Mei
|
| CWI |
Abstract
The Stochastic Steiner Tree Problem (SSTP) is well-known in the literature and has many applications. Although there are a few approaches specifically tailored to this stochastic optimization problem, there are considerably more state-of-the-art heuristics for its deterministic equivalent, the Steiner Tree Problem (STP). In this work, we show how to use one of these STP heuristics in a novel framework to solve the SSTP. This approach is a powerful, yet simple and easy-to-implement way of solving this complex problem. We test our method with benchmark instances from the literature and the numerical results show considerably faster computation times compared to the current state-of-the-art, with an optimality loss of approximately 5%.
Keywords
- Stochastic Programming
- Network Design
- Combinatorial Optimization
Status: accepted
Back to the list of papers