Decomposition approaches for recoverable robust optimization problems

J.M. van den Akker, P.C. Bouman, J.A. Hoogeveen, D.D. Tönissen

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
5 Downloads (Pure)

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 possible disturbances by including recourse actions in your planning strategy. Well-known approaches to create plans that take possible, common disturbances into account are robust optimization and stochastic programming. More recently, another approach has been developed that combines the best of these two: recoverable robustness. In this paper, we solve recoverable robust optimization problems by the technique of branch-and-price. We consider two types of decomposition approaches: separate recovery and combined recovery. We will show that with respect to the value of the LP-relaxation combined recovery dominates separate recovery. We investigate our approach for 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. For each problem, we present elaborate computational experiments. We think that our approach is very promising and can be generalized to many other problems.
Original languageEnglish
Pages (from-to)739-750
JournalEuropean Journal of Operational Research
Volume251
Issue number3
DOIs
Publication statusPublished - 16 Jun 2016

Keywords

  • Recoverable robustness
  • Column generation
  • Branch-and-price
  • Knapsack
  • Shortest path

Cite this

van den Akker, J.M. ; Bouman, P.C. ; Hoogeveen, J.A. ; Tönissen, D.D. / Decomposition approaches for recoverable robust optimization problems. In: European Journal of Operational Research. 2016 ; Vol. 251, No. 3. pp. 739-750.
@article{e6a90fd7d8554b84979e78be3ad58bf4,
title = "Decomposition approaches for recoverable robust optimization problems",
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 possible disturbances by including recourse actions in your planning strategy. Well-known approaches to create plans that take possible, common disturbances into account are robust optimization and stochastic programming. More recently, another approach has been developed that combines the best of these two: recoverable robustness. In this paper, we solve recoverable robust optimization problems by the technique of branch-and-price. We consider two types of decomposition approaches: separate recovery and combined recovery. We will show that with respect to the value of the LP-relaxation combined recovery dominates separate recovery. We investigate our approach for 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. For each problem, we present elaborate computational experiments. We think that our approach is very promising and can be generalized to many other problems.",
keywords = "Recoverable robustness, Column generation, Branch-and-price, Knapsack, Shortest path",
author = "{van den Akker}, J.M. and P.C. Bouman and J.A. Hoogeveen and D.D. T{\"o}nissen",
year = "2016",
month = "6",
day = "16",
doi = "10.1016/j.ejor.2015.12.008",
language = "English",
volume = "251",
pages = "739--750",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "3",

}

Decomposition approaches for recoverable robust optimization problems. / van den Akker, J.M.; Bouman, P.C.; Hoogeveen, J.A.; Tönissen, D.D.

In: European Journal of Operational Research, Vol. 251, No. 3, 16.06.2016, p. 739-750.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Decomposition approaches for recoverable robust optimization problems

AU - van den Akker, J.M.

AU - Bouman, P.C.

AU - Hoogeveen, J.A.

AU - Tönissen, D.D.

PY - 2016/6/16

Y1 - 2016/6/16

N2 - 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 possible disturbances by including recourse actions in your planning strategy. Well-known approaches to create plans that take possible, common disturbances into account are robust optimization and stochastic programming. More recently, another approach has been developed that combines the best of these two: recoverable robustness. In this paper, we solve recoverable robust optimization problems by the technique of branch-and-price. We consider two types of decomposition approaches: separate recovery and combined recovery. We will show that with respect to the value of the LP-relaxation combined recovery dominates separate recovery. We investigate our approach for 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. For each problem, we present elaborate computational experiments. We think that our approach is very promising and can be generalized to many other problems.

AB - 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 possible disturbances by including recourse actions in your planning strategy. Well-known approaches to create plans that take possible, common disturbances into account are robust optimization and stochastic programming. More recently, another approach has been developed that combines the best of these two: recoverable robustness. In this paper, we solve recoverable robust optimization problems by the technique of branch-and-price. We consider two types of decomposition approaches: separate recovery and combined recovery. We will show that with respect to the value of the LP-relaxation combined recovery dominates separate recovery. We investigate our approach for 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. For each problem, we present elaborate computational experiments. We think that our approach is very promising and can be generalized to many other problems.

KW - Recoverable robustness

KW - Column generation

KW - Branch-and-price

KW - Knapsack

KW - Shortest path

U2 - 10.1016/j.ejor.2015.12.008

DO - 10.1016/j.ejor.2015.12.008

M3 - Article

VL - 251

SP - 739

EP - 750

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -