Mathematisches Kolloquium

Freitag, 02.02.2018, 14:15 Uhr

Dealing with Uncertainties in discrete Optimization - a Recoverable Robust Approach

Christina Büsing (Juniorprofessur für Robuste Planung in der medizinischen Versorgung)

Abstract:
Dealing with uncertainties is an important task whenever minimization problems of real world applications are considered. A classical way to include them into the optimization process is called robust optimization. In robust optimization we choose a solution that is feasible in all considered uncertainty settings and minimizes the worst-case cost. However, this approach leads to over conservative solutions and neglects the fact that solutions can be adapted. The concept of recoverable robustness takes this option into account.
 
In this talk I will present a special version of recoverable robustness - the so called k-Delete recoverable robustness (k-Del RR) – to deal with cost uncertainties. K-Del RR consists of two stages. In the first stage, a solution is chosen. In the second stage, after the real costs are revealed, the solution can be adapted by deleting up to k elements to reduce the cost. This is motivated by an application in telecommunication where a technology upgrade is refused to at most k customers in order to hedge against the increased cost.
 
After a short introduction of the problem, we will consider 0-1 optimization problems and their k-Delete recoverable robust version. We prove in the first part of the talk that the k-Del RR shortest path and minimum matching problem are strongly NP-hard and provide polynomial solvable cases. In the second part of the talk we focus on exact algorithms to solve these problems. We will therefore derive several different IP-formulations and provide preliminary computational results on the run-time.

Wir laden herzlich alle Interessierten zu diesem Vortrag ein.

Ort:  Raum 008/SeMath, Pontdriesch 14-16, 52062 Aachen