TY - JOUR

T1 - Recovery-to-optimality

T2 - A new two-stage approach to robustness with an application to aperiodic timetabling

AU - Goerigk, Marc

AU - Schöbel, Anita

PY - 2014/12

Y1 - 2014/12

N2 - 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 trade-offs with respect to multiple evaluation criteria.

AB - 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 trade-offs with respect to multiple evaluation criteria.

KW - Recoverable robustness

KW - Robust optimization

KW - Robust timetabling

U2 - 10.1016/j.cor.2014.06.025

DO - 10.1016/j.cor.2014.06.025

M3 - Journal article

AN - SCOPUS:84905721019

VL - 52

SP - 1

EP - 15

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - PART A

ER -