Compte rendu de la 35ème JFRO

par François Delbot, Mathieu Lacroix, Amélie Lambert, Thibaut Lust et Florian Sikora dans le Bulletin #36 de la ROADEF

La 35ème édition des journées Franciliennes de Recherche Opérationnelle s'est déroulée le jeudi 23 juin dernier, dans les locaux du Conservatoire National des Arts et Métiers. Cette journée avait pour thème "Programmation quadratique". Elle a accueilli une quarantaine de participants. Cinq orateurs avaient accepté de faire un exposé. Ils ont présenté leurs travaux portant sur des algorithmes de résolution de problèmes consistant à optimiser une fonction quadratique dans un espace défini par des fonctions quadratiques, et où les variables peuvent être entières et/ou continues. Plusieurs difficultés entrent en jeu dans la résolution de cette classe de problèmes : la non-convexité des fonctions considérées, l'intégrité d'une partie des variables, ou bien encore la taille du problème considéré.

La journée a commencé par un tutoriel, donné par Sourour Elloumi (ENSIIE-SAMOVAR), présentant de nombreuses méthodes de résolutions de problèmes binaires basées sur la reformulation du problème initial en un problème équivalent linéaire ou quadratique convexe. Après avoir dé- fini plusieurs familles de reformulations, elle a montré comment déterminer, pour chaque famille, celle qui est "optimale" du point de vue de la borne obtenue par relaxation continue. Elle a ensuite montré comment étendre ces approches de résolution aux problèmes plus généraux qui possèdent des variables entières et/ou continues. Le premier exposé de l'après-midi a été donné par Jean-Charles Gilbert (INRIA - Paris). Il a présenté l'utilisation de l'algorithme du lagrangien augmenté pour traiter un problème d'optimisation quadratique convexe et non réalisable (contraintes incompatibles) ou non borné. Après avoir analysé le comportement de l'algorithme pour résoudre cette classe de problèmes, il a montré que, lorsque le problème quadratique n'est pas réalisable, l'algorithme du Lagrangien augmenté trouve la solution du problème réalisable le plus "proche" (dans un certain sens), avec une convergence linéaire globale vers une telle solution. Il a également donné des résultats numériques permettant de comparer l'efficacité de l'approche par rapport à d'autres codes d'activation de contraintes et de points intérieurs. Le deuxième exposé donné par Wim Van Ackooij (EDF) a présenté les modifications à apporter à la méthode de plans coupants pour optimiser une fonction convexe et non-différentiable, dans un espace combinatoire qui correspond à la base de la méthode de décomposition de Benders. Il a également présenté une analyse de la convergence de cette méthode sous des hypothèses faibles ainsi que des ré- sultats expérimentaux sur des problèmes quadratiques. Le troisième exposé a été donné par Emiliano Traversi (LIPN - Université Paris 13), où il a présenté une étude sur le comportement de l'algorithme de Dantzing-Wolfe appliqué aux problèmes quadratiques en variables binaires. Pour cela, il a présenté plusieurs décompositions qu'il a comparées d'un point de vue théorique et expérimental, notamment sur le problème du sac à dos quadratique avec une contrainte de cardinalité. Enfin, le dernier exposé de la journée a été donné par Sylvain Mouret (Artelys) où il a d'abord présenté la modélisation d'un problème de portefeuille d'actions par un programme quadradratique. Il a ensuite présenté les ré- sultats obtenus en résolvant ce modèle avec le solveur nonlinéaire Knitro.

Les transparents des exposés de cette journée sont en ligne sur le site des JFRO : http://jfro.roadef.org/