Objectifs de la formation

Traiter des problèmes d’optimisation combinatoire difficile à l’aide de la programmation par contraintes et de recherches locales.

Pour qui ?

Ingénieurs, scientifiques et développeurs intéressés par la modélisation de problèmes de décision et la mise en œuvre d’algorithmes d’optimisation.

Programmation par contraintes
• Programmation par contraintes : principes et utilisation.
• Présentation d’un solveur de programmation par contraintes : Xpress-Kalis.

Application de la programmation par contraintes
• Planification de personnel d’une salle de théâtre.
• Résolution d’un problème d’allocation de scènes de film.
• Résolution d’un problème d’affectation de fréquences.
• Paramétrage de l’énumération – Stratégies de branchement – Spécification de stratégies de recherche ad hoc par l’utilisateur.

Recherche locale
• Intuition (n-reines) – Voisinage (car-sequencing, carré magique) – Optimisation (warehouse location) – 2-opt, k-opt.
• Optimalité vs. Faisabilité (coloration de graphes) – Voisinages complexes (sport scheduling) – Échapper aux minima locaux, connectivité.
• Formalisation, heuristiques – Introduction aux métaheuristiques : recherche à voisinage variable (VNS), recuit simulé, recherche tabou.

Problèmes d’ordonnancement et de gestion de ressources
• Introduction aux problématiques d’ordonnancement.
• Ordonnancement disjonctif – application à la construction d’un stade.
• Ordonnancement disjonctif multi-machines – problème de job-shop.
• Ordonnancement cumulatif – ressources non renouvelables.