Apprentissage machine et génération de colonnes

Polytechnique Montreal 2022-12

Theses de doctorat (Ecole Polytechnique (Montreal, Quebec))
PolyPublie

RÉSUMÉ: Au cours des dernières années, l’apprentissage machine (ML - Machine Learning) a connu un développement sans précédent, surtout après l’émergence de l’apprentissage profond. Le domaine a connu des avancées remarquables qui ont suscité beaucoup d’intérêt auprès des chercheurs de plusieurs disciplines, incluant la communauté de recherche opérationnelle. Récemment, plusieurs travaux cherchant à exploiter les méthodes ML pour résoudre des problèmes d’optimisation combinatoire, ou bien pour accélérer le processus de résolution, ont vu le jour. Ceci a mené au développement de nombreuses méthodes qui ont montré un grand potentiel sur différents problèmes d’optimisation. Dans cette thèse, nous nous intéressons particulièrement à la méthode de génération de colonnes (GC), qui est une méthode d’optimisation utilisée pour résoudre efficacement des programmes linéaires comportant un grand nombre de variables (colonnes). Il s’agit d’une méthode itérative qui commence avec un petit sous-ensemble de variables du programme linéaire original, et génère de nouvelles colonnes au besoin jusqu’à atteindre une solution optimale. La méthode a prouvé son efficacité sur plusieurs problèmes industriels, tels que des problèmes de planification, d’ordonnancement, et de transport. Nous présentons dans cette thèse trois approches différentes pour intégrer l’apprentissage machine dans le contexte de la GC, soit pour accélérer l’optimisation et réduire les temps de calcul des méthodes exactes, ou bien pour développer des heuristiques qui produisent de bonnes solutions en des temps raisonnables. L’objectif général est de tirer profit des données qui sont collectées lors des exécutions antérieures afin d’obtenir des modèles de prédiction, qui seront capables de guider l’optimisation et de réduire l’espace de recherche. Dans le premier sujet, nous proposons une méthode de sélection de colonnes qui, à chaque itération de la GC, applique un modèle de prédiction pour sélectionner un sous-ensembl

Theses de doctorat; Mémoire ou thèse; NonPeerReviewed

Open access content. Open access content
copyright

text
French

GA0 oai:publications.polymtl.ca:10709
Morabit, M. (2022). Apprentissage machine et génération de colonnes [Thèse de doctorat, Polytechnique Montréal].
1430226847

ECOLE POLYTECHNIQUE DE MONTREAL
From OAIster®, provided by the OCLC Cooperative.

edsoai.on1430226847