# Deux notions de regrets en optimisation robuste

Dimitri Hubans, Sonia Cafieri, Laurent Houssin

► To cite this version:

Dimitri Hubans, Sonia Cafieri, Laurent Houssin. Deux notions de regrets en optimisation robuste. ROADEF 2026, Université de Tours [UT], Feb 2026, Tours, France. hal-05534843

HAL Id: hal-05534843

https://hal.science/hal-05534843v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Deux notions de regret en optimisation robuste

Dimitri Hubans¹, Sonia Cafieri¹, Laurent Houssin¹

ENAC, Toulouse

`{dimitri.hubans, sonia.cafieri, laurent.houssin}@enac.fr`

**Mots-clés** : *optimisation robuste, minmax regret, optimisation combinatoire*

## 1 Introduction

L'optimisation robuste est une façon d'aborder un problème d'optimisation qui permet de prendre en compte l'incertitude sur les paramètres du problème. Dans ce cadre, on considère un ensemble de scénarios, chaque scénario correspond à une valeur des paramètres incertains. Dans cette optique, on souhaite alors que la solution obtenue soit réalisable pour tous les scénarios, et que la valeur de sa fonction objectif optimise son pire cas parmi tous les scénarios. L'inconvénient majeur de ce paradigme est que la solution obtenue considère des scénarios trop extrêmes et que soit donc trop consevratrice. Pour cette raison, de nombreuses méthodes de construction d'ensemble de scénarios ont été développées, [5] en fait efficacement la synthèse. Cependant, une autre approche évitant le conservatisme des solutions est de considérer une autre forme d'objectif. Au lieu de seulement chercher à optimiser la valeur de la solution dans son pire cas, on cherche à minimiser son regret maximal. De façon classique, le regret d'une solution vis-à-vis d'un scénario est la différence entre la valeur de la solution dans ce scénario et la valeur de la meilleure solution possible de ce scénario. Cette notion est bien définie dans les cas où l'incertitude n'est présente que dans la fonction objectif ([5, 7]). Cependant, quand les contraintes et l'objectifs sont tous les deux entâchés d'incertitude, la notion de regret peut être définie de deux façons différentes. Ces deux définitions différent par l'ensemble de solution que l'on considère pour déterminer la valeur optimale de chaque scénario. On introduit alors deux notions de regrets : le regret optimiste et le regret pessimiste.

## 2 Définitions classiques

Considérons un problème d'optimisation linéaire déterministe : $\max_{x \in \mathcal{F}} c^t x$ où $\mathcal{F} = \{x \in \mathbb{R}^n | Ax \leq b\}$ avec $c \in \mathbb{R}^n$, $b \in \mathbb{R}^m$ et $A \in \mathbb{R}^{n \times m}$. On considère alors un ensemble $S$ de scénarios pour les paramètres incertains $A$ et $c$.

- L'ensemble des solutions réalisables pour le scénario $s$ est noté : $\mathcal{F}^s := \{x \in \mathbb{R}^n | A^s x \leq b\}$, où $A^s$ est la matrice des contraintes dans le scénario $s$.

- L'ensemble des solutions robustes est alors : $\mathcal{F}^{\cap} := \bigcap_{s \in S} \mathcal{F}^s$.

- L'ensemble des solutions partiellement réalisables est : $\mathcal{F}^{\cup} := \bigcup_{s \in S} \mathcal{F}^s$.

- Dans le cas où $\mathcal{F}^{\cap} = \mathcal{F}^{\cup} = \mathcal{F}$ (i.e. le cas sans incertitude en contraintes), le regret d'une solution $x$ par rapport au scénario $s$ est : $R(x, s) := \max_{x^* \in \mathcal{F}} c^s x^* - c^s x$.

## 3 Enjeux

Dans la littérature la plupart des études consacrées au regret considèrent seulement de l'incertitude dans la fonction objectif. Si l'incertitude ne porte que sur les contraintes, alors on verra que la définition de regret reste applicable même si elle n'apporte aucune plus value vis-à-vis de l'optimisation du pire cas. Nous nous intéressons donc ici au cas où l'incertitude est à la fois sur les contraintes et sur la fonction objectif. On définit alors deux notions de regrets.
— Le regret optimiste de $x$ dans le scénario $s$ est $R_O(x, s) := \max_{x^* \in \mathcal{F}^*} c^s x^* - c^s x$.

— Le regret pessimiste de $x$ dans le scénario $s$ est $R_P(x, s) := \max_{x^* \in \mathcal{F}^\cap} c^s x^* - c^s x$.

Le regret optimiste correspond donc à un regret par rapport aux solutions partiellement réalisables, tandis que le regret pessimiste est un regret par rapport aux solutions robustes.

Ces deux dernières définitions ne sont pas (à notre connaissance) introduites dans la littérature, il existe plusieurs cas d'utilisation de la notion de regret optimiste (voire par exemple [1, 2, 3, 6]), cependant, un seul article utilise le regret pessimiste (voire [4]).

Nous proposons d'étudier plusieurs exemples numériques simples permettant d'identifier certaines propriétés de ces deux notions. Ces exemples numériques sont construits sur des variantes incertaines du problème du sac à dos. Ils ont été construits de telle sorte que les différents paradigmes de l'optimisation robuste (pire cas, regret optimiste et regret pessimiste) soient tous optimisés par des solutions différentes, ce qui permettra d'illustrer certaines caractéristiques de ces notions et pourra aider au choix du paradigme le plus pertinent pour chaque problème d'optimisation. Pour finir, nous nous intéressons aux différences qu'engendrent ces définitions pour les méthodes de résolution, à la fois en terme théorique (mise en place des méthodes) et pratique (temps moyen nécessaire à la résolution).

Références

[1] Nectati Aras and Ümit Bilge Robust supply chain network design with multi-products for a company in the food sector. Applied mathematical modelling, 2018, vol. 60,

[2] Christian Artigues, Roel Leus and Frabrice Talla Nobibon Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flexible Services and Manufacturing Journal 25 (2013)

[3] T. Assavapokee, M.J. Realff and J.C. Ammons Min-Max Regret Robust Optimization Approach on Interval Data Uncertainty Journal of Optimization Theory and Applications, 2008, vol. 137, no 2

[4] Eduardo Conde and Marina Leal A robust optimization model for distribution network design under a mixed integer set of scenarios Computers & Operations Research 136 (2021)

[5] Marc Goerigk and Anita Schöbel. Algorithm engineering in Robust Optimization. Algorithm engineering : selected results and surveys. Cham : Springer International Publishing, 2016. p. 245-279.

[6] Adam Kasperski and Pawel Zielenski Minmax (regret) scheduling problems. Sequencing and scheduling with inaccurate data, 2014

[7] Panos Kouvelis and Yu. Robust discrete optimization and its applications. Vol 14. Springer science & Business Media, 2013.