Optimisation quadratique en variables binaires : heuristiques et cas polynomiaux

Kim-Alexandre ALLEMAND

Ecole Polytechnique Fédérale de Lausanne
Département de Mathématiques
CH - 1015 Lausanne

Le sujet de cette thèse est l'étude d'un problème d'optimisation combinatoire appelé optimisation quadratique en variables binaires. Il s'agit de trouver l'optimum (le minimum en l'occurence) d'une fonction polynomiale du deuxième degré en n variables, chacune de ces variables ne pouvant prendre que la valeur 0 ou 1 (variable binaire). Bien que simple à énoncer et apparemment tout aussi simple à résoudre, trouver la solution d'un tel problème par une méthode d'énumération est prohibitif du point de vue du temps. Ceci est dû au fait que le nombre de solutions devant être évaluées est démesuré pour des problèmes dont la taille n dépasse (à l'heure actuelle) quelques dizaines. Deux autres approches ont été abordée au cours de cette thèse.

La première consiste à trouver des cas particuliers de la fonction objectif pour lesquels la solution peut être déterminée en temps polynomial (cas réputés solubles). Le nouveau cas polynomial que nous présentons correspond aux instances dont la représentation quadratique pure de la fonction objectif est symétrique, semi-définie négative et de rang fixe. Nous proposons plusieurs algorithmes spécifiques de résolution ainsi qu'un algorithme général.

La deuxième manière d'aborder le problème d'optimisation quadratique en variables binaires est l'approche heuristique, c'est-à-dire à l'aide d'algorithmes raisonnablement rapides, mais qui ne garantissent pas la qualité de la solution obtenue. Plusieurs auteurs ayant développé des heuristiques fort variées, les réalisations de ces dernières sont extrêmement inhomogènes. Dans un premier temps, nous avons effectué un récapitulatif des composantes heuristiques (fonctionnalités de base communes), tout particulièrement dans le cas des heuristiques itératives. Dans un second temps, nous proposons deux heuristiques appelées respectivement heuristique génétique et heuristique de perturbation.

Finalement, nous présentons les résultats de tests numériques effectués d'après un protocole, de sorte à comparer de manière équitable l'apport des différentes composantes heuristiques. Ces résultats sont comparés aux résultats pouvant être trouvés dans littérature.

Pour plus d'informations, contactez le Professeur Tom Liebling
thomas.liebling@epfl.ch