《2016 A Semidefinite Relaxation for Air Traffic Flow Scheduling》.pdf

A Semidefinite Relaxation for Air Traffic Flow Scheduling Alexandre d’Aspremont∗ Laurent El Ghaoui† September 26, 2006 Abstract We first formulate the problem of optimally scheduling air traffic low with sector capacity constraints as a mixed integer linear program. We then use semidefinite relaxation techniques to form a convex relaxation of that problem. Finally, we present a randomization algorithm to further improve the quality of the solution. Because of the specific structure of the air traffic flow problem, the relaxation has a single semidefinite constraint of size dn where d is the maximum delay and n the number of flights. 1 Introduction In this paper, given a schedule of flights and their routes we solve the problem of finding a new schedule that satisfies a list of sector capacity constraints and minimizes the total delay compared to the original scheduled. While the optimal routing problem with weather uncertainty and capacity constraints is essen- tially intractable, [NEG05] show that robust optimal routing of a single aircraft under weather and traffic uncertainty can be solved efficiently as a robust Markov dynamic programming (MDP) problem. So the problem we solve here should be seen as a second phase: given the routes computed using MDP, our relax- ation produces an optimal schedule, satisfying capacity constraints while minimizing the total delay. While this scheduling problem is significantly simpler than the global routing problem, it still combinatorial (and in fact NP-Hard), hence we need to formulate a relaxation to obtain approximate solutions efficiently. We can interpret this problem as particular case of job shop scheduling problem where a task corresponds t