The computational complexity of stochastic optimization

Cassio Polpo de Campos, Georgios Stamoulis, Dennis Weyland

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
1 Downloads (Pure)


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.

Original languageEnglish
Title of host publicationCombinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers
Number of pages13
ISBN (Print)9783319091730
Publication statusPublished - 2014
Externally publishedYes
Event3rd International Symposium on Combinatorial Optimization, ISCO 2014 - Lisbon, Portugal
Duration: 5 Mar 20147 Mar 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8596 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference3rd International Symposium on Combinatorial Optimization, ISCO 2014


  • Chance constraints
  • Computational complexity
  • Stochastic combinatorial optimization
  • Stochastic vehicle routing


Dive into the research topics of 'The computational complexity of stochastic optimization'. Together they form a unique fingerprint.

Cite this