Open Collections

Data-Driven Two-Stage Linear Optimization: Feasibility and Approximation Guarantees

Banff International Research Station for Mathematical Innovation and Discovery

An important and challenging class of two-stage linear optimization problems are those without relative-complete recourse, wherein there exists first-stage decisions and realizations of the uncertainty for which there are no feasible second-stage decisions. Previous data-driven methods for these problems, such as the sample average approximation (SAA), are asymptotically optimal but have prohibitively poor performance with respect to out-of-sample feasibility. In this talk, we present a data-driven method for two-stage linear optimization problems without relative-complete recourse which combines (i) strong out-of-sample feasibility guarantees and (ii) general asymptotic optimality. Our method employs a simple robustification of the data combined with a multi-policy approximation. A key contribution of this work is the development of novel geometric insights, which we use to show that the proposed approximation is asymptotically optimal. We demonstrate the benefit of using this method in practice through numerical experiments. This is a joint work with Dimitris Bertsimas and Brad Sturt.

Mathematics; Operations research, mathematical programming; Computer science; Applied computer science

video/mp4

Author affiliation: Technion

2019-07-16

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/71010

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/