Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique
A semi-infinite constraint generation algorithm for two-stage robust optimization problems
Patxi Flambard
( Centre Inria de l'Universite de Bordeaux/IMB )Salle 2
le 17 avril 2025 à 11:00
In this talk we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse.
These problems have been the subject of exact solution approaches, notably, constraint generation (CG) and constraint-and-column generation (CCG).
Both approaches repose on an exponential-sized reformulation of the problem which uses a large number of constraints or constraints and variables.
The decomposition algorithms then solve and reinforce a relaxation of the aforementioned reformulation through the iterations which require the solution of bilinear separation problems.
Here, we present an alternative approach reposing on a novel reformulation of the problem with an exponential number of semi-infinite constraints. We present a nested decomposition algorithm to deal with the exponential and semi-infinite natures of our formulation separately.
We argue that our algorithm will lead to a reduced number of bilinear separation problems solved while providing a high quality relaxation.
We perform a detailed numerical study that showcases the superior performance of our proposed approach compared to the state-of-the-art and evaluates the contribution of different algorithmic components.