A. Métaheuristique de Recherche à Voisinage Variable

De très nombreux problèmes d’exploitation des données sont trop ardus ou de trop grandes tailles pour pouvoir être résolus exactement. Il est donc nécessaire de recourir à des heuristiques qui donnent en un temps modéré ou raisonnable une solution proche de l’optimum (ou parfois optimale mais sans que la preuve de son optimalité ne soit faite). Les problèmes étant très nombreux et les heuristiques encore plus, il est nécessaire pour étudier rigoureusement ces dernières de recourir à des cadres généraux pour la construction d’heuristiques, appelés métaheuristiques. Les métaheuristiques telles que la recherche génétique, le recuit simulé, la recherche avec tabou, la recherche à voisinages variables, les colonies de fourmis et d’autres, connaissent un vif succès depuis une vingtaine d’années. Même si les résultats théoriques sont rares et parfois peu pertinents, les progrès pratiques dans la résolution de multiples problèmes difficiles leur assurent succès et pérennité.

La recherche à voisinages variables (RVV) est une métaheuristique inventée et mise au point au GERAD, Montréal, par Nenad Mladenović et Pierre Hansen. Cette métaheuristique exploite systématiquement le changement de voisinage tant dans une méthode de descente vers un optimum local, que dans des perturbations qui permettent de sortir de la vallée correspondante. Sa simplicité et sa généralité permettent de l’appliquer tant pour les problèmes combinatoires que pour l’optimisation globale en variables discrètes et/ou continues. Plusieurs résultats notables seront discutés ci-dessous.

La RVV a servi de cadre pour le développement de méthodes de résolution approchée pour les trois classes de problèmes de l’analyse de données citées plus haut, ainsi que pour de nombreux problèmes proches dans les domaines, entre autres, de la localisation, la distribution, l’ordonnancement et la théorie des graphes. Son succès est attesté par de nombreuses citations (l’article originel sur la RVV paru dans Computers and Operations Research en 1997 a été cité 768 fois d’après Web of Knowledge et 2076 fois d’après Google scholar).

La 18e mini-conference EURO, organisée à Tenerife du 3 au 5 novembre 2005, était entièrement consacrée à la RVV. Les participants ont présenté 5 conférences plénières et 50 communications. Les meilleures d’entre elles ont été publiées dans trois numéros spéciaux d’European Journal of Operational Research, IMA Journal of Management Mathematics, Journal of Heuristics. De même, la 28ième Mini Conférence EURO organisée à Herceg Novi, Montenegro, 4–7 octobre 2012, a été entièrement consacrée à la RVV. Enfin, une troisième conférence internationale sur la RVV s’est tenue du 8 au 11 octobre 2014 à Djerba, Tunisie. Plus de 70 chercheurs venus de 19 pays ont présenté 4 conférences plénières et une cinquantaine de communications.

B. Le système AutoGraphiX (AGX)

Peu après la découverte de la RVV, Gilles Caporossi et Pierre Hansen ont compris qu’elle pouvait être utilisée pour résoudre efficacement une série de problèmes de théorie des graphes :

  1. Déterminer un graphe satisfaisant des contraintes données sur des invariants tels que le diamètre, le rayon, le nombre de stabilité, le nombre chromatique, le degré maximum, moyen ou minimum, etc.
  2. Déterminer un graphe maximisant ou minimisant la valeur d’un invariant sous des contraintes.
  3. Corroborer, réfuter ou réparer une conjecture.
  4. Découvrir de nouvelles conjectures.
  5. Prouver des résultats simples ou donner des idées de preuves dans des cas plus difficiles.

L’intuition de base est que l’on peut considérer tous ces problèmes comme des problèmes d’optimisation combinatoire, paramétrisés par le nombre de sommets et/ou d’arêtes sur une famille infinie de graphes (en pratique, on n’examinera que ceux de taille modérée). De plus, les problèmes résultants peuvent être résolus de manière approchée par une heuristique générique. Il n’est donc plus nécessaire de construire un algorithme spécifique pour chaque classe de problème. La mise en œuvre de ces idées fondamentales a mené au système AutoGraphiX (AGX). Dans celui-ci, les voisinages consistent en la suppression, l’addition ou le déplacement d’une ou plusieurs arêtes, etc. La famille de graphes obtenus est alors analysée par une ou plusieurs de trois approches d’exploitation des données : une méthode numérique basée sur l’analyse en composantes principales donnant des relations affines entre invariants, une méthode géométrique recherchant la fermeture convexe des points représentant les graphes dans l’espace des invariants et donnant des inégalités linéaires correspondant à chaque facette, et enfin, une méthode analytique consistant à reconnaître la ou les familles de graphes extrêmes et à utiliser une base de relations exprimant la valeur des invariants considérés en fonction de l’ordre du graphe pour obtenir de nouvelles relations.

