Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$24,000.00
Programmation mathématique locale - Local mathematical programming
EF 2015-16
Résumé
Dans les dix dernières années, j'ai développé de nouvelles méthodes très efficaces profitant de la dégénérescence en programmation linéaire pour réduire significativement et dynamiquement la taille des problèmes dégénérés, la dégénérescence elle-même et ultimement le temps de calcul. J'ai introduit ainsi un nouveau concept de décomposition intrinsèque: optimiser d'abord (efficacement) dans le sous-espace vectoriel (réduit) des variables de base non-dégénérées, chercher ensuite une direction de descente dans le sous-espace complémentaire et réitérer jusqu'à l'optimalité. De nouveaux algorithmes de haute performance utilisant cette décomposition ont permis de réduire le temps de calcul par des facteurs impressionnants, dépassant 20 pour des problèmes linéaires dégénérés par rapport à CPLEX, le logiciel dominant sur le marché.
Mon objectif de recherche principal est le développement des fondements théoriques et algorithmiques très solides d'une nouvelle filière méthodologique 'Local Mathematical Programming' pour la résolution efficace des problèmes (linéaires dégénérés, convexes non lisses, binaires) difficiles de très grande taille. Résoudre des problèmes de partitionnement (binaires) d'une vingtaine de milliers de contraintes et de plusieurs dizaines de millions de variables en moins d'une heure est un exemple de défi à relever par cette recherche. Pour ce faire, cinq nouvelles méthodes exactes dites locales seront élaborées afin de trouver très efficacement et en parallèle des directions de descente de haute qualité permettant de converger très rapidement vers l'optimum.
La spécialisation de ces algorithmes pour des problèmes de tournées de véhicules/horaires du personnel/clustering devrait permettre de développer une nouvelle génération de logiciels permettant des gains de productivité significatifs par rapport aux logiciels existants et ainsi contribuera à propulser la compétitivité des compagnies canadiennes qui commercialisent ces logiciels sur le marché mondial.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
436118-2013
Name nom
ElHallaoui, Issmail
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2013
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
3
Nb partie
5
Application title
Programmation mathématique locale - Local mathematical programming
Keyword
NSERC
Application summary
Dans les dix dernières années, j'ai développé de nouvelles méthodes très efficaces profitant de la dégénérescence en programmation linéaire pour réduire significativement et dynamiquement la taille des problèmes dégénérés, la dégénérescence elle-même et ultimement le temps de calcul. J'ai introduit ainsi un nouveau concept de décomposition intrinsèque: optimiser d'abord (efficacement) dans le sous-espace vectoriel (réduit) des variables de base non-dégénérées, chercher ensuite une direction de descente dans le sous-espace complémentaire et réitérer jusqu'à l'optimalité. De nouveaux algorithmes de haute performance utilisant cette décomposition ont permis de réduire le temps de calcul par des facteurs impressionnants, dépassant 20 pour des problèmes linéaires dégénérés par rapport à CPLEX, le logiciel dominant sur le marché.
Mon objectif de recherche principal est le développement des fondements théoriques et algorithmiques très solides d'une nouvelle filière méthodologique 'Local Mathematical Programming' pour la résolution efficace des problèmes (linéaires dégénérés, convexes non lisses, binaires) difficiles de très grande taille. Résoudre des problèmes de partitionnement (binaires) d'une vingtaine de milliers de contraintes et de plusieurs dizaines de millions de variables en moins d'une heure est un exemple de défi à relever par cette recherche. Pour ce faire, cinq nouvelles méthodes exactes dites locales seront élaborées afin de trouver très efficacement et en parallèle des directions de descente de haute qualité permettant de converger très rapidement vers l'optimum.
La spécialisation de ces algorithmes pour des problèmes de tournées de véhicules/horaires du personnel/clustering devrait permettre de développer une nouvelle génération de logiciels permettant des gains de productivité significatifs par rapport aux logiciels existants et ainsi contribuera à propulser la compétitivité des compagnies canadiennes qui commercialisent ces logiciels sur le marché mondial.