Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$43,000.00
Optimisation primale en nombres entiers - Primal integer optimization
EF 2023-24
Résumé
Mon objectif de recherche ultime est de résoudre efficacement et d'une façon exacte (optimale) des problèmes en nombres entiers de très grande taille par des méthodes primales, i.e, des méthodes permettant de passer d'une solution entière à une meilleure jusqu'à ce que l'optimalité soit prouvée. La présente demande entend propulser les développements théoriques et algorithmiques de cette filière méthodologique batisée `Primal Integer Optimization` (PIO). Ce genre de méthodes primales a l'avatange de générer en pratique plusieurs solutions de qualité au cours de la résolution au lieu d'une seule solution à la fin comme c'est souvent le cas des méthodes "duales" de type Branch tre vu comme un pas de l'avant considérable vers la réalisation du but ultime.De point de vue théorique, j'étudierais les propriétés polyhédriques permettant d'avoir des algorithmes primaux efficaces (avec une bonne complexité en pratique), notamment la quasi-intégralité. Cette propriété, nécessaire pour aller d'une solution entière à une autre adjacente améliorée, est présente dans les problèmes de partitionnement mais on la perd dans les problèmes binaires quelconques. Comment restituer cette propriété, même localement (moyennant des changements polyhédriques, quitte à augmenter la dimension du problème par l'ajout, par exemple, des variables agrégées appropriées) sera une question à étudier. J'étudierais aussi la caractérisation des solutions fractionnaires afin de les pénaliser en utilisant des normalisations qui pondèrent négativement les directions de descente vers celles-ci.On les évitera ainsi d'une façon préventive, i.e., sans branchement et sans coupes! Ces développements théoriques seront réétudiés dans d'autres contextes d'intérêt comme la génération de colonnes ou la ré-optimisation en temps réel (après perturbation) selon un ou plusieurs critères.De point de vue pratique, cette demande introduit un framework unifié où on peut utiliser, à chaque itération, des méthodes exactes ou heuristiques pour trouver en parallèle des directions de descente menant à des solutions entières améliorées. Ces méthodes seront combinées avec un "partial pricing" intelligent favorisant l'intégralité afin de converger plus rapidement. Résoudre optimalement ou presque des problèmes binaires complexes (en transport, mines et énergie) de plusieurs dizaines de milliers de contraintes et de millions de variables binaires dans des temps raisonnables (pour l'industrie) est un défi à relever. Un nouvel optimiseur PIO sera développé et mis à disposition de la communauté scientifique et l'industrie. C'est un jeune paradigme très prometteur en besoin de vitesse!
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
RGPIN-2018-05284
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
2023
Competition year année de concours
2018
Award amount
43000
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
2713
Research subject group en
Information technology
Research subject group fr
Algorithms
Research subject en
Technologie de l'information
Research subject fr
Algorithmes
Application title
Optimisation primale en nombres entiers - Primal integer optimization
Keyword
Calcul parallèle; Génération de colonnes; Horaires du personnel; Méthodes de décomposition; Programmation en nombres entiers (binaire); Programmation mathématique; Simplexe en nombres entiers; Transport aérien
Application summary
Mon objectif de recherche ultime est de résoudre efficacement et d'une façon exacte (optimale) des problèmes en nombres entiers de très grande taille par des méthodes primales, i.e, des méthodes permettant de passer d'une solution entière à une meilleure jusqu'à ce que l'optimalité soit prouvée. La présente demande entend propulser les développements théoriques et algorithmiques de cette filière méthodologique batisée `Primal Integer Optimization` (PIO). Ce genre de méthodes primales a l'avatange de générer en pratique plusieurs solutions de qualité au cours de la résolution au lieu d'une seule solution à la fin comme c'est souvent le cas des méthodes "duales" de type Branch tre vu comme un pas de l'avant considérable vers la réalisation du but ultime.De point de vue théorique, j'étudierais les propriétés polyhédriques permettant d'avoir des algorithmes primaux efficaces (avec une bonne complexité en pratique), notamment la quasi-intégralité. Cette propriété, nécessaire pour aller d'une solution entière à une autre adjacente améliorée, est présente dans les problèmes de partitionnement mais on la perd dans les problèmes binaires quelconques. Comment restituer cette propriété, même localement (moyennant des changements polyhédriques, quitte à augmenter la dimension du problème par l'ajout, par exemple, des variables agrégées appropriées) sera une question à étudier. J'étudierais aussi la caractérisation des solutions fractionnaires afin de les pénaliser en utilisant des normalisations qui pondèrent négativement les directions de descente vers celles-ci.On les évitera ainsi d'une façon préventive, i.e., sans branchement et sans coupes! Ces développements théoriques seront réétudiés dans d'autres contextes d'intérêt comme la génération de colonnes ou la ré-optimisation en temps réel (après perturbation) selon un ou plusieurs critères.De point de vue pratique, cette demande introduit un framework unifié où on peut utiliser, à chaque itération, des méthodes exactes ou heuristiques pour trouver en parallèle des directions de descente menant à des solutions entières améliorées. Ces méthodes seront combinées avec un "partial pricing" intelligent favorisant l'intégralité afin de converger plus rapidement. Résoudre optimalement ou presque des problèmes binaires complexes (en transport, mines et énergie) de plusieurs dizaines de milliers de contraintes et de millions de variables binaires dans des temps raisonnables (pour l'industrie) est un défi à relever. Un nouvel optimiseur PIO sera développé et mis à disposition de la communauté scientifique et l'industrie. C'est un jeune paradigme très prometteur en besoin de vitesse!