OUZIA Hacène

دكـتور
وحـدة : DECISION
تاريـخ المـغادرة : 31/08/2009
https://lip6.fr/Hacene.Ouzia

رئاسـة البـحث : Michel MINOUX

Hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1 : théorie et applications

Dans cette thèse, nous abordons les liens entre diverses hiérarchies de relaxations semi-algébriques pour des programmes linéaires mixtes 0-1. Parmi celles-ci, citons la hiérarchie de Sherali-Adams (S&A) et la hiérarchie Lift-and-Project (L&P). Tout d'abord, nous montrons que la hiérarchie L&P est semi-algébrique. Puis, nous introduisons une nouvelle hiérarchie de relaxations semi-algébriques, dite SRL*, intermédiaire entre les hiérarchies S&A et L&P. Nous examinons les liens entre les hiérarchies L&P et SRL*. Nous aborderons comment renforcer la description linéaire d'une relaxation L&P pour qu'elle coïncide avec celle d'une relaxation SRL*. Nous montrons aussi que toute relaxation S&A s'obtient en renforçant une relaxation SRL* par des contraintes dites « conditions de symétries ». Nous étayons notre analyse par des résultats de calculs préliminaires comparant le renforcement des relaxations L&P, S&A et SRL* de rang 2. Ensuite, nous caractérisons les programmes linéaires mixtes 0-1 pour lesquels les hiérarchies S&A et SRL* coïncident. Comme application, nous prouverons que les hiérarchies SRL* et S&A coïncident pour l'optimisation d'une fonction pseudo booléenne sur un polyèdre quelconque. Pour illustrer cette propriété nous présentons des résultats de calculs préliminaires sur des instances MINCUT avec contraintes de cardinalité. Enfin, nous présentons des expériences de calcul concernant les renforcements procurés par des relaxations L&P de rang 2 et 3 sur des instances Max-2SAT et Max-3SAT. Nous explorons également, la possibilité d'utiliser des relaxations L&P partielles.
Mots clés : Programmation en nombres entiers mixtes, Relaxation SRL, Optimisation combinatoire, Programmation disjonctive, Lift-and-Project, Relaxations RLT, Optimisation pseudo booléenne, Problème Max-SAT.

مناقـشـة مـذكـرة : 23/10/2008

أعـضاء لجنة المناقـشة :

A. R. Mahjoub, Professeur, Université Paris Dauphine (Rapporteur)
G. Cornuéjols, Professeur, Carnegie Mellon University (Rapporteur)
M. Minoux, Professeur, Université Paris 6 (Directeur de thèse)
P. Perny, Professeur, Université Paris 6 (Président du jury)
P. Bonami, Chargé de recherche CNRS au LIF, Marseille (Examinateur)
V. H. Nguyen, Maître de conférences, Université Paris 6 (Examinateur)

→ أسـتاذ مـحاضر

إصدارات 2004-2023

Mentions légales
خـريـطـة المـوقـع