Accélération de l'algorithme du simplexe pour les problèmes dégénérés

 

François Soumis

École Polytechnique de Montréal

 

Domaine : structures abstraites

Programme projet de recherche en équipe

Concours 2012-2013

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ées par cet algorithme.

Nous avons développé récemment une méthode qui réduit le nombre de contraintes des problèmes de partitionnement d'ensemble et l'avons intégrée à la génération de colonnes. Elle permet de réduire par un facteur 100 les temps de résolution des grands problèmes. Nous avons aussi développé une généralisation réduisant l'ensemble des contraintes linéaires qui diminue les temps de calcul par un facteur allant jusqu'à 20 pour certains problèmes dégénérés. Toutefois cette généralisation n'a pas été intégrée avec la génération de colonnes.

Les objectifs de ce projet sont :

  • Développer des méthodes de réduction pour traiter très efficacement différents types de contraintes populaires qui donnent lieu à de la dégénérescence : contraintes de conservation de flot et de multi-flot, contraintes de bornes supérieures, contraintes de recouvrement généralisé.
  • Combiner ces méthodes pour traiter efficacement des problèmes avec plusieurs types de contraintes. Chaque type de contraintes est réduit avec la méthode appropriée et les interactions sont traitées efficacement. 
  • Intégrer toutes ces méthodes avec la génération de colonnes et utiliser des processeurs parallèles pour traiter les très grands problèmes.
  • Adapter et évaluer le nouvel algorithme sur les grands problèmes d'horaires d'équipages aériens, de chauffeurs d'autobus et de quarts de travail.