As a leading consulting firm with a strong reputation across the transportation and aviation sector, M2P Consulting knows that efficient scheduling and resource allocation are critical to operational success. They also know that in these sectors, the ability to solve problems quickly is essential.
With Orbit, M2P’s Tail Optimizer/Disruption Solver, they can help airlines make sound decisions for their operations within minutes—effectively reducing costs, passenger impact, and CO₂ emissions.
But as scheduling problems grow in size and complexity, solve times can often slow down. To get the performance boosts they needed, M2P Consulting turned to Gurobi and their PDHG algorithm implementation for even more solving power.
The problem
Airline scheduling and tail assignment are notoriously complex problems, involving the coordination of aircraft, crews, potential passenger bookings, and numerous operational constraints and variables while striving to minimize costs and maximize service quality.
For M2P Consulting’s client, the challenge is optimizing tail assignments (how specific aircraft are assigned to flights) in a way that minimizes crew changes between flights to support reduced delay propagation.
“Depending on the duration of the flights, flight attendants can actually manage to operate on four flights in one day,” explains Dr. Dennis Adelhütte, Lead Consultant at M2P Consulting.
“You want the crew to stay on the same airplane—because if one of the flights is delayed and the crew must change aircraft for the next one, another flight could be delayed. And if there is no reserved crew member available, the delay branches and propagates, so that’s why they try to avoid that at all costs.”
The airline required a solution that could deliver high-quality schedules for a 48-hour planning horizon within tight computational timeframes, as even minor delays or suboptimal decisions could have significant business impacts.
The solution
To address these challenges, M2P Consulting explored Gurobi’s Primal-Dual Hybrid Gradient (PDHG) algorithm as an option to enable larger planning horizons and shorter solve times. The PDHG algorithm is well-suited for large-scale linear programs (LPs) or mixed-integer programs (MIPs), where solving the linear relaxation at the root node is particularly challenging. Running PDHG on a graphics processing unit (GPU) could unlock additional speedups; however, the main advantage still comes from the algorithm itself.
After hearing about Gurobi’s new PDHG implementation at the Decision Intelligence Summit in Vienna, the M2P Consulting team decided to open a support ticket to test the algorithm on their models in collaboration with the Gurobi Experts team.
M2P’s models have a special property: the solution of the root node relaxation is naturally close to the optimal integer solution, so even though the models are MIPs, there is little time spent in the branch-and-cut algorithms. Therefore, the PDHG algorithm for LPs can significantly impact the overall solve time by speeding up the root relaxation. By carefully integrating PDHG and adopting new hardware, M2P Consulting can tailor their solution to the airline’s specific scheduling requirements.
The collaborative relationship between M2P Consulting and Gurobi’s support team played a vital role in identifying this previously untapped potential. Gurobi’s thorough and responsive support facilitated the fine-tuning that M2P Consulting needed to help their client succeed.
“The support we’ve gotten from Gurobi has been really great. Whenever we needed something, we got fast, reliable answers,” explains Dr. Adelhütte.
Results
After testing Gurobi’s PDHG algorithm on a CPU, in conjunction with Gurobi’s robust MIP capabilities, M2P Consulting was able to achieve a 14x speedup for their airline client on regular instances and solve large instances that previously took 1.5 hours in just under 10 minutes (a 9x speedup). Using the GPU-enabled version of the PDHG algorithm on NVIDIA Grace-Hopper hardware delivers an additional three-fold speedup when solving the root relaxation, resulting in an overall 15% MIP runtime reduction compared to a 64-core high-performance CPU.
"We had tried the No-Relaxation (‘NoRel’) heuristic, warm-starting, and other classical strategies, but none of them moved the needle. So the PDHG algorithm has definitely been a big game-changer for us."
Dr. Julius Bauß, Senior Consultant at M2P Consulting
The M2P team had also developed heuristics to solve the tail assignment problem with crew scheduling, and while that approach was able to find feasible solutions, they were usually sub-optimal. The new approach delivered high-quality schedules quickly, reducing the average number of crew changes in the testing scenarios by 9%. There has also been a positive impact on fuel cost savings compared to the sub-optimal heuristic solutions.
“In our experience, Gurobi is not just doing the optimization. The team actually understands the business model behind it, and what you want from it,” said Dr. Adelhütte. “So for anyone considering Gurobi, I would say go for it.”