Ce programme de recherche a beaucoup progressé depuis 2009. D’une part, le programme AGX2, modulaire et écrit en C++, a succédé au programme AGX originel trop influencé par les premiers pas dans son élaboration. Ce travail a été réalisé principalement par Gilles Caporossi et une série de stagiaires français de l’ISIMA, Clermont-Ferrand et de l’ENAC, Toulouse.  D’autre part, pour évaluer la performance du nouvel outil ainsi créé, Mustapha Aouchiche a étudié les relations de la forme AGX1, c’est-à-dire, Formule_Mathematiques_PH_1

i1 et i2 sont des invariants,  Symbole_Mathematiques_PH_1 une des quatre opérations de l’arithmétique, l(n) et u(n) des bornes inférieures et supérieures les meilleures possibles dépendant seulement du nombre n de sommets des graphes considérés. Mustapha Aouchiche a considéré 20 invariants usuels, ce qui correspond à 1520 cas. Dans tous, sauf 60, des résultats ont été obtenus. Plus de 850 conjectures ont été prouvées automatiquement et plus de 400 à la main, avec l’aide de plusieurs spécialistes de la théorie des graphes (voir article accepté 2, articles parus 7, 8, 10, 13, 16, 18, 27, 29, 31, 32, 33, 50, 52, 57, 72, 73, 75 et articles soumis 3, 10, 11, 12). Plus d’une centaine de ces conjectures demeurent encore ouvertes.

Toujours dans le cadre des applications du système AutoGraphiX, Pierre Hansen et Mustapha Aouchiche ont introduit et initié l’étude de deux nouveaux outils pour l’investigation des propriétés des graphes connexes: le laplacien des distances  DL=Tr – D et le laplacien sans signe des distances DL=Tr + D , où  D est la matrice des distances d’un graphe connexe et Tr est la matrice indexé par les sommets du graphe et dont les éléments diagonaux sont les transmissions (somme des distances à partir d’un sommets vers tous les autres sommets) des sommets du graphs (voir les articles publié 27, accepté 2 et soumis 10). Moins d’une année après sa publication, l’article initiant cette étude suscite déjà l’intérêt de plusieurs chercheurs en théorie des graphes.

AGX a aussi été utilisé interactivement pour aider à prouver une conjecture surprenante et très difficile obtenue par Siemion Fajtlowicz à l’aide du système Graffiti, et ouverte depuis 2000 environ : la distance moyenne entre sommets d’un graphe ne dépasse jamais la moitié de la cardinalité d’un sous-graphe biparti induit maximum. De fait, une preuve de plus de 20 pages d’un résultat un peu plus fort (la distance moyenne entre sommets d’un graphe ne dépasse jamais la moitié de la cardinalité d’une forêt induite maximum) a été obtenue au bout de 3 ans  de travail (mais pas à plein temps!) par une équipe de 5 chercheurs (voir article publié 1).

C. Programmation quadratique non convexe

De très nombreux problèmes d’exploitation des données et de recherche opérationnelle s’expriment sous la forme de programmes non convexes, c’est-à-dire ayant plusieurs et souvent de très nombreux optima locaux. Ils ont longtemps été considérés comme étant hors de portée. Cependant, de nombreuses approches ont été proposées soit pour résoudre exactement des instances avec un petit nombre de variables (actuellement de l’ordre d’une centaine sauf si le problème présente une structure particulière) ou pour résoudre de manière approchée des problèmes de plus grande taille. Pierre Hansen et son équipe ont contribué à plusieurs approches. Avec Emilio Carrizosa (Séville), Frédéric Messine, Jean-Louis Lagouanelle et Jordan Ninin (Toulouse), Pierre Hansen a développé plusieurs méthodes basées sur l’analyse d’intervalles (voir articles parus 14 et 88). Cette approche donne des résultats garantis par des bornes sur l’erreur maximum.

L’algorithme QP, développé dans la thèse de Charles Audet dirigée par Pierre Hansen et Gilles Savard, et présentée à l’école Polytechnique de Montréal en 1997, permet de résoudre des programmes à contraintes quadratiques non convexes. Une version améliorée du logiciel correspondant a été présentée dans la thèse de Sylvain Perron, également présentée à l’école Polytechnique de Montréal et dirigée par Charles Audet et Pierre Hansen. De nouvelles amélioration augmentant la robustesse de cet algorithme ont été présentées dans la thèse de Antony Guillou, dirigée par Pierre Hansen et Sylvain Perron. De plus, plusieurs applications ont été réalisées dans différents domaines :

  1. En exploitation des données: le premier algorithme exact pour le problème de la discrimination par hyperplan minimisant la somme des carrés des distances à l’hyperplan séparateur, des objets mal classés a été obtenu. Ceci a mené à l’étude de la valeur optimale du paramètre p pour ce problème lors de l’utilisation d’une distance Lp.
  2. En finance: le premier algorithme exact pour la programmation par objectifs fractionnaires a également été obtenu.
  3. En recherche opérationnelle: un algorithme pour les problèmes de mélanges à plusieurs étages (pooling problems) a été développé sur la base de la RVV et de QP.
  4. En géométrie discrète: une série de problèmes d’optimisation définis sur les polygones convexes de diamètre ou de périmètre unité, ont été résolus par la conjonction de raisonnements géométriques et de recours à QP. Il s’agit notamment des problèmes de l’octogone de diamètre minimum et de côté unitaire, de l’octogone de diamètre unité et de périmètre maximum, des polygones de périmètre unité et de largeur maximum (voir article paru 2) ainsi que de quelques autres problèmes géométriques et des articles de synthèse sur ce sujet (voir articles parus 2, 3, 6, 19 et 71).

