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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

4 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers
Uitgeverij	Springer
Pagina's	173-185
Aantal pagina's	13
ISBN van geprinte versie	9783319091730
DOI's	https://doi.org/10.1007/978-3-319-09174-7_15
Status	Gepubliceerd - 2014
Extern gepubliceerd	Ja
Evenement	3rd International Symposium on Combinatorial Optimization, ISCO 2014 - Lisbon, Portugal Duur: 5 mrt. 2014 → 7 mrt. 2014

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8596 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	3rd International Symposium on Combinatorial Optimization, ISCO 2014
Land/Regio	Portugal
Stad	Lisbon
Periode	5/03/14 → 7/03/14

Toegang tot document

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

Andere bestanden en links

Link to publication in Scopus

Citeer dit

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 (blz. 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. blz. 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, blz. 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. blz. 173-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8596 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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. blz. 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

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit