Recoverable Robustness by Column Generation

Paul Bouman, JM van den Akker, JA Hoogeveen

Research output: Chapter/Conference proceedingConference proceedingAcademicpeer-review

10 Citations (Scopus)

Abstract

Real-life planning problems are often complicated by the occurrence of disturbances, which imply that the original plan cannot be followed anymore and some recovery action must be taken to cope with the disturbance. In such a situation it is worthwhile to arm yourself against common disturbances. Well-known approaches to create plans that take possible, common disturbances into account are robust optimization and stochastic programming. Recently, a new approach has been developed that combines the best of these two: recoverable robustness. In this paper, we apply the technique of column generation to find solutions to recoverable robustness problems. We consider two types of solution approaches: separate recovery and combined recovery. We show our approach on two example problems: the size robust knapsack problem, in which the knapsack size may get reduced, and the demand robust shortest path problem, in which the sink is uncertain and the cost of edges may increase.
Original languageEnglish
Title of host publicationAlgorithms -- ESA 2011
EditorsC. Demetrescu, M.M. Halldorsson
PublisherSpringer-Verlag
Pages215-226
Number of pages12
Volume6942
ISBN (Print)9783642237188
DOIs
Publication statusPublished - 5 Sep 2011

Fingerprint

Dive into the research topics of 'Recoverable Robustness by Column Generation'. Together they form a unique fingerprint.

Cite this