  We address the aircraft conflict resolution problem in air traffic control.
We introduce new mixed-integer programming formulations for aircraft conflict
resolution with speed, heading and altitude control which are based on
disjunctive linear separation conditions. We first examine the two-dimensional
aircraft conflict resolution problem with speed and heading control represented
as continuous decision variables. We show that the proposed disjunctive linear
separation conditions are equivalent to the traditional nonlinear conditions
for aircraft separation. Further, we characterize conflict-free pairwise
aircraft trajectories and propose a simple pre-processing algorithm to identify
aircraft pairs which are either always conflict-free, or which cannot be
separated using speed and heading control only. We then incorporate altitude
control and propose a lexicographic optimization formulation that aims to
minimize the number of flight level changes before resolving outstanding
conflicts via two-dimensional velocity control. The proposed mixed-integer
programming formulations are nonconvex, and we propose convex relaxations,
decomposition methods and constraint generation algorithms to solve the
two-dimensional and lexicographic optimization formulations to guaranteed
optimality. Numerical experiments on four types of conflict resolution
benchmarking instances are conducted to test the performance of the proposed
mixed-integer formulations. Further, the proposed disjunctive formulations are
compared against state-of-the-art formulations based on the so-called shadow
separation condition. Our numerical results show that the proposed disjunctive
linear separation conditions outperform existing formulations in the literature
and can solve significantly more instances to global optimality. For
reproducibility purposes, all formulations and instances are made available on
a public repository.
