Journées de l'optimisation 2019

HEC Montréal, 13-15 mai 2019

JOPT2019

HEC Montréal, 13 — 15 mai 2019

Horaire Auteurs Mon horaire

MB10 Coupling Operations Research and Machine Learning I - Columm Generation

13 mai 2019 10h30 – 12h10

Salle: TD Assurance Meloche Monnex

Présidée par Guy Desaulniers

4 présentations

  • 10h30 - 10h55

    Accelerating the optimization of aircrew rostering with machine learning

    • Alice Wu, prés.,

    A classical approach to optimize the crews’ rosterings is column generation. With the pairings as input, the optimizer solves for each employee a shortest path problem in a graph with all the possible pairings to generate rosters. The purpose of this project is to predict with machine learning the probability of a pairing being in an employee’s monthly block. We aim to solve this in sequential phases, with the most probable pairings first, and then gradually adding the rest of the pairings. This is how we can significantly reduce the size of the graphs and therefore the computational time.

  • 10h55 - 11h20

    Evolution strategies for the crew rostering problem

    • Philippe Racette, prés., Polytechnique Montréal

    The crew rostering problem is solved using dynamic constraint aggregation (DCA), but schedules must sometimes be rearranged at greater speed than available. This talk explores how artificial intelligence can guide the DCA algorithm with a focus on evolution strategies and neural networks. Preliminary results are presented and next steps discussed.

    Keywords: evolution strategies, crew rostering, neural networks

  • 11h20 - 11h45

    Machine learning in airline crew pairing to construct initial clusters for dynamic constraint aggregation

    • Yassine Yaakoubi, prés., Gerad
    • Francois Soumis, GERAD et Polytechnique
    • Simon Lacoste-Julien, MILA, Université de Montréal

    In this talk, we introduce a new paradigm for solving the crew pairing problem, modeled as a set partitioning problem: "Start with Machine Learning – Finish with Mathematical Programming." Machine Learning produces predictions on some parts of the solution of the new instance based on solutions of similar instances. This information feeds the Column Generation optimizer to finish the work taking account of the exact cost function and the complex constraints. This approach reduces the solution time significantly without losing on the quality of the solution.

  • 11h45 - 12h10

    Accelerating column generation using machine learning

    • Mouad Morabit, prés., Polytechnique Montréal
    • Guy Desaulniers, GERAD - Polytechnique Montréal
    • Andrea Lodi, Polytechnique Montreal

    Column generation (CG) is a well-known method for solving large-scale linear problems. In this presentation, we propose to integrate a machine learning technique in the context of CG to reduce computation time. More precisely, a classification algorithm is proposed to select promising columns at each CG iteration when solving a problem that is subject to degeneracy in the master problem. An application to the vehicle and crew scheduling problem in urban transport will be presented

Retour