Presentation on YouTube.

The last decade has seen the arrival of machine learning-assisted optimization methods. These approaches involve the use of machine learning models to guide, or even completely replace, traditional optimization algorithms. Although machine learning-assisted optimization has enjoyed many successes, there are still no clear guidelines on best practice.

In this presentation, I propose two methods for accelerating branch-and-price algorithms using machine learning. First, I introduce a partial pricing strategy to solve the aircrew scheduling problem. Specifically, we train a machine learning model to predict the pairings (sets of flights constituting one or more working days) most likely to be included in each crew member's schedule. Only the most likely pairings are taken into account when solving each crew member's sub-problems, thus considerably reducing computation time. This strategy achieves five times faster solution times, without compromising solution quality.

Next, I present a machine learning-based heuristic branching strategy for solving the crew pairing problem (CPP). The two most commonly used heuristic branching methods for solving the CPP are the diving heuristic (DH) and the strong branching heuristic (HSB). Although DH is much faster than HSB, HSB has been shown to yield better solutions. Our branching method (IAFIX) attempts to imitate strong branching by using a machine learning model to predict the impact of fixing a variable on the value of the linear relaxation of the problem. Our results show that IAFIX is as fast as DH, while obtaining solutions comparable to those obtained with HSB.