Linéarisation et relaxation lagrangienne pour problèmes quadratiques en variables binaires
Institution:
AvignonDisciplines:
Directors:
Abstract EN:
A quadratic 0/1 problem is an optimization problem where a quadratic objective function, subject to linear contraints, have to be minimized. In the general case, the problem is NP-Hard and arises in mathematical modeling of several real world applications. Exact methods, for solving the problem, are based on Branch-and-Bound scheme for which the corresponding lower bands may be divided in four groups : Semidefinite Relaxations, Lagrangean Relaxations, Posiform Methods and Linearization Techniques. In this thesis, linearization and lagrangean relaxation techniques have been particularly studied. Two instances of the general quadratic problem have been considered : "the graph bipartitioning problem and the unconstrained quadratic 0/1 problem". For the graph bipartitioning problem, an hybrid scheme, mixing linearization and lagrangean relaxations, have been proposed. The new scheme provides significative improvements compared to the state-of-the-art approaches. For the unconstrained quadratic 0/1 problem, a general linearization framework, unifying and generalizing the existing linearization techniques have been proposed. Based on this new framework, including many linear models, some new linearizations have been tested. In comparison with existing linearizations, many encouraging results have been noticed in the numerical tests
Abstract FR:
Un problème quadratique en variables binaires est un problème d'optimisation en variables binaires consistant à minimiser une fonction objectif quadratique sous des contraintes linéaires. Dans le cas général, c'est un problème dificile à résoudre de manière exacte (NP- difficile), trouvant de nombreuses applications pratiques. La résolution exacte du problème passe par la détermination de bornes inférieures qu'il convient d'intégrer dans des schémas de séparation et évaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de la programmation semi-définie positive à l'optimisation globale, sont utilisées pour déterminer ces bornes. Nous nous sommes particulièrement intéressés aux méthodes lagrangiennes et aux techniques de linéarisation. Nous avons traité dans cette thèse deux instances particulières du problème : "la bipolarisation de graphes avec contrainte de cardinalité" et "le problème quadratique en variables binaires sans contrainte". Pour la bipartition de graphes, nous avons proposé une démarche hybride mêlant relaxation lagrangienne et linéarisation de problème. Les tests numériques, issus de l'algorithme résultant, ont montré des améliorations significatives par rapport à certaines techniques existantes. Pour le problème quadratique en variables binaires sans contrainte, des études sur les techniques de linéarisation ont été effectuées. Elles consistent à remplacer la fonction objectif quadratique par une forme linéaire, grâce à l'ajout de variables permettant de remplacer les parties quadratiques de la fonction. L'ajout de ces variables entraînent [sic] aussi l'ajout de contraintes visant à s'assurer de la validité du remplacement. Après étude et tests des linéarisations existantes, nous unifions ces techniques dans un schéma général de linéarisation. De nouveaux modèles ont, grâce à ce schéma , vu le jour et améliorent significativement les résultats numériques des formulations linéaires précédentes