The computational complexity of stochastic optimization

Cassio Polpo de Campos; Georgios Stamoulis; Dennis Weyland

doi:10.1007/978-3-319-09174-7_15

The computational complexity of stochastic optimization

Cassio Polpo de Campos, Georgios Stamoulis, Dennis Weyland

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

1 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers
Publisher	Springer
Pages	173-185
Number of pages	13
ISBN (Print)	9783319091730
DOIs	https://doi.org/10.1007/978-3-319-09174-7_15
Publication status	Published - 2014
Externally published	Yes
Event	3rd International Symposium on Combinatorial Optimization, ISCO 2014 - Lisbon, Portugal Duration: 5 Mar 2014 → 7 Mar 2014

Publication series

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

Conference

Conference	3rd International Symposium on Combinatorial Optimization, ISCO 2014
Country/Territory	Portugal
City	Lisbon
Period	5/03/14 → 7/03/14

Keywords

Chance constraints
Computational complexity
Stochastic combinatorial optimization
Stochastic vehicle routing

Access to Document

10.1007/978-3-319-09174-7_15

Cite this

de Campos, C. P., Stamoulis, G., & Weyland, D. (2014). The computational complexity of stochastic optimization. In Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers (pp. 173-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8596 LNCS). Springer. https://doi.org/10.1007/978-3-319-09174-7_15

de Campos, Cassio Polpo ; Stamoulis, Georgios ; Weyland, Dennis. / The computational complexity of stochastic optimization. Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers. Springer, 2014. pp. 173-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{abfa326065fb4a5b86507148df310201,

title = "The computational complexity of stochastic optimization",

abstract = "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.",

keywords = "Chance constraints, Computational complexity, Stochastic combinatorial optimization, Stochastic vehicle routing",

author = "{de Campos}, {Cassio Polpo} and Georgios Stamoulis and Dennis Weyland",

year = "2014",

doi = "10.1007/978-3-319-09174-7_15",

language = "English",

isbn = "9783319091730",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "173--185",

booktitle = "Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers",

address = "Germany",

note = "3rd International Symposium on Combinatorial Optimization, ISCO 2014 ; Conference date: 05-03-2014 Through 07-03-2014",

}

de Campos, CP, Stamoulis, G & Weyland, D 2014, The computational complexity of stochastic optimization. in Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8596 LNCS, Springer, pp. 173-185, 3rd International Symposium on Combinatorial Optimization, ISCO 2014, Lisbon, Portugal, 5/03/14. https://doi.org/10.1007/978-3-319-09174-7_15

The computational complexity of stochastic optimization. / de Campos, Cassio Polpo; Stamoulis, Georgios; Weyland, Dennis.
Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers. Springer, 2014. p. 173-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8596 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 -

de Campos CP, Stamoulis G, Weyland D. The computational complexity of stochastic optimization. In Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers. Springer. 2014. p. 173-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-09174-7_15

The computational complexity of stochastic optimization

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this