L’optimisation robuste (OR) est un cadre populaire pour gérer l’incertitude qui survient dans les problèmes d’optimisation. Essentiellement, l’OR impose que les solutions réalisables satisfassent à chaque contrainte robuste pour toutes les réalisations des paramètres dans un ensemble d’incertitude donné U. Nous considérons dans ce projet l’optimisation robuste combinatoire (ORC), le sous-domaine de l’OR qui étudie les problèmes d’optimisation combinatoire (OC). De plus, nous supposons que l’ensemble d’incertitude est l’ensemble d’incertitude de type budget UΓ introduit par Bertismas et Sim et extrêmement populaire dans la littérature sur l’optimisation combinatoire et l’optimisation dans les réseaux. L’ensemble UΓ considère que chaque paramètre incertain varie entre sa valeur moyenne et sa valeur maximale et que le nombre de paramètres qui atteignent simultanément leur valeur maximale est limité par Γ. Nous dénotons les problèmes d’optimisation qui en résultent par Г-ORC.
L’approche classique de l’OR reformule les contraintes robustes par des reformulations convexes en utilisant, par exemple, la dualité conique ou la dualité de Fenchel. Bien qu’utiles pour les problèmes d’optimisation sans variables discrètes, ces reformulations non-linéaires sont assez limitées pour les problèmes d’optimisation combinatoire, brisant très souvent leurs structures combinatoires. C’est pourquoi deux autres approches ont vu le jour :
* Les approches purement combinatoires telles que le résultat de Bertsimas et Sim (2003) qui montre comment résoudre des problèmes purement binaires min max Г-ORC avec incertitude des coûts en résolvant jusqu’à n fois la contrepartie déterministe, où n est le nombre de variables du problème.
* Les approches de décomposition, qui séparent tout problème Г-ORC en un problème maître (MP) et des problèmes de séparation (S). MP contient les contraintes déterministes ainsi que les contraintes robustes écrites uniquement pour un nombre fini de scénarios. Les problèmes S sont résolus pour vérifier si nous devons étendre le nombre de scénarios utilisés dans MP, ce qui donne lieu à des algorithmes de génération de lignes et de colonnes. Ici, la structure combinatoire de UΓ peut être utilisée pour développer des algorithmes combinatoires efficaces.
L’objectif de cet axe de recherche est d’approfondir ces approches combinatoires. Comme les approches combinatoires sont généralement dépendantes du problème, nous nous concentrons sur des problèmes spécifiques. Des recherches récentes ont porté sur les problèmes de plus court chemins contraints, de planification de lots de production, et d’ordonnancement. En plus des algorithmes de solution exacte, nous étudierons également les algorithmes d’approximation, qui ont été peu appliqués à ce type de problèmes.