15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
15th EUROPT Workshop on Advances in Continuous Optimization
Montréal, Canada, 12 — 14 juillet 2017
Robustness and copositivity
14 juil. 2017 08h45 – 10h00
Salle: Nancy et MichelGaucher
Présidée par Immanuel Bomze
3 présentations

08h45  09h10
A Copositive Approach for TwoStage Adjustable Robust Optimization with Uncertain RightHand Sides
We study twostage adjustable robust linear programming in which the righthand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NPhard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the twostage problem can be reformulated as a copositive optimization problem, which in turn leads to a class of tractable, semidefinitebased approximations that are at least as strong as the affine policy. We validate the effectiveness of our approach over several literature examples.

09h10  09h35
Conic Programming Reformulations of TwoStage Distributionally Robust Linear Programs over Wasserstein Balls
Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximations error can be substantial. In this talk, we show that twostage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, when the ambiguity set constitutes a 2Wasserstein ball centered at a discrete distribution, then the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of twostage problems based on semidefinite approximations of the copositive cone.

09h35  10h00
Linearized robust counterparts of twostage robust optimization problem
We study twostage robust optimization problem wherein some decisions can be made when the actual data is revealed. Since this problem is computationally intractable we propose a conservative tractable approximation scheme for this problem based on linearizing the bilinear terms that appear due to the recourse problem. We relate this new scheme to methods that are based on exploiting affine decision rules. Furthermore, we show that our proposed method can be exploited to provide exact solutions for a family of robust multiitem newsvendor problem. Using a robust operating room allocation problem, we also show how our proposed method can be used to derive conservative approximations that are tighter than existing tractable methods.