Thèmes : programmation linéaire en nombres entiers optimisation multi-objectif optimisation combinatoire problèmes de satisfaction de contraintes (CSP) algèbre (max,+) pour les systèmes à événements discrets recherche arborescente méthodes hybrides métaheuristiques

La méthode YIELDS

Au-delà des domaines plus applicatifs, nous proposons des modèles mathématiques pour les systèmes dynamiques à événements discrets et des méthodes génériques de résolution de problèmes d’optimisation discrète et de satisfaction de contraintes (CSP).

Pour la résolution de CSP, un accent particulier est mis sur les méthodes de recherche arborescente associées à des techniques d’apprentissage et/ou des méthodes de recherche locale à voisinages étendus. De nouvelles procédures de résolution arborescentes basées sur la notion de divergence (écart d’instanciation par rapport à celles d’une heuristique de référence) sont proposées (voir figure).

Nous avons également proposé des techniques basées sur l’apprentissage des impacts des décisions au cours de la recherche pour l'optimisation discrète. Nous nous intéressons également aux méthodes intégrant programmation linéaire en nombres entiers  et programmation par contraintes, notamment au sein de méthodes de décomposition de type "génération de colonnes". 

Pour la modélisation et l’étude des systèmes à événements discrets, la théorie des systèmes (max,+) constitue également un outil que nous contribuons à développer. Des méthodes originales de commande de tels systèmes sont étudiées au sein de notre groupe.

Enfin, le groupe s'intéresse à la programmation mathématique multi-objectif via notamment des méthodes de séparation et coupes et des métaheuristiques.

Contacts : Christian Artigues, Patrick Esquirol, Emmanuel Hebrard, Laurent Houssin, Nicolas Jozefowiez, Pierre Lopez

Post-docs : Clément Pira, Gilles Simonin

Thèses en cours : Yacine Gaoua, Kata Kiatmanaroj, Boadu Mensah Sarpong, Mohamed Siala, Panwadee Tangpattanakul

Quelques publications :  (voir la liste complète sur le serveur du LAAS) :

• C.ARTIGUES, M.GENDREAU, L.M.ROUSSEAU, A.VERGNAUD, Solving an integrated employee timetabling and production scheduling problem via hybrid branch-and-bound, Computers and Operations Resaearch, to appear.
  
• B.BONTOUX, D.FEILLET, C.ARTIGUES, E.BOURREAU, Dynamic cooperative search for constraint satisfaction and combinatorial optimization : application to a rostering problem, 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA'2007), Paris (France), Août 2007, pp.557-560
  
• B.GACIAS, C.ARTIGUES, P.LOPEZ, Recherches arborescente et locale pour les problèmes d'ordonnancement avec contraintes de précédence et temps de préparation, 9ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'08), Clermont-Ferrand (France), 25-27 Février 2008, pp.45-62
  
• W.KAROUI, M.J.HUGUET, P.LOPEZ, W.NAANAA, YIELDS: A yet improved limited discrepancy search for CSPs, 4th International Conference, CPAIOR 2007, Bruxelles (Belgique), 23 Mai 2007, pp.99-111