A Generic Framework for Optimisation under Uncertainty with Recourse: Theory and Examples

Extending the black-box complexity framework, we consider multi-stage stochastic optimisation problems under recourse. Such problems ask for a solution to an optimisation problem under uncertainty, where once the uncertainty is (partially) observed, in one or more stages, a stage-by-stage set of ‘recourse’ actions may be applied to repair the solution. These problems have been studied in the optimisation literature for decades, and applications include multistage portfolio investment, routing under uncertainty, and (dynamic) rescheduling. To facilitate rigorous complexity analysis of these problems in a black-box setting, we develop a precise, broad framework enabling us to describe what information is exchanged between the black-box and the optimisation algorithm, and what solution concept is used. To illustrate the power of the technique, we develop runtime bounds for evolutionary algorithms applied to stochastic optimisation problems with recourse. The theoretical results are complemented by experiments.