TY - JOUR

T1 - A comment on “computational complexity of stochastic programming problems”

AU - Hanasusanto, Grani A.

AU - Kuhn, Daniel

AU - Wiesemann, Wolfram

N1 - Publisher Copyright:
© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

PY - 2016/9/1

Y1 - 2016/9/1

N2 - Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Program A 106(3):423–432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is governed by independent uniform distributions. We show that Dyer and Stougie’s proof is not correct, and we offer a correction which establishes the stronger result that even the approximate solution of such problems is #P-hard for a sufficiently high accuracy. We also provide new results which indicate that linear two-stage stochastic programs with random recourse seem even more challenging to solve.

AB - Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Math Program A 106(3):423–432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is governed by independent uniform distributions. We show that Dyer and Stougie’s proof is not correct, and we offer a correction which establishes the stronger result that even the approximate solution of such problems is #P-hard for a sufficiently high accuracy. We also provide new results which indicate that linear two-stage stochastic programs with random recourse seem even more challenging to solve.

KW - Complexity theory

KW - Stochastic programming

KW - Two-stage problems

UR - http://www.scopus.com/inward/record.url?scp=84944929440&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944929440&partnerID=8YFLogxK

U2 - 10.1007/s10107-015-0958-2

DO - 10.1007/s10107-015-0958-2

M3 - Article

AN - SCOPUS:84944929440

SN - 0025-5610

VL - 159

SP - 557

EP - 569

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -