Nouvelle filière méthodologique pour la résolution optimale des problèmes de partitionnement de très grande taille

 

Issmail Elhallaoui

École Polytechnique de Montréal

 

Domaine : structures abstraites

Programme projet de recherche en équipe

Concours 2014-2015

Notre objectif principal est de développer une nouvelle filière méthodologique autour d'ISUD, une approche de résolution primale exacte pour le problème de partitionnement d'ensemble, beaucoup plus efficace que l'approche classique. ISUD trouve rapidement une séquence de solutions entières de coûts décroissants menant à l'optimalité, contrairement à l'approche classique "duale" résolvant la relaxation linéaire et utilisant le branch&cut.

L'objectif de ce projet est d'effectuer les développements théoriques et algorithmiques, pour améliorer la nouvelle filière méthodologique, permettant de résoudre très efficacement des problèmes de partitionnement de très grande taille (ex. avec une vingtaine de milliers de contraintes et plusieurs dizaines de millions de variables). Trois améliorations très importantes seront développées: 1) Caractérisation et pénalisation des directions de descente menant à des solutions fractionnaires. 2) Décompositions mathématiques permettant de trouver en parallèle des directions de descente. 3) Génération de colonnes en nombres entiers. Chacune des trois améliorations constitue un sous-objectif de recherche.

Un nouveau solveur générique intégrant les nouvelles percées scientifiques sera développé afin de résoudre efficacement des problèmes complexes de grande envergure notamment en classification et en transport. Le nouveau solveur sera mis à la disposition des membres du GERAD et CIRRELT et à leurs collaborateurs.