TY - JOUR
T1 - Duality gaps in nonconvex stochastic optimization
AU - Dentcheva, Darinka
AU - Römisch, Werner
PY - 2004
Y1 - 2004
N2 - We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.
AB - We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.
KW - Decomposition
KW - Duality gap
KW - Integer programming
KW - Lagrangian relaxation
KW - Nonconvex optimization
KW - Stochastic programming
UR - http://www.scopus.com/inward/record.url?scp=10044238568&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=10044238568&partnerID=8YFLogxK
U2 - 10.1007/s10107-003-0496-1
DO - 10.1007/s10107-003-0496-1
M3 - Article
AN - SCOPUS:10044238568
SN - 0025-5610
VL - 101
SP - 515
EP - 535
JO - Mathematical Programming
JF - Mathematical Programming
IS - 3
ER -