Rechercher

[Lam09] Résolution de programmes quadratiques en nombres entiers

Mémoire de Thèse : Soutenue le: 01 January 2009, pp. 150, pp.: Directeur:ALain Billionnet et Sourour Elloumi
Rapporteur 1: Walid Ben Ameur
Rapporteur 2: Franz Rendl
Membre du jury: Pierre Hansen
Membre du jury: Frédéric Roupin
Membre du jury: François Vanderbeck, : Résolution de programmes quadratiques en nombres entiers,

Auteurs: A. Lambert

Mots clés: Binary Programming, General integer programming, Mixed-integer programming, Quadratic programming, Linear Reformulation, Quadratic convex reformulation, Semi-definite programming, Branch and Bound, Experiments

Résumé: Soit (QP) un programme quadratique en variables entières qui consiste à minimiser une fonction quadratique soumise à des contraintes linéaires. Un tel problème appartient à la classe des problèmes NP-difficiles. Les solveurs standards qui utilisent des algorithmes de Branch and Bound peuvent résoudre efficacement (QP) dans le cas particulier où sa fonction objectif est convexe. Ainsi, pour résoudre (QP) nous avons choisi de le reformuler en un programme équivalent ayant une fonction objectif convexe. Deux cas sont alors possibles : soit nous reformulons (QP) en un programme linéaire, soit nous le reformulons en un programme quadratique et convexe. Dans la première partie de cette thèse, nous présentons plusieurs reformulations linéaires de (QP), i.e. reformulations en un programme équivalent qui a une fonction objectif linéaire. Il existe de nombreuses méthodes de linéarisation pour la programmation quadratique binaire. Une approche naturelle pour résoudre (QP) est donc de le reformuler en un programme quadratique en variables binaires. Cela peut être fait en remplaçant chaque variable entière par sa décomposition binaire, puis en linéarisant chaque nouveau produit de variables binaires. Cependant, cette méthode que nous appelons BBL (Binary Binary Linearization), fournit un programme linéaire avec un grand nombre de variables et de contraintes. Nous proposons donc une nouvelle approche, BIL (Binary Integer Linearization), qui consiste à reformuler (QP) en un programme quadratique particulier où chaque terme quadratique est le produit d'une variable entière par une variable binaire. Comme dans la méthode BBL, les variables binaires viennent de la décomposition binaire des variables entières initiales. Ensuite, nous linéarisons le programme obtenu en remplaçant chaque terme quadratique par une variable réelle et un ensemble d'inégalités. Comme le nombre de termes quadratiques est plus petit que dans la méthode BBL, le nombre de variables additionnelles est réduit. Donc, le programme obtenu avec la méthode BIL est significativement plus petit. De plus, contrairement à ce que l'on pourrait attendre, l'approche BIL fournit une borne obtenue par relaxation continue de meilleure qualité que celle fournie par l'approche BBL. Chaque reformulation aboutit à un programme linéaire équivalent à (QP) que nous renforçons en lui ajoutant des inégalités valides. Dans une deuxième partie, nous présentons plusieurs reformulations quadratiques convexes de (QP), i.e. nous reformulons (QP) en un programme équivalent ayant une fonction objectif quadratique et convexe. Nous introduisons d'abord une approche simple pour convexifier (QP) qui consiste à exprimer linéairement les carrés des variables entières en utilisant leurs décompositions unaires, puis à convexifier à l'aide de la plus petite valeur propre du Hessien de la fonction objectif de (QP). Nous appelons cette méthode NC (Naive Convexification). Ensuite, nous introduisons un nouveau schéma de reformulations convexes qui perturbe la fonction objectif à l'aide de l'expression linéaire des produits des variables entières initiales, et des contraintes d'égalité de (QP). Puis nous montrons que nous pouvons calculer au sein de ce schéma une reformulation optimale du point de vue de la borne obtenue par relaxation continue : la reformulation IQCR (Integer Quadratic Convex Reformulation). Cette reformulation est basée sur la solution optimale duale d'une relaxation semi-définie de (QP). De plus, nous montrons que la méthode IQCR peut s'adapter facilement à la programmation mixte entière. Cette adaptation, que nous appelons IQCRs permet également d'intégrer les contraintes d'inégalité dans la perturbation de la fonction objectif de notre schéma de reformulations convexes. Ensuite, nous présentons une restriction intéressante de la méthode IQCR, appelée CQCR (Compact Quadratic Convex Reformulation). La différence entre cette approche et la méthode IQCR est que CQCR n'utilise que les expressions linéaires des carrés des variables pour perturber la fonction objectif, alors qu'IQCR utilise celles de tous les produits. L'intérêt est que de CQCR fournit un programme reformulé de plus petite taille en comparaison avec celui de l'approche IQCR, ce qui peut être avantageux expérimentalement. Finalement, nous appliquons les 3 méthodes NC, CQCR et IQCR à la programmation quadratique binaire. Nous montrons que NC et CQCR sont équivalentes à des méthodes déjà connues. Un résultat intéressant est que IQCR constitue une amélioration des convexifications existantes pour la programmation quadratique binaire. Dans une troisième partie, nous présentons un algorithme de Branch and Bound spécifique basé sur une propriété de projection de la méthode IQCR. Finalement, nous comparons expérimentalement les quatre reformulations linéaires et les trois reformulations quadratiques et convexes de (QP) que nous avons obtenues. Dans le cas où les variables sont entières, les expérimentations concernent deux classes d'instances de (QP), l'une ayant une contrainte d'égalité et l'autre une contrainte d'inégalité. Les résultats montrent que la plupart des instances ayant jusqu'à 40 variables peuvent être résolues en moins d'une heure avec un solveur standard par les reformulations IQCR et CQCR. Nous testons ensuite notre reformulation convexe IQCR sur la programmation quadratique binaire. Les résultats confirment que notre approche IQCR améliore les convexifications existantes.

Equipe: oc
Download

BibTeX

@phdthesis {
Lam09,
title="{Résolution de programmes quadratiques en nombres entiers}",
author="A. Lambert",
year=2009,
pages="150",
address="{CEDRIC Laboratory, Paris, France}",
note="{
Directeur:ALain Billionnet et Sourour Elloumi
Rapporteur 1: Walid Ben Ameur
Rapporteur 2: Franz Rendl
Membre du jury: Pierre Hansen
Membre du jury: Frédéric Roupin
Membre du jury: François Vanderbeck}",
}