Présentation sur YouTube.

La dernière décénie a vu l'arrivée des méthodes d'optimisations assistés par l'apprentissage machine. Ces approches consistent en l'utilisation de modèles d'apprentissage machine pour orienter, voire remplacer complètement, les algorithmes d'optimisation traditionnels. Bien que l'optimisation assistée par l'apprentissage machine ait connu de nombreux succès, il n'existe toujours pas de directives claires sur les meilleures pratiques à adopter.

Dans cette présentation, je propose deux méthodes visant à accélérer les algorithmes de branch-and-price grâce à l'apprentissage machine. Tout d'abord, j'introduis une stratégie d'énumération partielle (partial pricing) pour résoudre le problème de création d'horaires d'équipage aérien. Plus précisément, nous entraînons un modèle d'apprentissage machine à prédire les rotations (ensembles de vols constituant un ou plusieurs jours de travail) les plus susceptibles d'être incluses dans l'horaire de chaque membre d'équipage. Seules les rotations les plus probables sont prises en compte lors de la résolution des sous-problèmes de chaque membre d'équipage, ce qui permet de réduire considérablement le temps de calcul. Cette stratégie permet d'obtenir des temps de résolution cinq fois plus rapides, sans compromettre la qualité des solutions.

Ensuite, je présente une stratégie de branchement heuristique basée sur l'apprentissage machine pour résoudre le problème des rotations d'équipage aérien (crew pairing problem, CPP). Les deux méthodes de branchement heuristiques les plus couramment utilisées pour résoudre le CPP sont l'heuristique de branchement en profondeur (diving heuristic, DH) et l'heuristique de branchement fort (heuristic strong branching, HSB). Bien que DH soit beaucoup plus rapide que HSB, il est établi que HSB permet d'obtenir de meilleures solutions. Notre méthode de branchement (IAFIX) tente d'imiter le branchement fort en utilisant un modèle d'apprentissage machine pour prédire l'impact de la fixation d'une variable sur la valeur de la relaxation linéaire du problème. Nos résultats démontrent que IAFIX est aussi rapide que DH, tout en permettant d'obtenir des solutions comparables à celles obtenues avec HSB.