Adjustable robust optimization with discrete uncertainty

Jointly with Enrico Malaguti, Michele Monaci

Year: 2023

Abstract: In this paper, we study Adjustable Robust Optimization (ARO) problems with discrete uncertainty. Under a very general modeling framework, we show that such two-stage robust problems can be exactly reformulated as ARO problems with objective uncertainty only. This reformulation is valid with and without the fixed recourse assumption and is not limited to continuous wait-and-see decision variables, unlike most of the existing literature. Additionally, we extend an enumerative algorithm akin to a branch-and-cut scheme for which we study the asymptotic convergence. We discuss how to apply the reformulation on two variants of well known optimization problems: a Facility Location Problem in which uncertainty may affect the capacity values and a Multiple Knapsack Problem with uncertain weights, and we report extensive computational results demonstrating the effectiveness of the approach.

Cite as:

@article{Lefebvre2024,
  title = {Adjustable Robust Optimization with Discrete Uncertainty},
  volume = {36},
  ISSN = {1526-5528},
  DOI = {10.1287/ijoc.2022.0086},
  number = {1},
  journal = {INFORMS Journal on Computing},
  publisher = {Institute for Operations Research and the Management Sciences (INFORMS)},
  author = {Lefebvre,  Henri and Malaguti,  Enrico and Monaci,  Michele},
  year = {2024},
  X_month = {jan},
  pages = {78--96}
}

Open Access

Optimization Online

Open Data

We have public instances and raw results. The columns in .csv files are explained in the corresponding public rmarkdown (see open methodology) while the instances format is explained in README.md files in the associated .zip.
DisruptionFLP/instances.zip
DisruptionFLP/results_ccg_DisruptionFLP.csv DisruptionFLP/results_benders_DisruptionFLP.csv

Open Methodology

Our R report for the FLP application is available here.

Open Source

Nothing to report here.

Open Educational Resources

  • A scientific poster which was presented at the Mixed Integer Programming Workshop 2022, New York (USA) (MIP_poster.pdf).
  • Slides which were presented at EURO2022 and ROADEF2022 (EURO2022.pdf).
MIP_poster.pdf EURO2022.pdf