TY - JOUR
T1 - A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
AU - Xu, Guanglin
AU - Burer, Samuel
N1 - Publisher Copyright:
© 2017, Springer Science+Business Media, LLC, part of Springer Nature.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2018/5/1
Y1 - 2018/5/1
N2 - 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.
AB - 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.
KW - Bilinear programming
KW - Copositive programming
KW - Non-convex quadratic programming
KW - Robust optimization
KW - Semidefinite programming
KW - Two-stage adjustable robust optimization
UR - http://www.scopus.com/inward/record.url?scp=85039851683&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85039851683&partnerID=8YFLogxK
U2 - 10.1007/s10589-017-9974-x
DO - 10.1007/s10589-017-9974-x
M3 - Article
AN - SCOPUS:85039851683
VL - 70
SP - 33
EP - 59
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
SN - 0926-6003
IS - 1
ER -