Recovery-to-optimality: A new two-stage approach to robustness with an application to aperiodic timetabling

摘要

The goal of robust optimization is to hedge against uncertainties: in most real-world applications, the specific problem instance depends on uncertain data and is hence not known beforehand. In this work we introduce a new two-stage approach called recovery-to-optimality to handle uncertain optimization problems. Motivated by two-stage stochastic programming and in a similar spirit as the well-known approaches of adjustable robustness or recovery robustness, our new concept allows us to adapt a solution when the realized input scenario is revealed. Using a metric in the solution space measuring the recovery costs, we can evaluate the worst-case costs or the average costs of any solution. Our new concept recovery-to-optimality asks for a solution which can be recovered to an optimal solution with low recovery costs. We set up the robust counterpart (RecOpt) for this concept. However, our intention is to provide a practical approach that can easily be used to generate robust solutions for any application. Building on solution algorithms for the deterministic problem, and on algorithms from location theory, we propose a generic procedure which is able to generate solutions with low recovery costs. We point out properties of these solutions and analyze special cases in which the outcome of the procedure coincides with the optimal solutions to (RecOpt). In an experimental study, we apply our approach to linear programs, and to the problem of finding aperiodic train timetables. We compare it to other robustness concepts, and discuss their tradeoffs with respect to multiple evaluation criteria.