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

Guanglin Xu () and Samuel Burer ()
Additional contact information
Guanglin Xu: University of Iowa
Samuel Burer: University of Iowa

Computational Optimization and Applications, 2018, vol. 70, issue 1, No 2, 33-59

Abstract: 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 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-017-9974-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:70:y:2018:i:1:d:10.1007_s10589-017-9974-x

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-017-9974-x

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().