A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides

Guanglin Xu, Samuel Burer

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)33-59
Number of pages27
JournalComputational Optimization and Applications
Volume70
Issue number1
DOIs
StatePublished - May 1 2018

Keywords

  • Bilinear programming
  • Copositive programming
  • Non-convex quadratic programming
  • Robust optimization
  • Semidefinite programming
  • Two-stage adjustable robust optimization

Fingerprint Dive into the research topics of 'A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides'. Together they form a unique fingerprint.

Cite this