EURO 2025 Leeds
Abstract Submission

1695. Two notions of regret in problems with uncertainties in objective function and feasibility space

Invited abstract in session WC-31: Solution Algorithms for Optimization under Uncertainty 2, stream Stochastic and Robust optimization.

Wednesday, 12:30-14:00
Room: Maurice Keyworth 1.06

Authors (first author is the speaker)

1. Dimitri Hubans
Enac
2. Laurent houssin
LAAS-CNRS
3. Sonia Cafieri
ENAC - Ecole Nationale d'Aviation Civile

Abstract

In a robust optimization framework, the goal is to find a solution that is robust to uncertainty in the sense that it is feasible and of good quality in all scenarios. In the literature, many problems consider uncertainty only in the objective function. In such cases, optimization is performed either through optimizing the worst case or optimizing the regret. However, when uncertainties lie both in the objective function and the constraints, another notion of regret appears. As far as we know, this alternative notion of regret has not been addressed in the literature. This second notion of regret compares solutions computed under uncertainties to solutions that are only robust to the uncertainties on the feasible space while considering a deterministic objective function. The two notions of regret may appear similar at a first glance but yield different properties. In particular we can find rather simple problems in which optimizing one or the other regret gives different solutions. In this presentation we rigorously define the two notions of regret. We use a classical problem as an example: the knapsack problem. We address the problem under uncertainty, where uncertainties are in both the weight and the profit of each item. We show on some instances of this problem that the optimization of the two different regrets gives different solutions. We also discuss some differences arising in the solution methods for the two versions of the problem.

Keywords

Status: accepted

Back to the list of papers