Groupe d’études et de recherche en analyse des décisions

Méthodes d’optimisation pour les grands problèmes de programmation en nombres entiers

François Soumis Professeur titulaire, Département de mathématiques et de génie industriel, Polytechnique Montréal, Canada

Plusieurs problèmes d’horaires se formulent comme des problèmes de recouvrement de tâches où chaque colonne comprend un ensemble de tâches pouvant être couvert par une personne ou un véhicule. Dans les grands réseaux de transport ces problèmes comprennent des milliers de contraintes et des millions de millions de variables. Certains problèmes comprennent aussi plusieurs autres contraintes linéaires : flots, multiflots, bornes sur les ressources utilisées, … Une première idée popularisée par notre équipe est de réduire le nombre de variables avec la méthode de génération de colonnes. Les variables sont générées dynamiquement par des sous-problèmes de plus court chemin avec contraintes. Une seconde idée que nous avons proposée récemment réduit le nombre de contraintes de recouvrement en agrégeant les tâches effectuées par une même personne ou un même véhicule dans la solution courante. L’agrégation est modifiée dynamiquement pour permettre d’atteindre la solution optimale. La réduction du nombre de contraintes a aussi été généralisée pour les autres contraintes linéaires. Plusieurs idées ont été développées pour obtenir rapidement de bonnes solutions entières : fixation de variables, coupes dans le problème maitre et les sous problèmes, branchement sur plusieurs variables à la fois, branchement mou, … Des résultats sur de grands problèmes de transport par avion, train et autobus seront présentés et un aperçu des recherches en cour sera donné.