OUZIA Hacène

doctorant à Sorbonne Université
Équipe : DECISION
https://perso.lip6.fr/Hacene.Ouzia

Direction de recherche : 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.


Soutenance : 23/10/2008

Membres du jury :

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)

Maître de Conférences

Publications 2004-2024