Authors: Patxi Flambard, Ayse Nur Arslan, Boris Detienne
Abstract: In this paper, we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse. These problems have been the subject of exact solution approaches, notably constraint generation and constraint-and-column generat
[Read more]
In this talk we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse. These problems have been the subject of exact solution approaches, notably, constraint generation (CG) and constraint-and-column generation (CCG). Both approaches repose on an exponential-sized reformulation of the problem which uses a large number of constraints or constraints and variables. The decomposition algorithms then solve and reinforce a relaxation of the aforementioned reformulation through the iterations which require the solution of bilinear separation problems. Here, we present an alternative approach reposing on a novel reformulation of the problem with an exponential number of semi-infinite constraints. We present a nested decomposition algorithm to deal with the exponential and semi-infinite natures of our formulation separately. We argue that our algorithm will lead to a reduced number of bilinear separation problems solved while providing a high quality relaxation. We perform a detailed numerical study that showcases the superior performance of our proposed approach compared to the state-of-the-art and evaluates the contribution of different algorithmic components.
[Read more]
Robust optimization has evolved as a key paradigm for handling data uncertainty within mathematical optimization problems: it requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. Project DROI proposes to study primal and dual approximations for such problems.
[Read more]