Home > Research > Publications & Outputs > Minmax regret combinatorial optimization proble...

Associated organisational unit

Electronic data

  • source

    Rights statement: This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 258, 1, 2017 DOI: 10.1016/j.ejor.2016.10.055

    Accepted author manuscript, 474 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

View graph of relations

Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>1/04/2017
<mark>Journal</mark>European Journal of Operational Research
Issue number1
Volume258
Number of pages12
Pages (from-to)58-69
Publication StatusPublished
Early online date4/11/16
<mark>Original language</mark>English

Abstract

We consider robust counterparts of uncertain combinatorial optimization problems, where the difference to the best possible solution over all scenarios is to be minimized. Such minmax regret problems are typically harder to solve than their nominal, non-robust counterparts. While current literature almost exclusively focuses on simple uncertainty sets that are either finite or hyperboxes, we consider problems with more flexible and realistic ellipsoidal uncertainty sets. We present complexity results for the unconstrained combinatorial optimization problem, the shortest path problem, and the minimum spanning tree problem. To solve such problems, two types of cuts are introduced, and compared in a computational experiment.

Bibliographic note

This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 258, 1, 2017 DOI: 10.1016/j.ejor.2016.10.055