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

Electronic data


Text available via DOI:

View graph of relations

Representative scenario construction and preprocessing for robust combinatorial optimization problems

Research output: Contribution to journalJournal articlepeer-review

E-pub ahead of print
<mark>Journal publication date</mark>29/10/2018
<mark>Journal</mark>Optimization Letters
Number of pages15
Publication StatusE-pub ahead of print
Early online date29/10/18
<mark>Original language</mark>English


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%.

Bibliographic note

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