15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

Schedule Authors My Schedule

Robustness and copositivity

Jul 14, 2017 08:45 AM – 10:00 AM

Location: Nancy et Michel-Gaucher

Chaired by Immanuel Bomze

3 Presentations

  • 08:45 AM - 09:10 AM

    A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

    • Guanglin Xu, presenter, The University of Iowa
    • Samuel Burer, The University of Iowa

    We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which in turn leads to a class of tractable, semidefinite-based approximations that are at least as strong as the affine policy. We validate the effectiveness of our approach over several literature examples.

  • 09:10 AM - 09:35 AM

    Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

    • Grani A. Hanasusanto, presenter, The University of Texas at Austin
    • Daniel Kuhn, École Polytechnique Fédérale de Lausanne

    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 two-stage 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 2-Wasserstein 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 two-stage problems based on semidefinite approximations of the copositive cone.

  • 09:35 AM - 10:00 AM

    Linearized robust counterparts of two-stage robust optimization problem

    • Amir Ardestani-Jaafari, presenter, University of British Columbia
    • Erick Delage, GERAD, HEC Montréal

    We study two-stage 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 multi-item 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.