Discrete Optimization and Constraint Satisfaction

Themes :
  • Integer linear programming
  • Multiobjective optimization
  • Combinatorial optimization
  • Constraint satisfaction Problems (CSP)
  • (max,+) Algebra for discrete event systems
  • Tree and Local search
  • Hybrid methods
  • Metaheuristics
  

The YIELDS Method

Beyond more applicative fields, we also propose mathematical models for dynamic discrete-event systems and generic solving methods for discrete optimization and constraint satisfaction problems (CSP).

More particularly for CSPs, we concentrate on tree search procedures associated with learning techniques, and/or large neighborhood search. New tree search procedures based on discrepancy search are proposed, as well as some learning on impact of decision-making during search. We are also interested in hybrid methods integrating ILP and constraint programming.

Concerning the modeling and control of discrete event systems, the (max,+) theory is also a relevant tool that we contribute to study. The group studies some original control methods for this class of system.

We are also intersted in multiobjective optimization via branch and cut and metaheuristic techniques.

Contacts : Christian Artigues, Cyril Briand, Patrick Esquirol, Laurent Houssin, Marie-José Huguet, Nicolas Jozefowiez, Pierre Lopez

PhD student : Bernat Gacias , Wafa Karoui

Selected publications (see complete list on LAAS server) :

  • 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

  • N. JOZEFOWIEZ, F. GLOVER, M. LAGUNA, Multi-objective meta-heuristics for the traveling salesman problem with profits, Journal of Mathematical Modelling an Algorithms, 7, 2008.

  • 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