A seminar by Prof. Jonas Prünte (TU Dortmund)
Date: 30 MAY 2019 from 11:00 to 13:00
Event location: Aula 5.2 - Viale Risorgimento, 2 - DEI Bologna
Type: Seminar
We address combinatorial optimization problems with uncertain objective functions, given by discrete probability distributions.
Within this setting, we investigate the so-called K-adaptability approach: the aim is to calculate a set of K feasible solutions such that the objective value of the best of these solutions, calculated in each scenario independently, is optimal in expectation.
We show that the problem is NP-hard even if the underlying certain problem is trivial, and present further complexity results concerning approximability and fixed-parameter tractability with respect to K.
Moreover, we present exact solution methods as well as a heuristic for this problem, and compare them in an extensive experimental evaluation.
Joint work with Prof. Christoph Buchheim