A Semidefinite Relaxation for
Air Traffic Flow Scheduling

arXiv:cs/0609145v1 [cs.CE] 26 Sep 2006

Alexandre d’Aspremont∗

Laurent El Ghaoui†

February 22, 2018

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 essentially 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 relaxation 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 to an
aircraft occupying a sector at a certain time, with the aircraft routes correspond to lists of tasks that have to
performed in sequence and where the sector capacities correspond to server capacities. In our case, a few
key distinctions simplify the problem formulation. First, the different tasks are independent (one aircraft’s
route is not dependent on another). Second, for each aircraft, no time gap is allowed between two tasks (we
assume that aircraft can’t be held en-route).
Scheduling problems are notoriously hard combinatorial problems. Classic instances include the jobshop scheduling problem (see [CB76] for example) or the travelling salesman problem (see [RSL77] for
example). Semidefinite relaxations and randomization techniques have and excellent track record, which
can be traced to [LS91], [Ali95], [GW95] and [PW95] among others. Recently, [FMOF01] applied these
techniques to aircraft conflict avoidance for free flight, by adjusting aircraft speed and bearing.
In this paper, we first formulate the air traffic flow scheduling problem as a mixed integer linear programming problem. We then apply the lifting procedure of [GW95] to formulate a semidefinite relaxation
∗
†

ORFE Department, Princeton University, Princeton, NJ 08544. alexandre.daspremont@m4x.org
EECS Department, U.C. Berkeley, Berkeley, CA 94720. elghaoui@eecs.berkeley.edu

1

of the problem. Because of the structure of our problem here, we only have dn binary variables, where d
is the maximum delay and n the number of flights, which means that the semidefinite relaxation has one
semidefinite constraint of size dn + 1, allowing to scale better than classic scheduling problem relaxations.
We then detail a randomization procedure based on that of [GW95] that uses the matrix solution of the
semidefinite relaxation to further improve the quality of the solution. While [FMOF01] focus on free flight
and conflict avoidance, our main concern is on meeting sector capacity constraints, a key limiting factor in
the European airspace, by adjusting delay at departure. This relative simplicity allows the algorithm to scale
very well with the number of aircraft. Finally, because of its particular structure, we show that this relaxation is amenable to first-order methods for large-scale semidefinite optimization such as those detailed in
[HR00] and [Nes04] which are natural algorithms for solving large-scale problems for which a low precision
is required.
The paper is organized as follows. The second section defines the main scheduling problem and formulates it as a mixed integer linear program. The third section derives the semidefinite relaxation of that
problem. In the fourth section, we show how to exploit the result of this relaxation to further improve the
solution using a randomization technique. Finally, in section five, we present some numerical results.

