Home > Research > Publications & Outputs > Representative scenario construction and prepro...

Research

Associated organisational units

Electronic data

Links

Text available via DOI:

View graph of relations

Representative scenario construction and preprocessing for robust combinatorial optimization problems

Research output: Contribution to Journal/Magazine › Journal article › peer-review

E-pub ahead of print

Standard

Representative scenario construction and preprocessing for robust combinatorial optimization problems. / Goerigk, Marc; Hughes, Martin.
In: Optimization Letters, 29.10.2018.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Goerigk, M & Hughes, M 2018, 'Representative scenario construction and preprocessing for robust combinatorial optimization problems', Optimization Letters. https://doi.org/10.1007/s11590-018-1348-5

APA

Goerigk, M., & Hughes, M. (2018). Representative scenario construction and preprocessing for robust combinatorial optimization problems. Optimization Letters. Advance online publication. https://doi.org/10.1007/s11590-018-1348-5

Vancouver

Goerigk M, Hughes M. Representative scenario construction and preprocessing for robust combinatorial optimization problems. Optimization Letters. 2018 Oct 29. Epub 2018 Oct 29. doi: 10.1007/s11590-018-1348-5

Author

Goerigk, Marc ; Hughes, Martin. / Representative scenario construction and preprocessing for robust combinatorial optimization problems. In: Optimization Letters. 2018.

Bibtex

@article{3e1a2d60196c4d8f861388ab66b6daa1,
title = "Representative scenario construction and preprocessing for robust combinatorial optimization problems",
abstract = "In robust combinatorial optimization with discrete uncertainty, approximation algorithms based on constructing a single scenario representing the whole uncertainty set are frequently used. One is the midpoint method, which uses the average case scenario. It is known to be an N-approximation, where N is the number of scenarios. In this paper, we present a linear program to construct a representative scenario for the uncertainty set, which gives an approximation guarantee that is at least as good as for previous methods. We further employ hyper heuristic techniques operating over a space of preprocessing and aggregation steps to evolve algorithms that construct alternative representative single scenarios for the uncertainty set. In numerical experiments on the selection problem we demonstrate that our approaches can improve the approximation guarantee of the midpoint approach by more than 20%.",
author = "Marc Goerigk and Martin Hughes",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-018-1348-5",
year = "2018",
month = oct,
day = "29",
doi = "10.1007/s11590-018-1348-5",
language = "English",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",

}

RIS

TY - JOUR

T1 - Representative scenario construction and preprocessing for robust combinatorial optimization problems

AU - Goerigk, Marc

AU - Hughes, Martin

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-018-1348-5

PY - 2018/10/29

Y1 - 2018/10/29

N2 - In robust combinatorial optimization with discrete uncertainty, approximation algorithms based on constructing a single scenario representing the whole uncertainty set are frequently used. One is the midpoint method, which uses the average case scenario. It is known to be an N-approximation, where N is the number of scenarios. In this paper, we present a linear program to construct a representative scenario for the uncertainty set, which gives an approximation guarantee that is at least as good as for previous methods. We further employ hyper heuristic techniques operating over a space of preprocessing and aggregation steps to evolve algorithms that construct alternative representative single scenarios for the uncertainty set. In numerical experiments on the selection problem we demonstrate that our approaches can improve the approximation guarantee of the midpoint approach by more than 20%.

AB - In robust combinatorial optimization with discrete uncertainty, approximation algorithms based on constructing a single scenario representing the whole uncertainty set are frequently used. One is the midpoint method, which uses the average case scenario. It is known to be an N-approximation, where N is the number of scenarios. In this paper, we present a linear program to construct a representative scenario for the uncertainty set, which gives an approximation guarantee that is at least as good as for previous methods. We further employ hyper heuristic techniques operating over a space of preprocessing and aggregation steps to evolve algorithms that construct alternative representative single scenarios for the uncertainty set. In numerical experiments on the selection problem we demonstrate that our approaches can improve the approximation guarantee of the midpoint approach by more than 20%.

U2 - 10.1007/s11590-018-1348-5

DO - 10.1007/s11590-018-1348-5

M3 - Journal article

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

ER -