A Deep Learning Approach to Accelerate MILP Solvers with Application to the Aircraft Routing Problem

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Large-scale Aircraft Routing Problems (ARPs) remain challenging for standard Branch-and-Bound (B&B) and modern Mixed-Integer Linear Programming (MILP) solvers due to vast search spaces and instance-agnostic heuristics. Methods: We develop a learning-to-accelerate framework centered on a Two-Stage Route Selection Graph Convolutional Network (TRS-GCN) that predicts the importance of flight string variables using structural, LP relaxation, and operational features. Predictions are injected into the solver via three mechanisms: an ML-guided feasibility pump for warm starts, static problem reduction through predictive pruning, and a dynamic hybrid branching rule that blends ML scores with pseudo-costs. A synthetic generator produces realistic ARP instances with seed solutions for robust training. Results: On large instances derived from Bureau of Transportation Statistics data, TRS-GCN-guided static reduction safely pruned up to 49.2% of variables and reduced the time to reach the baseline solver’s 12-h target objective by 52.4%. The dynamic search strategy also yielded more incumbents within fixed time budgets compared with baselines. Conclusion: Integrating TRS-GCN into MILP workflows improves search efficiency for ARPs, offering complementary gains from warm-starting, pruning, and branching without changing the underlying optimality guarantees.
Funding Information
  • Key Laboratory of Mathematical Modelling and High Performance Computing of Air Vehicles (NUAA), MIIT (202303)

This publication has 29 references indexed in Scilit: