Programmation mathématique locale - Local mathematical programming

点击翻译按钮获取中文摘要

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.