Adjustable robust optimization with objective uncertainty

Jointly with Boris Detienne, Enirco Malaguti, Michele Monaci

Year: 2023

Abstract: In this work, we study optimization problems where some cost parameters are not known at decision time and the decision flow is modeled as a two-stage process within a robust optimization setting. We address general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and involve mixed-integer variables, thus extending the existing literature to a much wider class of problems. We show how these problems can be reformulated using Fenchel duality, allowing to derive an enumerative exact algorithm, for which we prove asymptotic convergence in the general case, and finite convergence for cases where the first-stage variables are all integer.

An implementation of the resulting algorithm, embedding a column generation scheme, is then computationally evaluated on a variant of the Capacitated Facility Location Problem with uncertain transportation costs, using instances that are derived from the existing literature. To the best of our knowledge, this is the first approach providing results on the practical solution of this class of problems.

Cite as:

@article{Detienne2024,
  title = {Adjustable robust optimization with objective uncertainty},
  volume = {312},
  ISSN = {0377-2217},
  DOI = {10.1016/j.ejor.2023.06.042},
  number = {1},
  journal = {European Journal of Operational Research},
  publisher = {Elsevier BV},
  author = {Detienne,  Boris and Lefebvre,  Henri and Malaguti,  Enrico and Monaci,  Michele},
  year = {2024},
  X_month = {jan},
  pages = {373--384}
}

Open Access

Optimization Online

Open Data

The instances for the FLP application are available on our GitHub. Go to FLP instances

Open Methodology

Nothing to report here.

Open Source

Our code is publicly available on the GitHub repository hlefebvr/AB_AdjustableRobustOptimizationWithObjectiveUncertainty

Open Educational Resources

Nothing to report here.