TY - GEN
T1 - The computational complexity of stochastic optimization
AU - de Campos, Cassio Polpo
AU - Stamoulis, Georgios
AU - Weyland, Dennis
PY - 2014
Y1 - 2014
N2 - This paper presents an investigation on the computational complexity of stochastic optimization problems. We discuss a scenario-based model which captures the important classes of two-stage stochastic combinatorial optimization, two-stage stochastic linear programming, and two-stage stochastic integer linear programming. This model can also be used to handle chance constraints, which are used in many stochastic optimization problems. We derive general upper bounds for the complexity of computational problems related to this model, which hold under very mild conditions. Additionally, we show that these upper bounds are matched for some stochastic combinatorial optimization problems arising in the field of transportation and logistics.
AB - This paper presents an investigation on the computational complexity of stochastic optimization problems. We discuss a scenario-based model which captures the important classes of two-stage stochastic combinatorial optimization, two-stage stochastic linear programming, and two-stage stochastic integer linear programming. This model can also be used to handle chance constraints, which are used in many stochastic optimization problems. We derive general upper bounds for the complexity of computational problems related to this model, which hold under very mild conditions. Additionally, we show that these upper bounds are matched for some stochastic combinatorial optimization problems arising in the field of transportation and logistics.
KW - Chance constraints
KW - Computational complexity
KW - Stochastic combinatorial optimization
KW - Stochastic vehicle routing
UR - http://www.scopus.com/inward/record.url?scp=84905863953&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-09174-7_15
DO - 10.1007/978-3-319-09174-7_15
M3 - Conference contribution
SN - 9783319091730
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 173
EP - 185
BT - Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers
PB - Springer
T2 - 3rd International Symposium on Combinatorial Optimization, ISCO 2014
Y2 - 5 March 2014 through 7 March 2014
ER -