D. Applications de la Recherche à Voisinage Variable

L’emploi de la RVV pour résoudre des problèmes très divers a permis son extension de diverses manières, tant pour résoudre des problèmes d’optimisation combinatoire que des problèmes d’optimisation globale. Les heuristiques obtenues sont très souvent parmi les plus performantes. Ceci semble être dû en large partie à ce que, comme on l’observe empiriquement, les optimums locaux sont souvent concentrés dans une petite partie de l’espace des solutions admissibles. L’exploration des voisinages d’un premier optimum local mène donc souvent à un meilleur optimum et ainsi de suite. Parmi les applications ayant eu le plus de succès, notons :

  1. En exploitation des données: le problème de la classification-régression étudié dans la thèse de Réal Carbonneau dirigée par Pierre Hansen, Gilles Caporossi et Rustam Vahidov (voir articles parus 45, 63 et 85). Dans ce problème, on s’efforce d’obtenir à la fois une partition des entités et classes et la meilleure régression pour les entités de chacune des classes. L’objectif est de minimiser la somme des carrés des erreurs. Réal Carbonneau a exploré trois approches exactes permettant de résoudre optimalement des instances encore plus grande: la programmation logique-quadratique, l’optimisation par séparation répétitive branch and bound inaugurée par Brusco, et enfin la génération de colonnes qui correspond à l’état de l’art. La RVV est utilisée pour trouver rapidement de bonnes solutions pour le problème dans son ensemble ainsi que le sous problème de génération de colonnes.
  2. En recherche opérationnelle: plusieurs problèmes classiques de localisation, par exemple de problème simple de localisation des entrepôts (sans contraintes de capacité) et le problème de la p-mediane également beaucoup étudié en exploitation des données. L’application simultanée de la RVV au primal et au dual de ce problème donne d’excellent résultats c’est-à-dire des solutions quasi-optimales avec une garantie ex post sur l’erreur le plus souvent inférieure à 1% pour des instances ayant près de 90 000 entités (voir article paru 15).
  3. En localisation: le problème de la localisation des franchises afin d’assurer une bonne accessibilité au produits vendus tout en évitant de la « cannibalisation » aux concurrences internes entre les différentes franchises. Plusieurs heuristiques entrant dans la cadre de la RVV ont été étudiées et comparées dans la thèse de Benhaz Saboonchi dirigée par Pierre Hansen et Sylvain Perron (voir article accepté 3 et articles soumis 8 et 9).
  4. En traitement des images: le problème de la quantisation des couleurs.

E. « Matheuristiques »

Les heuristiques et les méthodes exactes sont bien sûr complémentaires. Le rôle positif d’heuristiques utilisées au sein de méthodes exactes a souvent été observé. Réciproquement, notamment sous l’impulsion de l’article de Matteo Fischetti et Andrea Lodi, Math Programming 2003, sur « Local Branching », le rôle de méthodes exactes pour résoudre des étapes d’une heuristique a été mis en évidence. Le développement de ces deux courants fait l’objet de ce qu’on appelle parfois « matheuristics ». Les deux premiers colloques internationaux sur ce sujet ont été organisés à Bertinoro, Italie par Pierre Hansen, Vittorio Maniezzo et Stefan Voss en 2006 et le premier le troisième d’entre eux en 2008. Le rôle de la RVV en matheuristics est bien illustré par un algorithme complexe pour le problème simple de localisation des entrepôts de la recherche opérationnelle (voir article paru 15). Ce problème est très proche du problème de la p-médiane qui est fondamental en classification. L’algorithme utilise la RVV, y compris la décomposition, puis en éliminant un grand nombre de variables grâce aux conditions d’écarts complémentaires, en résolvant ensuite le dual à l’aide d’une solution non admissible obtenue à partir du primal puis de la RVV et d’un algorithme exact spécifique appelée méthode du simplexe glissante, et enfin une procédure d’optimisation par séparation. Il a permis de résoudre exactement des problèmes avec 15000 usagers et 15000 localisations potentielles, soit environ 225 millions de variables.