Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

École Polytechnique de Montréal

$59,000.00

Primalisation pour l'optimisation grande taille

EF 2024-25

Résumé
Les méthodes comme la Décomposition de Benders, Branch & Cut et Génération de colonnes (Branch & Price) sont très utilisées en recherche opérationnelle pour résoudre une panoplie de problèmes d'optimisation allant des chaînes logistiques, aux horaires de personnel, etc. Elles sont très efficaces pour résoudre les problèmes en nombres entiers de taille/densité/gap petits ou moyens. Cependant, la résolution devient pénible quand le problème d'optimisation est de grande taille : le temps pour trouver une solution entière primale satisfaisante souvent non acceptable, besoin du développement spécifique, e.g. décomposition spécifique, branchement spécifique, développement des heuristiques primales spécifiques, etc. Ceci peut se traduire par des mois voire des années de développement à chaque fois qu'on a un problème de telle taille. Ces limitations peuvent être attribuées au fait que ces méthodes sont « duales », car on y améliore essentiellement une borne inférieure (pour un problème de minimisation) jusqu'à ce qu'elle soit proche ou égale à une borne supérieure, i.e., une solution entière primale.  L'objectif à long terme de ce programme de recherche est de développer un mécanisme de décomposition de tels problèmes en sous-problèmes plus petits qu'on peut résoudre rapidement avec les mêmes méthodes duales et où on a, pourtant, une solution entière primale, améliorée à chaque itération et ce jusqu'à l'optimalité. Ce mécanisme est en quelque sorte une primalisation de ces méthodes qui sont duales à la base. Le but ultime est de résoudre plus efficacement et bien évidemment, réduire le recours au développement spécifique pour l'optimisation grande taille.  La recherche proposée est une amélioration majeure, de mes anciens travaux sur la programmation primale en nombres entiers, où à partir d'une solution entière initiale, on trouve une séquence de solutions entières de coût décroissant jusqu'à l'optimalité en décomposant le problème original en sous-problèmes de taille plus petite. De plus, ces sous-problèmes garderont la même structure du problème original et donc solvables par la méthode appropriée (Benders par exemple). En pratique, il est généralement possible de construire, à l'aide de ML par exemple, une solution entière initiale proche (de point de vue primale) de la solution finale : la séquence recherchée devra être courte. Mieux encore, on détient en tout temps une solution entière primale, au cas où on fait un arrêt heuristique, ce qui est très fréquent en optimisation grande taille. Le mécanisme de primalisation proposé est générique et donc applicable à une variété très large de problèmes rencontrés en pratique. Les PHQs formés par ce programme de recherche maîtriseront ainsi des méthodes avant-gardistes très utiles en pratique. Ceci est bien pour l'avancement de la science et aidera nos partenaires industriels Canadiens à améliorer leurs technologies et donc leur compétitivité sur la scène internationale.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-06137
Name nom
El Hallaoui, Issmail
Department département
Mathématique 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
2024
Competition year année de concours
2024
Award amount
59000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Primalisation pour l'optimisation grande taille
Keywords
programmation en nombres entiers; programmation mathématique; optimisation grande taille; optimisation temps réel; méthodes de décomposition; transport et logistique; horaires du personnel; logiciels d'optimisation
Application summary
Les méthodes comme la Décomposition de Benders, Branch & Cut et Génération de colonnes (Branch & Price) sont très utilisées en recherche opérationnelle pour résoudre une panoplie de problèmes d'optimisation allant des chaînes logistiques, aux horaires de personnel, etc. Elles sont très efficaces pour résoudre les problèmes en nombres entiers de taille/densité/gap petits ou moyens. Cependant, la résolution devient pénible quand le problème d'optimisation est de grande taille : le temps pour trouver une solution entière primale satisfaisante souvent non acceptable, besoin du développement spécifique, e.g. décomposition spécifique, branchement spécifique, développement des heuristiques primales spécifiques, etc. Ceci peut se traduire par des mois voire des années de développement à chaque fois qu'on a un problème de telle taille. Ces limitations peuvent être attribuées au fait que ces méthodes sont « duales », car on y améliore essentiellement une borne inférieure (pour un problème de minimisation) jusqu'à ce qu'elle soit proche ou égale à une borne supérieure, i.e., une solution entière primale.  L'objectif à long terme de ce programme de recherche est de développer un mécanisme de décomposition de tels problèmes en sous-problèmes plus petits qu'on peut résoudre rapidement avec les mêmes méthodes duales et où on a, pourtant, une solution entière primale, améliorée à chaque itération et ce jusqu'à l'optimalité. Ce mécanisme est en quelque sorte une primalisation de ces méthodes qui sont duales à la base. Le but ultime est de résoudre plus efficacement et bien évidemment, réduire le recours au développement spécifique pour l'optimisation grande taille.  La recherche proposée est une amélioration majeure, de mes anciens travaux sur la programmation primale en nombres entiers, où à partir d'une solution entière initiale, on trouve une séquence de solutions entières de coût décroissant jusqu'à l'optimalité en décomposant le problème original en sous-problèmes de taille plus petite. De plus, ces sous-problèmes garderont la même structure du problème original et donc solvables par la méthode appropriée (Benders par exemple). En pratique, il est généralement possible de construire, à l'aide de ML par exemple, une solution entière initiale proche (de point de vue primale) de la solution finale : la séquence recherchée devra être courte. Mieux encore, on détient en tout temps une solution entière primale, au cas où on fait un arrêt heuristique, ce qui est très fréquent en optimisation grande taille. Le mécanisme de primalisation proposé est générique et donc applicable à une variété très large de problèmes rencontrés en pratique. Les PHQs formés par ce programme de recherche maîtriseront ainsi des méthodes avant-gardistes très utiles en pratique. Ceci est bien pour l'avancement de la science et aidera nos partenaires industriels Canadiens à améliorer leurs technologies et donc leur compétitivité sur la scène internationale.