2 Problem formulation
Suppose we are given routes for n aircraft flying across an airspace composed of m sectors with capacities
given by C ∈ Rm . We decompose a particular day into T periods, so that a particular flight route starting at
time s can represented by a matrix R(i,s) ∈ Rm×T such that:
( (i,s)
Rjt = 1 if aircraft i is in sector j at time t
(i,s)

Rjt

= 0 if not.

We can formulate the problem of minimizing total delay while satisfying capacity constraints as:
Pn Pd
xij j
minimize
Pni=1 Pdj=0
subject to
x R(i,s+j) ≤ C
Pdi=1 j=0 ij
j=0 xij = 1
xij ∈ {0, 1}, i = 1, . . . , n, j = 0, . . . , d,

(1)

in the variable xij ∈ Rn×(d+1) where d is the maximum delay (in units of time). Here, xij = 1 means that
P
aircraft i will be delayed by j units of time (because x is a binary variable and dj=0 xij = 1, there can only
be a single nonzero xij for each aircraft i). The first constraint makes sure that sector capacity constraints
are met and the objective is the sum of aircraft delays.

3 Semidefinite Relaxation
In this section, we apply the lifting procedure detailed in [GW95] to form a semidefinite relaxation of
problem (1). We can rewrite (1) as a non-convex quadratic program (QP):
Pn Pd
minimize
j=0 xij j
Pi=1
n Pd
subject to
x R(i,s+j) ≤ C
(2)
Pdi=1 j=0 ij
j=0 xij = 1
x2ij − xij = 0, i = 1, . . . , n, j = 0, . . . , d,
2

in the variable xij ∈ Rn×(d+1) . We can rewrite this problem as:
Pn Pd
minimize
j=0 xij j
Pi=1
n Pd
(i,s+j) ≤ C
subject to
j=0 xij R
Pi=1
d
i = 1, . . . , n
j=0 xij = 1,
X = vec(x) vec(x)T
diag(X) = vec(x)

(3)

in the variables xij ∈ Rn×(d+1) and X ∈ Sn(d+1) . This is a non-convex quadratic program and is computationally hard. We now detail how to obtain a convex relaxation of problem (3) using Lagrangian duality.

3.1 Lagrangian relaxation
Let us start from a general nonconvex quadratically constrained quadratic program (QCQP):
minimize xT P0 x + q0T x + r0
subject to xT Pi x + qiT x + ri ≤ 0,

(4)

i = 1, . . . , m,

with variable x ∈ Rn , and parameters Pi ∈ Sn , qi ∈ Rn , and ri ∈ R. We form the Lagrangian,
!T
!
m
m
m
X
X
X
T
λi ri .
λi qi
x + r0 +
λi Pi x + q0 +
P0 +
L(x, λ) = x
i=1

i=1

i=1

To find the dual function, we minimize over x, using the general formula (see example 4.5 in [BV04]):

r − 14 q T P † q, if P  0 and q ∈ R(P )
T
T
inf x P x + q x + r =
−∞, otherwise.
x∈R
The dual function is then:
g(λ) =

inf n L(x, λ)

x∈R

1
= −
4

q0 +

m
X
i=1

λi q i

!T

P0 +

m
X
i=1

λi Pi

!†

q0 +

m
X

λi q i

i=1

!

+

m
X

λi ri + r0 .

i=1

We can form the dual of (4), using Schur complements (cf. §A.5.5):
P
maximize γ + m
i ri + r0
i=1 λ
P
P


(P0 + m
(q0 + m
i=1 λi Pi )
i=1 λi qi ) /2
P
subject to
0
T
(q0 + m
−γ
i=1 λi qi ) /2
λi ≥ 0, i = 1, . . . , m,

(5)

in the variable λ ∈ Rm . As the dual to (4), this is a convex program, it is in fact a semidefinite program
(SDP). This SDP is called the Lagrangian relaxation of the nonconvex QCQP. It can be solved efficiently
and gives a lower bound on the optimal value of the nonconvex QCQP. We form take the dual of program
(5) (see [BV04, §5.9.2]):
minimize Tr(XP0 ) + q0T x + r0
T
subject to 
Tr(XPi ) +
 qi x + ri ≤ 0,
X x
 0,
xT 1

i=1,. . . ,m,

with variable x ∈ Rn , X ∈ Sn and parameters Pi ∈ Sn , qi ∈ Rn , and ri ∈ R.
3

(6)

3.2 A relaxation of the scheduling problem
Using the results of the previous section, we can form the Lagrangian relaxation of (3) as:
Pn Pd
minimize
j=0 xij j
Pi=1
n Pd
subject to
x R(i,s+j) ≤ C
Pdi=1 j=0 ij
x = 1, i = 1, . . . , n,
 j=0 ij

X
vec(x)
0
vec(x)T
1
diag(X) = vec(x),

(7)

which is a semidefinite program in the variables xij ∈ Rn×(d+1) and X ∈ Sn(d+1) and can be solved
efficiently. The objective of this program is a lower bound on the global solution.

3.3 First-order methods
An important structural property of problem (7) is that, because diag(X) = vec(x) and 1T x = n the
matrix variable:


X
vec(x)
vec(x)T
1

has constant trace equal to n + 1. This means that the dual of (7) is a maximum conic eigenvalue minimization problem for which efficient first-order methods such as the spectral bundle algorithm of [HR00]
and the optimal first-order method of [Nes04]. In Section 5, we present numerical experiments using the
SBmethod code by [HR00] on increasingly large randomly chosen problems. SBmethod solves large-scale
dense instances for which it returns a solution (x, X). It can also solve much larger problems by exploiting
sparsity, in which case however it only returns the optimal x, which somewhat decreases the performance
of the randomization methods detailed in the next section.

4 Randomization
The Lagrangian relaxation techniques developed in §3.1 provided lower bounds on the optimal value of the
program in (4), but did not however give any particular hint on how to compute good feasible points. The
semidefinite relaxation in (6) produces a positive semidefinite or covariance matrix together with the lower
bound on the objective. In this section, we exploit this additional output to compute good approximate
solutions with, in some cases, hard bounds on their suboptimality.

4.1 Randomization
In section 3.1, the original nonconvex QCQP:
minimize xT P0 x + q0T x + r0
subject to xT Pi x + qiT x + ri ≤ 0,
was relaxed into:

minimize Tr(XP0 ) + q0T x + r0
T
subject to 
Tr(XPi ) +
 qi x + ri ≤ 0,
X x
 0.
xT 1
4

i = 1, . . . , m,

i = 1, . . . , m,

(8)

The last (Schur complement) constraint being equivalent to X − xxT  0, if we suppose x and X are the
solution to the relaxed program in (8), then X − xxT is a covariance matrix. If we pick x as a Gaussian variable with x ∼ N (x, X − xxT ), x will solve the nonconvex QCQP in (4) “on average” over this distribution,
meaning:
minimize E(xT P0 x + q0T x + r0 )
subject to E(xT Pi x + qiT x + ri ) ≤ 0, i = 1, . . . , m,
and a “good” feasible point can then be obtained by sampling x a sufficient number of times, then simply
keeping the best feasible point. Of course the direct sampling technique above does not guarantee that a
feasible point will be found. In particular, if the program includes an equality constraint, then this method
will certainly fail. However, it is sometimes possible to directly project the random samples onto the feasible
set. As we will see below, this is the case here

4.2 Randomized schedules
Suppose we have solved
Pn Pd
minimize
j=0 xij j
Pi=1
n Pd
subject to
xij R(i,s+j) ≤ C
Pdi=1 j=0
x = 1, i = 1, . . . , n,
 j=0 ij

X
vec(x)
0
vec(x)T
1
diag(X) = vec(x),
to get an optimal xij ∈ Rn×(d+1) and X ∈ Sn(d+1) . We can simply sample a Gaussian variable u ∼
N (x, X − xxT ) and compute its projection v on


d

X
\
n×(d+1)
n×(d+1)
xij = 1, i = 1, . . . , n .
{0, 1}
x∈R
:


j=0

We then compute the delay for each feasible random schedule v and keep the best solution.

5 Numerical Example
To fix ideas, let us begin by solving a very simple scheduling example. Suppose that there are only four
sectors and two flights.

4
1 2 3
Each sector has capacity one. In our format, a solution where both flights leave on time will be represented
by x = (1, 0, 1, 0) and a solution where flight 1 is delayed by one unit of time will be written as x =
(0, 1, 1, 0). Flight one starts from sector 1 and ends in sector 4, while flight 2 starts from sector 3 and also
ends in sector 4. It takes each flight one unit of time to cross each sector and both flights are scheduled to

5

depart at time 1 and conflict in sectors 2 and 3. The maximum delay is 1 unit of time. The problem variables
are x ∈ R4 and X ∈ S4 , the linear sector capacity constraints impose:
 1 0 0 0 

















0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0

0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0

0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0

0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0









x ≤ 1








and the objective vector is given by c = (0, 1, 0, 1). We solve (7) using SEDUMI by [Stu99] to get the
following solution:




1/2
1/2


x=
1/2 
1/2

0.50
 0.24
and X = 
0.24
0.24

0.24
0.50
0.24
0.24

0.24
0.24
0.50
0.24

0.24
0.24 
.
0.24 
0.50

Here, the solution is not binary valued. The reason for this is symmetry, the problem too simple and symmetric in flights one and two, so the solution is a mix of the two optimal solutions. This is easily fixed
by adding a small random perturbation to the objective (implicitly breaking the tie by giving one aircraft
priority over another). The solution is then:
 


1
1
0
 
 0
x =   and X = 
0
0
1
1

0
0
0
0

0
0
0
0

1
0 
.
0 
1

Here, the fact that X = xxT also shows that the relaxation is tight and that the solution x is globally optimal.

5.1 Computing times
Here, we generate random problems in an airspace with 50 sectors and a maximum delay of 2 units of time.
In Figure 1, plot of CPU time (in minutes) versus number of aircraft for these problems.
With n = 20 for example, the computing time is about 6 minutes, for a problem with 1018 possible
schedules. While general-purpose interior point solvers such as SEDUMI by [Stu99] can solve reasonably
large problem instances. Using the fact that the semidefinite program in (7) has constant trace, more specialized first order methods (see [HR00] or [dEGJL05] and [d’A05] for example) can be used to solve much
larger problems.

5.2 Randomization
To illustrate the randomization method detailed in §4, we first solve problem (7) on a random problem
with 5 sectors, 3 flights and a maximum delay of 4 units of time. The solution x to (7) has an objective

6

1

4

10

10

3

10

0

CPU time

CPU time

10

−1

10

2

10

1

10

−2

10

0

10

PSfrag replacements

PSfrag replacements

−3

10

0

10

1

2

10

−1

10

10

1

2

10

10

n

3

10

n

Figure 1: Log-log plot of CPU time (in minutes) versus number of aircraft for randomly generated
problems, left: interior point methods, right: spectral bundle method.

value of 3, which gives a lower bound on the global optimum. We then generate 100 sample points from
u ∼ N (x, X − xxT ) and compute their projection v on


d

X
\
xij = 1, i = 1, . . . , n .
{0, 1}n×(d+1)
x ∈ Rn×(d+1) :


j=0

For those sample schedules that meet the capacity constraints, we compute the total delay. Figure 2 shows
the distribution of these objective values. We notice that the best delay found by randomization is equal
7

6

Samples

5

4

3

2

PSfrag replacements

1

0

3

3.5

4

4.5

5

5.5

6

Total delay
Figure 2: Histogram of randomized objective values (Total delay).

to 3, which matches the lower bound produced by solving problem (7). This shows that 3 is the globally
optimum delay and that the corresponding randomized solution is optimal.

7

Acknowledgements
The authors would like to acknowledge financial support from Eurocontrol grant C20083E/BM/05 and a gift
from Google, Inc.

References
[Ali95]

F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial
optimization. SIAM Journal on Optimization, 5:13–51, 1995.

[BV04]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[CB76]

E.G. Coffman and J.L. Bruno. Computer and job-shop scheduling theory. Wiley, 1976.

[d’A05]

A. d’Aspremont. Smooth optimization for sparse semidefinite programs. ArXiv: math.OC/0512344,
2005.

[dEGJL05] A. d’Aspremont, L. El Ghaoui, M.I. Jordan, and G. R. G. Lanckriet. A direct formulation for sparse PCA
using semidefinite programming. Advances in Neural Information Processing Systems, 17:41–48, 2005.
[FMOF01] E. Frazzoli, Z. H. Mao, J. H. Oh, and E. Feron. Aircraft conflict resolution via semi-definite programming.
AIAA J. of Guidance, Control, and Dynamics, 24(1):79–86, 2001.
[GW95]

M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42:1115–1145, 1995.

[HR00]

C. Helmberg and F. Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on
Optimization, 10(3):673–696, 2000.

[LS91]

L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on
Optimization, 1(2):166–190, 1991.

[NEG05]

Arnab Nilim and Laurent El Ghaoui. Robust solutions to markov decision problems with uncertain transition matrices. To appear in Operations Research, 2005.

[Nes04]

Y. Nesterov. Smoothing technique and its application in semidefinite optimization. CORE Discussion
Paper No. 2004/73, 2004.

[PW95]

S. Poljak and H. Wolkowicz. Convex relaxations of (0, 1)-quadratic programming. Mathematics of
Operations Research, 20(3):550–561, 1995.

[RSL77]

D. J. Rosenkrantz, R.E. Stearns, and P.M. Lewis. An analysis of several heuristics for the traveling
salesman problem. SIAM J. Comput., 6:563–581, 1977.

[Stu99]

J. Sturm. Using SEDUMI 1.0x, a MATLAB toolbox for optimization over symmetric cones. Optimization
Methods and Software, 11:625–653, 1999.

8

