Grant: Collaborative Research and Development Grants

L'algorithme du Simplexe est depuis plus de 50 ans l'outil le plus utilisé pour traiter les problèmes de programmation linéaire. Notre équipe a popularisé la méthode de génération de colonnes pour réduire le nombre de variables traités par le Simplexe. Ce projet réduit le nombre de contraintes en agrégeant les contraintes dépendantes après avoir éliminé les variables nulles de la base. La méthode proposée permet d'atteindre la solution optimale en modifiant dynamiquement l'agrégation. L'agrégation réduit le temps par itération car la base est plus petite et réduit la proportion d'itérations dégénérées en supprimant des variables nulles de la base. La recherche proposée comprend le développement de stratégies plus sophistiquées de gestion de l'algorithme et sa généralisation aux contraintes de recouvrement généralisées, de conservation de flot et linéaires générales et aux problèmes en nombres entiers. Elle portera aussi sur la spécialisation de l'algorithme pour traiter de grands problèmes d'horaires de véhicules et de personnel. Les premiers résultats obtenus et le potentiel des améliorations proposées devraient permettre d'accélérer la résolution par un facteur de 25 par rapport aux méthodes actuelles. Ceci permettra de traiter des problèmes beaucoup plus grands : traiter des problèmes d'une semaine plutôt qu'une journée, traiter simultanément deux étapes de processus de planification qui sont actuellement traitées séquentiellement.