Optimization Online


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

Guanglin Xu (guanglin-xu***at***uiowa.edu)
Samuel Burer (samuel-burer***at***uiowa.edu)

Abstract: 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 investigate several examples from the literature demonstrating that our tractable approximations significantly improve the affine policy. In particular, our approach solves exactly in polynomial time a class of instances of increasing size for which the affine policy admits an arbitrarily large gap.

Keywords: Two-stage adjustable robust optimization, robust optimization, bilinear programming, non-convex quadratic programming, semidefinite programming, copositive programming

Category 1: Robust Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Other Topics (Dynamic Programming )


Download: [PDF]

Entry Submitted: 09/23/2016
Entry Accepted: 09/23/2016
Entry Last Modified: 05/20/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society