Sonia Cafieri

David Rey

Maximizing the Number of Conflict-free Aircraft using Mixed-Integer Nonlinear Programming

Keywords: Mixed-integer nonlinear programming, Conflict detection and resolution, Air traffic control, Deterministic global optimization, Modeling

We address the conflict detection and resolution problem in air traffic control, where an aircraft conflict is a loss of separation between aircraft trajectories. Conflict avoidance is crucial to ensure flight safety and remains a challenging traffic control problem. We focus on speed control to separate aircraft and consider two approaches: (i) maximize the number of conflicts resolved and (ii) identify the largest set of conflict-free aircraft. Both problems are modeled using mixed-integer nonlinear programming and a tailored greedy algorithm is proposed for the latter. Computational efficiency is improved through a pre-processing algorithm which attempts to reduce the size of the conflict resolution models by detecting the existence of pairwise potential conflicts. Numerical results are provided after implementing the proposed models and algorithms on benchmark conflict resolution instances. The results highlight the benefits of using the proposed pre-processing step as well as the versatility and the efficiency of the proposed models.

Introduction

One of the missions of air traffic control services is to ensure the safety of aircraft throughout their flight. This task is achieved by continuously monitoring aircraft trajectories, anticipating potential loss of separation, known as conflict, and issuing appropriate conflict resolution maneuvers. Due to the forecasted increase in flight travel volume in the next decades (see, e.g., [START_REF]Eurocontrol long-term forecast: IFR Flight Movements 2010-2030[END_REF]), the automation of conflict detection and resolution procedures has received a growing attention over the past few years. Indeed, the traffic growth is likely to impact air traffic controllers workload, with consequent safety issues which could lead to considerable delays.

Aircraft conflict avoidance can be achieved through a variety of maneuvers to separate aircraft trajectories. Flight heading angle deviation is the most widely used separation maneuver. Alternatively, flight level changes can be performed, even if they are usually not preferred due to passenger comfort and fuel consumption considerations. Another possibility is to adjust flights' speed subject to aerodynamical and passenger comfort constraints. In contrast to other separation maneuvers, speed control often requires some level of automation to be operated due to the (small) magnitude of the possible speed adjustments and is therefore seldom used by air traffic controllers ( [START_REF] Granger | Optimal resolution of en-route conflicts[END_REF]). See [START_REF] Kuchar | A review of conflict detection and resolution modeling methods, Intelligent Transportation Systems[END_REF] for a review up to the year 2000 of mathematical models for aircraft conflict avoidance.

The approach proposed in the present work aims at performing conflict avoidance by aircraft speed control and is based on mixed-integer optimization, which is attracting a growing attention in Air Traffic Management (ATM), in particular for air conflict detection and resolution problems. First approaches of this kind date back to 2002 ( [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF][START_REF] Richards | Aircraft trajectory planning with collision avoidance using mixed integer linear programming[END_REF]), where mixed-integer linear programs were proposed, based on aircraft separation by heading or speed changes, derived from geometrical considerations on aircraft trajectories. More recently, the works of [START_REF] Alonso-Ayuso | A mixed 0-1 nonlinear optimization model and algorithmic approach for the collision avoidance in ATM: velocity changes through a time horizon[END_REF][START_REF] Alonso-Ayuso | Conflict avoidance: 0-1 linear models for conflict detection & resolution[END_REF][START_REF] Alonso-Ayuso | On modeling the air traffic control coordination in the collision avoidance problem by mixed integer linear optimization[END_REF] extend the models of [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF] through mixed-integer nonlinear programs based on various aircraft separation techniques. [START_REF] Omer | A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers[END_REF] proposes a mixed-integer linear programming model for air conflict resolution which combines speed and heading maneuvers and relies on a space-discretization of aircraft trajectories. Mixed-integer nonlinear programming for aircraft speed change maneuvers executed in time windows is proposed in [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF]. Recent works that focus exclusively on speed regulation maneuvers also include [START_REF] Rey | Minimization of potential air conflicts through speed regulation[END_REF][START_REF] Rey | Equity-oriented aircraft collision avoidance model[END_REF][START_REF] Rey | Subliminal speed control in air traffic management: Optimization and simulation[END_REF], where a space-discretization approach is used to represent aircraft trajectories and separation. An overview of MINLP modeling for aircraft conflict avoidance is presented in [START_REF] Cafieri | MINLP in air traffic management: Aircraft conflict avoidance[END_REF].

In most of the above works, it is implicitly assumed that the range of the selected separation maneuvers is broad enough to resolve all conflicts. In this context, the aim is generally detecting and solving all conflicts that may occur in the monitored airspace during a time horizon, and the focus is to optimize the amount of resources-typically minimizing the deviation to aircraft nominal trajectories-used for deconfliction. However, if one restricts himself to a subset of possible separation maneuvers, it may happen that not all conflicts can be resolved. For instance, if the available separation maneuvers are limited (e.g. finite number of alternative trajectories) or if their range is tightly constrained (as in the case of speed deviations), and the number or the severity of the potential conflicts is significant (e.g. high aircraft density), then the selected separation maneuvers may not suffice to ensure the feasibility of the corresponding optimization problem where one aims at separating all aircraft. Hence, it can be of interest to optimize the number of conflicts that can be solved when a separation maneuver is applied, in order to easily distinguish between conflicts that can be solved and those that require the application of another separation strategy. This lead in [START_REF] Rey | Minimization of potential air conflicts through speed regulation[END_REF][START_REF] Rey | Equity-oriented aircraft collision avoidance model[END_REF][START_REF] Rey | Subliminal speed control in air traffic management: Optimization and simulation[END_REF][START_REF] Cafieri | Maximizing the number of solved aircraft conflicts through velocity regulation[END_REF] to propose objective functions and models seeking to maximize the number of conflicts resolved or to minimize the total conflict duration.

The interest for this kind of approaches specially applies to deconfliction based on speed control. Speed control-based conflict resolution models emerged at the beginning of the XXI century with the advent of advanced flight management systems that provided more accurate trajectory predictions [START_REF] Warren | Trajectory prediction concepts for next generation air traffic management[END_REF]. Building on this technological development, speed control methods offered a new way to improve traffic conditions by adjusting aircraft future longitudinal positions. Soon after, the concept of subliminal speed control was introduced on the premise that minor speed adjustments around aircraft nominal speeds were almost imperceptible to air traffic controllers. This paradigm has been validated in field experiments [START_REF] Drogoul | Erasmus strategic deconfliction to benefit sesar[END_REF] in the context of the ERASMUS [START_REF] Brochard | Erasmus -en route air traffic soft management ultimate system[END_REF] project. Due to its limited impact on air traffic controllers' workload [START_REF] Athènes | ATC complexity and controller workload: Trying to bridge the gap[END_REF], conflict avoidance by subliminal speed control is considered a promising approach to introduce some automation in ATM in the near future to improve traffic conditions using a very moderate amount of control resources. It constitutes a competitive candidate to introduce a "filter" on air traffic, prior to the use of more trajectory-intensive conflict avoidance methods (e.g. heading and altitude maneuvers) that would require either controller intervention or a fully automated traffic control paradigm. From a practical point of view, the approach proposed in this paper can be intended as a first step, acting as a pre-processing, to efficiently perform conflict avoidance.

In this paper, building on [START_REF] Cafieri | Maximizing the number of solved aircraft conflicts through velocity regulation[END_REF], we first present a model from mixedinteger nonlinear programming (MINLP) to maximize the number of solved conflicts (pairwise separated aircraft) when this maneuver is applied. This model, following [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF], does not require any form of discretization, unlike the most of previous works in the area, thus resulting in a compact mixed-integer nonlinear program. The computational performance of such a MINLP is improved by a novel technique to identify potential aircraft conflicts, based on the solution of a simple concave bound-constrained continuous maximization problem. The detection of potential conflicts is carried out in a preprocessing phase where pairwise conflicts are identified before a complete model, i.e. with all the relevant pairs of aircraft, is solved. Then, based on the observation that for a large number of aircraft in the observed air sector it may be difficult to solve many conflicts simultaneously, and that, even not imposing solving all conflicts, the problem can be computational demanding, we propose a novel approach to identify the largest set of conflict-free aircraft. To this aim, we first propose a MINLP model and then, to improve its computational sustainability, a greedy algorithm that iteratively removes conflicting aircraft from the original set containing all the observed aircraft. Numerical experiments show that the proposed approach allows us to find competitive solutions.

The paper is organized as follows. In Section 2 we first discuss about the mathematical representation of aircraft trajectories separation, then we propose a mathematical programming formulation, from MINLP, for aircraft conflict avoidance achieved through speed regulation. Section 3 focuses on conflict detection, and presents an algorithm to identify potential aircraft conflicts when speed control is applied. In Section 4 we propose an approach to identify the largest set of aircraft that are conflict-free when speed regulation is applied. This is done through a MINLP problem, as well as a greedy aircraft-removal algorithm tailored on the problem. In Section 5 we present and discuss the results of numerical experiments carried out to validate the proposed approaches. Section 6 draws some conclusions and presents some perspectives.

Problem Modeling

In this section, we first discuss the mathematical representation of the crucial condition of separation between aircraft trajectories. Then, we propose a mathematical programming formulation for aircraft conflict avoidance, where the above separation condition clearly represents the main constraint on the decision variables.

Representation of Aircraft Separation

Let us consider a set A of n aircraft flying during their cruise flight in a given air sector, all at the same flight level. Let x i (t) be the vector representing the position of flight i at time t. The relative position of aircraft i and j at time t can be represented as

x r ij (t) = x i (t) -x j (t).
Let d be the horizontal separation standard, aircraft i and j are separated if

x r ij (t) ≥ d, ∀t (1)
where • is the Euclidean norm in the two-dimensional space formed by aircraft trajectories. Assuming that uniform motion laws apply, x r ij (t) can also be expressed as the sum of the initial relative position of flights i and j, x r0 ij , and their relative speed, v r ij : x r ij (t) = x r0 ij + v r ij t. Therefore squaring Equation ( 1) we obtain the separation condition

f ij (t) ≡ v r ij 2 t 2 + 2x r0 ij • v r ij t + x r0 ij 2 -d 2 ≥ 0 ( 2
)
where • is the inner product in the Euclidean space. From Equation (2), f ij (t) is a 2nd order convex polynomial in t which is minimal when its derivative vanishes:

f ij (t) = 0 ⇔ t m ij = -x r0 ij • v r ij v r ij 2 (3)
t m ij is the time at which f ij (t) is minimal and therefore represents the instant at which the aircraft relative position is minimal. Following [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF], we observe that, substituting t m ij in f ij (t), the separation condition (2) can be represented

as v r ij 2 ( x r0 ij 2 -d 2 ) -(x r0 ij • v r ij ) 2 ≥ 0. ( 4
)
that does not depend anymore on t.

Observe that the discriminant of the 2nd order equation

f ij (t) = 0, ∆ ij , is equal to ∆ ij = 4(x r0 ij • v r ij ) 2 -4 v r ij 2 ( x r0 ij 2 -d 2 ), (5)
so the following cases can occur:

1. if ∆ ij ≤ 0, then f ij (t) has no roots and therefore x r ij (t) ≥ d, ∀t, hence aircraft are separated 2. otherwise, aircraft are in conflict. Let t ij and t ij be the roots of f ij (t) = 0:

t ij = -2(x r0 ij • v r ij ) -∆ ij 2 v r ij 2
and

t ij = -2(x r0 ij • v r ij ) + ∆ ij 2 v r ij 2 (6)
where t ij and t ij are the instants of entry and exit from the conflict. In this case, aircraft are separated only when both roots are negative (the conflict was in the past). We will refer to the above conditions as condition 1 and condition 2 on ∆ ij . Hence, note that imposing the separation condition (4) is equivalent as imposing ∆ ij ≤ 0. This condition is employed in the mathematical model presented below.

Maximizing the Number of Solved Conflicts

In [START_REF] Cafieri | Maximizing the number of solved aircraft conflicts through velocity regulation[END_REF] a nonlinear mixed-integer program was introduced to maximize the number of aircraft conflicts that can be solved by only performing speed control. Here we recall the main elements of such a model and propose some extensions. The main motivation for this kind of modeling is that, as discussed in Section 1, when a subset of possible separation maneuvers is considered, we are not guaranteed to be able to solve all conflicts, i.e. the resulting mathematical program may be infeasible. This may specially occur for approaches focused on speed control, and is reinforced by the request of a subliminal control which imposes minor speed variations, thus restricting the feasible region of the problem. In contrast, alternative separation maneuvers, such as heading angle changes and vertical maneuvers, are generally sufficient to resolve all conflicts.

As we want to maximize the number of solved conflicts, that is equivalent to maximize the number of aircraft pairs that are separated, we introduce the following binary decision variable, for each pair (i, j):

z ij =
1 if aircraft i and j are separated 0 otherwise [START_REF] Alonso-Ayuso | Conflict avoidance: 0-1 linear models for conflict detection & resolution[END_REF] Since we focus on speed control to separate aircraft trajectories, the other main decision variables are continuous variables q i , ∀i ∈ A, representing the speed variation rate of each aircraft, expressed as a percentage of its norm.

A value q i = 1 corresponds to an unchanged speed. Each q i is restricted to a fixed range [q i , q i ], which ensure a subliminal control when q i and q i are chosen in such a way that the aircraft speed is between -6% and +3% of the original speed (see [START_REF] Drogoul | Erasmus strategic deconfliction to benefit sesar[END_REF]). The actual velocity of aircraft i is then given by v i q i , with v i the airspeed vector, and the relative speed of aircraft i and j is expressed by

v r ij = v i q i -v j q j . (8)
Using the above condition ∆ ij ≤ 0, and the definition of z ij , aircraft separation can then be represented using the following constraint:

(2z ij -1) v r ij 2 ( x r0 ij 2 -d 2 ) ≥ (2z ij -1)(x r0 ij • v r ij ) 2 ∀i, j ∈ A : i < j (9)
Note that Eq. ( 9) does not impose a separation condition to all pairs of aircraft. It is instead used to account for pairs of aircraft (i, j) for which the separation condition is verified (z ij = 1), either thanks to an employed speed control (at least one between q i and q j is not equal to 1), or because i and j have separated trajectories regardless of their speed variations. Remark that [START_REF] Omer | A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers[END_REF] does not guarantee to count all pairs of aircraft that are separated (for instance, those for which condition 2 on ∆ ij holds).

The mathematical programming model seeking to maximize the number of conflicts that are solved amongst all pairs of aircraft using speed control can be summarized as follows, in Model 1.

Model 1 (Max.VC). max i,j∈A:i<j z ij [START_REF] Cafieri | Aircraft deconfliction with speed regulation: new models from mixed-integer optimization[END_REF] subject to

(2z ij -1) v r ij 2 ( x r0 ij 2 -d 2 ) ≥ (2z ij -1)(x r0 ij • v r ij ) 2 ∀i, j ∈ A : i < j (11) v r ij = v i q i -v j q j ∀i, j ∈ A : i < j ( 12
)
q i ≤ q i ≤ q i ∀i ∈ A (13)
z ij ∈ {0, 1} ∀i, j ∈ A : i < j (14)
The proposed model can be enriched adjoining further conditions to check for aircraft separation. In particular, this can be done taking into account the geometry of the considered trajectories. Aircraft trajectories are usually represented by straight lines, that, for a pair of aircraft in an air sector observed during a time window, can be supposed intersecting in no more than one point. Thus, the inner product x r0 ij • v r ij can be used to identify if aircraft are converging or diverging. If aircraft are initially separated and their trajectories are diverging, then they will remain separated. Namely:

• if t m ij ≥ 0, i.e
. the instant of minimal separation is in the future, then aircraft are converging and they can be involved in a conflict;

• if t m ij < 0, i.e. the instant of minimal separation is in the past, then aircraft are diverging and collision has therefore already been avoided, although aircraft could still be in conflict (violate the separation standards).

Recall that the time of minimal separation is given by t

m ij = -x r0 ij • v r ij / v r ij 2 . If ||v r ij || = 0
, then aircraft trajectories are parallel and aircraft fly at the same speed. If the smallest distance between aircraft trajectories is less than the separation norm, there is a risk of conflict. Two cases may occur: if aircraft fly in the same direction, then their separation can be determined by comparing their initial distance with the separation norm; otherwise, aircraft fly in opposite directions and will be in conflict upon crossing one another. In both cases, this situation can be easily checked in a pre-processing step, and the pair of aircraft can be omitted from the set of considered pairs. Assume that v r ij > 0, the sign of t m ij depends on the sign of the inner product

x r0 ij • v r ij
which can be determined using a linear combination of vector components. Let y ij be the binary variable defined as

y ij =
1 if aircraft i and j are diverging and x r0 ij ≥ d 0 otherwise

The following constraint can then be adjoined to the formulation:

(2y ij -1)(x r0 ij • v r ij ) ≥ 0 ( 15
)
To ensure that a pair of diverging is separated we need to make sure that both aircraft are initially separated. We define the sets 15) is indexed on set P S and, in a pre-processing phase, we set y ij = 0 ∀(i, j) ∈ P N S . Note that, although Constraint ( 15) is nonlinear, it can be linearized using a Fortet's reformulation [START_REF] Fortet | Applications de l'algèbre de boole en recherche opérationelle[END_REF] for products of binary and continuous variables.

P S ≡ {i, j ∈ A : i < j, x r0 ij ≥ d} and P N S ≡ {i, j ∈ A : i < j, x r0 ij < d}. Constraint (
Finally, we account for a separated pair (i, j) either when ∆ ij ≤ 0 or the two trajectories are diverging. The or condition is modeled introducing a new variable w ij ≥ 0 and corresponding constraints

w ij ≥ z ij , w ij ≥ y ij , w ij ≤ z ij + y ij ∀i, j ∈ A : i < j
The resulting model is summarized in Model 2.

Model 2 (Max.VC+). max i,j∈A:i<j

w ij (16)
subject to

(2z ij -1) v r ij 2 ( x r0 ij 2 -d 2 ) ≥ (2z ij -1)(x r0 ij • v r ij ) 2 ∀i, j ∈ A : i < j (17) v r ij = v i q i -v j q j ∀i, j ∈ A : i < j (18) q i ≤ q i ≤ q i ∀i ∈ A (19)
(2y ij -1)(x r0 ij • v r ij ) ≥ 0 ∀(i, j) ∈ P S (20)
w ij ≥ z ij ∀i, j ∈ A : i < j (21)
w ij ≥ y ij ∀i, j ∈ A : i < j (22)
w ij ≤ z ij + y ij ∀i, j ∈ A : i < j (23) z ij , y ij ∈ {0, 1} ∀i, j ∈ A : i < j (24) 0 ≤ w ij ≤ 1 ∀i, j ∈ A : i < j (25)
Model 2 is a mixed-integer nonlinear program that contains more variables and (linear) constraints than Model 1, while including an additional way to identify separated aircraft trajectories. The impact of this additional feature is discussed in Section 5.

Conflict Detection

Aircraft separation constraints appearing in Models 1 and 2 are indexed on all pairs of aircraft, which implies a large number of constraints, n(n -1)/2, for increasing n. Motivated by the observation that some pairs of trajectories may always be separated, regardless of the possible speed variations, the natural approach to reduce the size of the optimization problem of interest is to try to identify some pairs of aircraft for which the induced separation constraints can be omitted. In the remainder of this section, we define aircraft nominal and potential conflicts, and propose a novel algorithm to identify potential conflicts, based on the solution of a bound-constrained convex optimization problem.

Recall that, for each pair of aircraft, their trajectories are separated when the condition ∆ ij ≤ 0 holds, where ∆ ij is the discriminant of f ij (t). Let ∆ ij (q) be the function

q = (q i , q j ) ∈ R 2 → ∆ ij (q) ∈ R
representing the value of ∆ ij for a combination of speed variations q = (q i , q j ) of aircraft i and j. We define the set of nominal conflicts N as the set of pairs (i, j) ∈ A, i < j which violate the separation distance when aircraft nominal speeds are maintained, i.e. no speed control is applied. It follows from the definition that N can be determined by evaluating for each pair (i, j) the function ∆ ij (q) at the point (q i , q j ) = (1, 1), that is for q corresponding to no variations of aircraft speeds. This procedure is summarized in Algorithm 1.

Algorithm 1: Nominal Conflict Detection

Input: A set of aircraft A with initial position x r0 ij and speed v r ij , separation norm d, a speed control vector q Output:

A set of nominal conflicts N N ← ∅ for i ∈ A, j ∈ A : i < j do if ∆ ij (q = 1) > 0 then N ← N ∪ {(i, j)} return N
The set N , however, cannot be used to simply reduce the number of aircraft pairs on which separation constraints are indexed. Solving Model 1 by indexing its constraints using the set N may, indeed, solve some or all of these conflicts, but the newly obtained speed control vector q may also result in generating new conflicts among pairs of aircraft initially separated. To account for this issue, we seek to determine the set of potential conflicts P which contains all the pairs of aircraft that could possibly result in a loss of separation when speed control is applied. This set is then defined considering all possible values of q = (q i , q j ) for each pair of aircraft. To decide the existence of a potential conflict for a pair (i, j), let us consider the following two-variables problem:

c ij = max ∆ ij (q) : q ≤ q ≤ q , ∀i, j ∈ A : i < j (26)
If c ij > 0, then there exists at least a combination of speed variations such that ∆ ij (q) > 0, which means that aircraft may be in conflict-the pair (i, j) then belongs to P . Otherwise, aircraft i and j cannot be in conflict (regardless of the speed variations, they will always remain separated), and the associated separation constraint can be omitted in the optimization problem. To identify the pairs belonging to P , we need to solve problem (26) for all (i, j). We next show that the conditions under which ∆ ij (q) is a concave function only depend on the initial relative position of the aircraft and their initial velocity.

Proposition 1. Let i, j ∈ A : i < j be two aircraft and let q i and q j be their respective speed variation rate. We index the vector components by 1 and 2 respectively. The function ∆ ij (q) for all q such that q ≤ q ≤ q is concave if and only if Conditions C 1 , C 2 and C 3 hold:

C 1 : v 2 i,1 (d 2 -(x r0 ij,2 ) 2 ) + v 2 i,2 (d 2 -(x r0 ij,1 ) 2 ) ≤ 0 (27) C 2 : v 2 j,1 (d 2 -(x r0 ij,2 ) 2 ) + v 2 j,2 (d 2 -(x r0 ij,1 ) 2 ) ≤ 0 (28) C 3 : (v i,1 v j,2 -v i,2 v j,1 ) 2 ((x r0 ij,1 ) 2 -d 2 )((x r0 ij,2 ) 2 -d 2 ) ≥ 0 (29)
Proof. Recall that:

∆ ij (q) = 4(x r0 ij • v r ij ) 2 -4 v r ij 2 ( x r0 ij 2 -d 2 ) = 4(x r0 ij • (v i q i -v j q j )) 2 -4 v i q i -v j q j 2 ( x r0 ij 2 -d 2 )
The factor 4 in the expression of ∆ ij (q) can be ignored since it does not change the sign of c ij . Therefore ∆ ij (q) can be expressed as

∆ ij (q) = x r0 ij,1 (v i,1 q i -v j,1 q j ) + x r0 ij,2 (v i,2 q i -v j,2 q j ) 2 -(v i,1 q i -v j,1 q j ) 2 + (v i,2 q i -v j,2 q j ) 2 (x r0 ij,1 ) 2 + (x r0 ij,2 ) 2 -d 2
The second partial derivatives of ∆ ij (q) are thus:

∂ 2 ∆ ij (q) ∂q 2 i =2v 2 i,1 (d 2 -(x r0 ij,2 ) 2 ) + 2v 2 i,2 (d 2 -(x r0 ij,1 ) 2 ) ∂ 2 ∆ ij (q) ∂q 2 j =2v 2 j,1 (d 2 -(x r0 ij,2 ) 2 ) + 2v 2 j,2 (d 2 -(x r0 ij,1 ) 2 ) ∂ 2 ∆ ij (q) ∂q i ∂q j =2v i,1 v j,1 ((x r0 ij,2 ) 2 -d 2 ) + 2v i,2 v j,2 ((x r0 ij,1 ) 2 -d 2 )
Let D k,n be the nth principal minor of order k of the Hessian matrix of function ∆ ij (q). To show that ∆ ij (q) is concave, it suffices to show that its Hessian matrix is negative semidefinite, i.e. that (-1) k D k,n > 0, for each principal minor. The first order principal minors are

D 1,1 = ∂ 2 ∆ ij (q)/∂q 2 i and D 1,2 = ∂ 2 ∆ ij (q)/∂q 2 j .
By construction, if C 1 and C 2 hold, then -D 1,1 ≥ 0 and -D 1,2 ≥ 0. The second order principal minor is

D 2,1 = ∂ 2 ∆ ij (q) ∂q 2 i ∂ 2 ∆ ij (q) ∂q 2 j - ∂ 2 ∆ ij (q) ∂q i ∂q j 2 = (v i,1 v j,2 -v i,2 v j,1 ) 2 ((x r0 ij,1 ) 2 -d 2 )((x r0 ij,2 ) 2 -d 2 )
Hence if C 3 holds, then D 2,1 ≥ 0 and ∆ ij (q) is concave.

Although function ∆ ij (q) is not always concave, it is reasonable to assume that some pairs of aircraft will fall into this category. An immediate consequence of Proposition 1 is that, assuming that the initial state of flights meets the conditions C 1 , C 2 and C 3 , the value of c ij can be determined a priori using a generic NLP solver, since any local maximum of a concave function is also a global optimum. Figure 1 depicts an example of potential conflict amongst two flights with a look-ahead of 15 min and trajectories intersecting with a right angle; the maximum of the function is attained when both flights fly at the same speed. Further, its concavity can be decided analytically by evaluating Conditions C 1 , C 2 and C 3 .

q i 0.98
" ij (q i ; q j ) 0.96 0.94 0.9 We hereby denote C ij 1,2,3 the binary parameter defined as:

C ij 1,2,3 = 1 if C 1 , C 2 and C 3 hold for i, j ∈ A : i < j 0 otherwise
Algorithm 2 returns a set P of pairs of aircraft that can be used to index the separation constraints in Model 1. Namely, in such constraints we can substitute the statement ∀i < j by (i, j) ∈ P .

Algorithm 2: Potential Conflict Detection

Input: A set of aircraft A with initial position x r0 ij and speed v r ij , speed control bounds [q, q] Output: A set of potential conflicts P P ← {i, j ∈ A : i < j} for (i, j)

∈ P do if C ij 1,2,3 = 1 then c ij ← max ∆ ij (q) : q ≤ q ≤ q if c ij ≤ 0 then P ← P \ {(i, j)} return P
The impact of the detection of potential conflicts on the numerical solution of the MINLP Model 1 is discussed in Section 5.

Largest Conflict-free Aircraft Set

In this section, we present an approach to identify the largest set of aircraft among which all conflicts are solved when speed control is applied. In other words, an aircraft belongs to such a set when its trajectory is separated from that of all other aircraft in the observed air sector (and separation is achieved by speed control). Conflict resolution through speed control as represented by Models 1 and 2 seeks to solve a maximum number of conflicts given a set of aircraft. These models can provide trajectory adjustments that minimize the number of unresolved conflicts and thus work in the aircraft pairs space. Therefore, if not all conflicts can be resolved by speed control only, then their outcome indicates which pairs of aircraft remain in potential conflict. We also observe that, depending on the traffic configuration, it may be critical to work in the aircraft space, i.e., identify which aircraft should be selected for additional separation maneuvers (e.g. heading angle deviation, altitude change). To address this operational challenge, we introduce a new conflict resolution model which focuses on individual aircraft behavior instead of considering pairs of aircraft. Specifically, we propose to identify the largest set of conflict-free aircraft using speed control. This is equivalent to remove the minimal number of conflicting aircraft from the initial aircraft set. From an air traffic control perspective, this approach has a simple interpretation: the trajectories of the retained aircraft are separated while the removed aircraft can be handled by air traffic control services for trajectory management through heading and/or altitude change.

We first propose a mathematical programming formulation for the identification of the largest conflict-free aircraft set. Then, for the sake of computational efficiency, we propose an aircraft-removal algorithm aiming at solving the same problem.

Largest Conflict-free Set: MINLP

The mathematical programming formulation is based on Model 1. A new binary variable is introduced for each aircraft to decide if it belongs to the conflict-free set. It is defined, for each i ∈ A, as follows:

s i = 1 if aircraft i is in the conflict-free set 0 otherwise (30)
Recall that, for each pair of aircraft i and j, the decision variable z ij is used to represent their separation. If i and j are separated (z ij = 1), then both i and j could be included in the conflict-free set (if they are also separated from all other aircraft in the conflict-free set). In this case, variables s i and s j are free. On the other hand, if i and j are not separated (z ij = 0), then both aircraft cannot belong to the conflict-free set. This means that either s i or s j must take the value 0. Reciprocally, if both aircraft belong to the conflict-free set (s i = s j = 1), then they are separated from each other and so z ij = 1. Therefore, the linking constraint between variables z ij , s i and s j reads

s i + s j ≤ 1 + z ij ∀i, j ∈ A : i < j (31)
Equation ( 31) is then added to the constraints of Model 1. The objective function is a linear function expressed by the sum of s i , ∀i, and has to be maximized. The mathematical programming model seeking to maximize the size of the set of conflict-free aircraft using speed control can be summarized as follows, in Model 3. subject to

s i + s j ≤ 1 + z ij ∀i, j ∈ A : i < j (33) (2z ij -1) v r ij 2 ( x r0 ij 2 -d 2 ) ≥ (2z ij -1)(x r0 ij • v r ij ) 2 ∀i, j ∈ A : i < j (34) v r ij = v i q i -v j q j ∀i, j ∈ A : i < j (35) q i ≤ q i ≤ q i ∀i ∈ A ( 36
)
s i ∈ {0, 1} ∀i ∈ A (37)
z ij ∈ {0, 1} ∀i, j ∈ A : i < j (38)
Model 3 is again a MINLP, that contains n(n -1)/2 more linear constraints (in (33)) and n more integrality constraints (on variables s i ) than Model 1.

Similarly as for the case of the Model 1, Model 3 can be enhanced by introducing variables y ij and w ij and appending Constraints [START_REF] Fortet | Applications de l'algèbre de boole en recherche opérationelle[END_REF] to [START_REF] Wächter | On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[END_REF] to separate pairs based on aircraft divergence. We refer to the resulting model as Model 4 (Max.CS+).

We next propose an algorithm to identify the largest conflict-free set.

Largest Conflict-free Set: Algorithm

Alternatively to solve the above MINLP Model 3, we propose an algorithm that aims at removing the minimal number of conflicting aircraft from the initial aircraft set. It provides a "greedy" method for aircraft-removal, iteratively removing the aircraft which penalizes the most other aircrafts' trajectories.

For this section it is convenient to write the conflict resolution model using a set C ⊆ P to represent the set of current conflicts and a set A C ⊆ A to represent the set of current aircraft. Specifically, we use C instead of P and A C instead of A in Model 1. These sets are updated during the execution of the algorithm.

The algorithm starts by solving the MINLP problem 1, with constraints defined over C and A C , using the set of all aircraft and the set of nominal conflicts obtained by executing Algorithm 1. Then, the algorithm iteratively checks for unsolved conflicts and terminates if there are none. Otherwise, if all the current conflicts C have been solved, the set of not solved conflicts nS is added to C; if one or more current conflict has not been solved, the algorithm selects an aircraft to be removed. This selection is based on two sequential criteria: (i) the number of times each aircraft is involved in an unresolved conflict and, if there is more than one aircraft maximizing this criterion, (ii) the number of times each of these aircraft are involved in a potential conflict. For each solve, z denotes the value of the objective function and q the current optimal solution. The iterative process terminates when there are no more elements in the set nS. The algorithm is described in Algorithm 3.

Numerical Results

Testing environment

All considered mathematical programming models are implemented using the Ampl modeling language ( [START_REF] Fourer | AMPL: A Modeling Language for Mathematical Programming[END_REF]).

MINLP problems (Models 1, 2 and 3) are solved using the global optimization COIN-OR solver Couenne ( [START_REF] Belotti | Branching and bounds tighteningtechniques for non-convex minlp[END_REF]), that implements a spatial Branchand-Bound algorithm based on convex relaxations, with a 300s time limit for independent solves and a 60s time limit for solves within Algorithm 3. For the detection of potential conflicts, IPOPT ( [START_REF] Wächter | On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[END_REF]), implementing an Interior-Point method, is used to solve the NLPs for each pair of trajectories that form a concave program. All tests are performed on a Windows 64-bit machine with an i7 processor, a CPU at 2.9 GHz and 8 Gb of RAM.

Numerical experiments are carried out on randomly generated instances. Two types of initial aircraft configurations are considered: RCP instances : They are generated by placing n aircraft with the same speed (400 NM/h) in a 2-dimensional airspace represented by a circle of radius 100 NM or 200 NM, which headings are randomly and uniformly deviated with an angle comprised between -30 • and +30 • from the diameter of the circle. These test problems are henceforth referred to as Random Circle Problems (RCP) instances (similar instances have been used to test conflict resolution models by [START_REF] Vanaret | Benchmarking conflict resolution algorithms[END_REF][START_REF] Rey | Equity-oriented aircraft collision avoidance model[END_REF][START_REF] Rey | Subliminal speed control in air traffic management: Optimization and simulation[END_REF]).

RTP instances : They are generated by placing n aircraft with the same speed (400 NM/h) in a 2-dimensional airspace represented by a square of edge 100 NM with random headings. These test problems are designed to represent random traffic configurations where some aircraft may be diverging and/or initially violating the 5 NM separation standard and are henceforth referred to as Random Trajectory Problems (RTP) instances (similar instances have been used to test conflict resolution models by [START_REF] Alonso-Ayuso | Collision avoidance in air traffic management: A mixed-integer linear optimization approach[END_REF]).

Figure 2 depicts two benchmark problems: an RCP instance with 20 aircraft (2a) and an RTP instance with 20 aircraft (2b). RCP instances seek to represent high-density traffic configurations as no pair of aircraft is initially diverging, i.e. for each pair (i, j) ∈ A, the instant of minimal separation is always in the future t m ij > 0. We use Model 1 to resolve a maximum number of In this case, Model 2 is selected for conflict resolution since some pairs of aircraft may be separated using the y ij variables. In all tests we consider a subliminal speed control range, i.e., we set q i = 0.94 and q i = 1.03. This corresponds to speed variations comprised between -6% to +3% of aircraft nominal speed (400 NM/h). We next present results obtained using Models 1 and 2 with and without pre-processing the set of potential pairwise conflicts using Algorithm 2.

Results: Maximizing the number of resolved conflicts, with and without potential conflict detection

Tables 1 and2

q i |.
The average number of nominal conflicts for 10-aircraft RCP instances is 7.35 and the average number of potential conflicts is 20.75. These values are increased to 16.75 and 71.05 for 20-aircraft RCP instances. The results in Tables 1 and2 show the viability of Model 1 and Algorithm 2. For the most of the results, where a solution is computed, a number of aircraft pairs close to the total number of pairs, is separated in a reasonable time. Moreover, results show that using Algorithm 2 improves the computational performance in solving Model 1 by both (i) improving runtime and (ii) finding better solutions, i.e. with more separated pairs of aircraft. Specifically, when the set of potential conflicts P is used to index the constraints of Model 1, runtime is significantly reduced for some instances (best results are in bold face) and it is comparable in the other cases. In the case of comparable runtimes, often more conflicts are solved when Algorithm 2 is used, even though global optimality is not proven (Couenne with a time limit is employed to solve the MINLP). Note that it is not guaranteed that the reduced MINLP provide a better solution than the initial MINLP-with all pairs of aircraft-when the time limit is reached. Indeed, in this scenario, the spatial branch-andbound algorithm implemented within Couenne may terminate with a less effective solution when Algorithm 2 is used that without conflict detection. For 10-aircraft RCP instances, where the total number of aircraft pairs is 45, a number of separated pairs between 40 and 45 is obtained. For some 20-aircraft RCP instances, solving Model 1 without any pre-processing is unsuccessful in finding a feasible solution (the objective function value is 0) within the allocated computing time, whereas a feasible solution is always found when potential conflicts are detected. Notice that the pre-processing time is quite stable: approximately 2.8 seconds for 10-aircraft instances and 5 to 6.5 seconds for 20-aircraft instances. Hence, in most cases the runtime of Algorithm 2 is small compared to the solve time for the MINLP models. The average number of nominal conflicts for 10-aircraft RTP instances is 4.35 and the average number of potential conflicts is 13.1. These values are increased to 17.7 and 57.15 for 20-aircraft RTP instances. Tables 3 and4 summarize the results obtained solving Model 2 with and without pre-processing data using Algorithm 2 on 20 RTP instances with 10 and 20 aircraft, respectively. As in the previous case studies, for each instance, Model 2 is solved by indexing the constraints on all pairs of aircraft (columns without CD) and by indexing the constraints on the set P of potential conflicts, detected by running Algorithm 2 (columns with CD). The headings are identical to the ones of Tables 1 and2 with the addition of the fourth left-most column |P N S | which gives the cardinality of the set of initially non-separated pairs of aircraft; these pairs will remain in conflict regardless of the decisions taken. Therefore the maximum number of separable pairs (by any separation maneuver) is 45 -|P N S | for 10-aircraft instances and 190 -|P N S | for 20-aircraft instances.

The tests conducted on the RTP instances highlight the versatility of Model 2 which is able to solve several instances to optimality within the allocated computing time. In 10-aircraft instances, the optimal solution is systematically found within the allocated computing time, with or without conflict detection. While pre-processing the set of potential conflicts helps in reducing the solve time, the improvement is generally marginal. In contrast, for 20-aircraft instances, the initial MINLP struggles to find feasible solutions (instances with an objective value of 0) whereas the reduced MINLP systematically finds feasible-and sometimes optimal-solutions within the allocated solve time.

In all the tests conducted, all aircraft are systematically accelerated or decelerated. This is due to the models used which do not optimize the amount of resources required to separate aircraft. The average deviation is always comprised between 1% and 6% with most cases between 2% and 4%. While in most instances the number of aircraft accelerated and decelerated is relatively balanced, it can happen that a majority of aircraft is accelerated or decelerated, in which case more speed control resources are used.

Results: Finding the largest conflict-free aircraft set

In this section, we discuss the results of numerical experiments on the problem of finding the largest conflict-free aircraft set. These results are obtained running Couenne on Models 3 and 4, and on the other side solving the same problems, Max.CS and Max.CS+, using Algorithm 3, within which Couenne is run on Models 1 and 2. The results are presented in Tables 5,6, 7 and 8. The headings are as follows: the five (resp. six) left-most columns are identical to the ones in Tables 1 and2 (resp. Tables 3 and4), the next two columns give the objective value and the runtime after solving Model 3 (resp. 4) and the five next columns provide some detail on the implementation of Algorithm 3: |A C | is the cardinality of the obtained largest conflict-free aircraft set, N b. It. is the total number of iterations in the while loop, N b. Add. is the number of times all current conflicts are solved during the iterative process (if z = |C| is true) and N b. Rem. is the number of times at least one conflict is not solved (if z = |C| is false); finally the next column gives the total time spent solving Model 1 (resp. 2) within the iterative process.

The three right-most columns give the number of accelerated and decelerated aircraft and the average deviation from aircraft nominal speeds. A time limit of 300 seconds is imposed for each direct solve of Models 3 and 4 and a time limit of 60 seconds is imposed for each solve of Models 1 and 2 within Algorithm 3. For both solution methods, Algorithm 2, whose efficiency has been proven in the above numerical experiments, is used to pre-process the set of potential conflicts. From Tables 5 and6, we observe a drastic reduction of the computing time on most of the instances when using Algorithm 3 with respect to that of the direct solution of Max.CS by Couenne, as expected for a greedy algorithm. As for the quality of the solution, we report that the size of the final conflict-free set is always very close to its maximum possible value n, the largest number of removed aircraft being 3 for the tested instances. This is very encouraging to obtain an air sector where only a very small number of remaining conflicting aircraft need to be handled by air traffic services. Further, comparing |A C | to the objective function value of Max.CS, it appears that Algorithm 3 is able to find comparable or even better solutions (recall that the solution process of Max.CS through Couenne is stopped when a time limit is reached). On 20-aircraft instances, the direct solution of Max.CS is only able to prove optimality on three instances including two for which the entire set of flights is separable. In contrast, Algorithm 3 systematically finds feasible and competitive solutions with a maximum of 4 aircraft removed from the initial set.

The tests conducted to find the largest conflict-free set of aircraft on RTP instances exhibits similar trends. The 10-aircraft instances are efficiently solved to optimality using Model 4 and Algorithm 3 performs quite well except for instance RTP 10 6 in which the largest set found by the heuristic consists of 7 aircraft instead 10. The 20-aircraft instances are more challenging for Algorithm 3 with 5 to 12 aircraft being removed in each test, thus showing that the greedy approach can occasionally be myopic in terms of selecting which aircraft to remove from the conflict-free set.

Conclusions

In this paper, we have presented aircraft conflict resolution models which rely exclusively on speed control to separate aircraft. The proposed models are formulated using MINLP and are solved with a global optimization engine (Couenne). In contrast to previous research on conflict resolution, the presented approach does not assume any form of discretization (space or time) to solve the aircraft collision avoidance problem, hence providing exact flight trajectory adjustments. Due to the nature of the problem at hand, two formulations are proposed: (i) maximize the number of conflicts resolved and (ii) find the largest conflict-free aircraft set. Both formulations take into account the fact that not all aircraft may be separated by speed control only and thus highlight the necessity to count separated pairs of aircraft or conflict-free aircraft. The initial formulations are indexed on all pairs of aircraft, then a pre-processing step is proposed to reduce the number of necessary separation constraints by identifying potential air conflicts based on the available aircraft speed regulation range. This procedure works by considering each pair of aircraft independently and can be executed efficiently by solving a concave program, for each pair of aircraft satisfying geometric conditions only depending on their initial position and speed. Finally, a heuristic algorithm is proposed to find the largest conflict-free aircraft set based on an aircraft-removal strategy which selects aircraft penalizing the most other aircraft trajectories.

The proposed models and algorithms are tested on air traffic control benchmark instances and the results obtained highlight the benefits of using a pre-processing step to reduce the size of the MINLP formulations as well as the versatility and the efficiency of the proposed models. The heuristic algorithm is shown to significantly reduce computing time while finding competitive-if not optimal-solutions. Based on the reported runtimes, it is clear that MINLP models occasionally struggle to prove optimality although they may be efficient in finding feasible solutions with some pre-processing that reduces the constraint set size. This suggests that fast heuristic algorithms could be designed on the premise that a relatively small computing time limit is sufficient to find a feasible solution.

Future works will be focused on improving runtime and solution quality by developing further efficient solution approaches. Hybrid conflict resolution maneuvers, combining the proposed speed control-based models with heading angle deviation and/or altitude change, will be investigated to provide a more comprehensive conflict resolution framework. Finally, the robustness of the proposed solution approaches with regards to the uncertainty on aircraft trajectory prediction models will be quantified and relevant models developed.

Figure 1 :

 1 Figure 1: Plot of function ∆ ij (q) for two flights whose trajectories intersect with a right angle and distance of 100 NM from the intersection point. The separation distance is 5 NM and the speed variation is [0.94, 1.03].

  (a) An RCP instance with 20 aircraft (b) An RTP instance with 20 aircraft

Figure 2 :

 2 Figure 2: Illustration of Conflict Resolution benchmark problems

  gives the number of pairs of aircraft which satisfy Conditions C 1 , C 2 and C 3 (corresponding to a concave program), R P is the percentage of conflicting aircraft with respect to the total number of pairs, Time CD is the total pre-processing time (i.e. running Algorithm 2) expressed in seconds. The next four columns give the objective value and the runtime of Model 1 without and with pre-processing, respectively. The three right-most columns provide information on the solution with CD: Nb. Acc. is the number of aircraft accelerated, Nb. Dec. is the number of aircraft decelerated and Avg. Dev. is the average deviation in absolute value from aircraft nominal speed expressed in % i.e.1

	summarize the results obtained solving Model 1 with and without pre-processing data by detecting potential conflicts (Algorithm 2) on 20 RCP instances with 10 and 20 aircraft, respectively. Specifically, for each instance, Model 1 is first solved by indexing the constraints on all pairs of aircraft (columns without CD), and then by indexing the constraints on the set P of potential conflicts, detected by running Algorithm 2 (columns with CD). The headings are as follows: Pairs is the total number of pairs of aircraft, |N | is the cardinality of set N (nominal conflicts), |P | is the car-dinality of set P (potential conflicts), C ij 1,2,3 |A| i∈A |1 -

Table 1 :

 1 Results of the solution of Model 1 with and without Conflict Detection (CD) on RCP instances with 10 aircraft and a radius of 100NM. CD is performed using Algorithm 2. The time limit of Couenne is 300 seconds, all time measures are in seconds.

							Without CD		With CD
						Time	Obj.	Time	Obj.	Time	Nb.	Nb. Avg.
	Instance	Pairs |N |	C ij 1,2,3	|P | R P	CD	Max.VC Max.VC Max.VC Max.VC Acc. Dec. Dev.
	RCP 10 1	45	10	36	20 44.4	2.9	41	300.8	43	300.7	3	7	3.7
	RCP 10 2	45	11	36	23 51.1	2.8	43	300.6	44	300.6	3	7	3.6
	RCP 10 3	45	8	36	20 44.4	2.9	41	300.8	43	300.6	6	4	2.4
	RCP 10 4	45	7	36	23 51.1	2.9	43	300.8	43	300.1	6	4	3.0
	RCP 10 5	45	7	36	19 42.2	2.7	43	300.8	44	7.5	3	7	2.8
	RCP 10 6	45	3	36	17 37.8	2.9	44	300.3	44	4.6	1	9	1.8
	RCP 10 7	45	8	36	22 48.9	2.7	41	300.6	42	300.6	3	7	2.0
	RCP 10 8	45	3	36	19 42.2	2.7	44	300.8	44	117.1	1	9	5.0
	RCP 10 9	45	8	36	22 48.9	2.7	42	300.6	43	300.5	3	7	2.7
	RCP 10 10	45	8	36	24 53.3	2.7	43	300.5	43	300.8	5	5	3.6
	RCP 10 11	45	7	36	22 48.9	2.8	42	300.6	42	300.6	5	5	2.0
	RCP 10 12	45	10	36	21 46.7	2.9	40	301.6	42	300.6	4	6	2.9
	RCP 10 13	45	5	36	20 44.4	2.7	44	300.9	44	55.5	2	8	3.5
	RCP 10 14	45	6	36	17 37.8	2.7	42	300.7	44	16.5	2	8	4.3
	RCP 10 15	45	7	36	21 46.7	2.8	42	300.6	44	301.0	2	8	4.4
	RCP 10 16	45	7	36	23 51.1	2.7	44	300.6	44	300.8	4	6	2.6
	RCP 10 17	45	5	36	21 46.7	2.9	42	300.8	42	300.5	3	7	2.5
	RCP 10 18	45	7	36	19 42.2	2.9	45	1.9	45	0.3	3	7	2.3
	RCP 10 19	45	10	36	21 46.7	2.9	44	300.5	44	24.9	4	6	2.2
	RCP 10 20	45	10	36	21 46.7	2.8	40	300.7	42	300.6	2	8	2.6

Table 2 :

 2 Results of the solution of Model 1 with and without Conflict Detection (CD) on RCP instances with 20 aircraft and radius of 200NM. CD is performed using Algorithm 2. The time limit of Couenne is 300 seconds, all time measures are in seconds.

Table 3 :

 3 Results of the solution of Model 2 with and without Conflict Detection (CD) on RTP instances with 10 aircraft. CD is performed using Algorithm 2. The time limit of Couenne is 300 seconds, all time measures are in seconds.

		Without CD		With CD
	Time	Obj.	Time	Obj.	Time	Nb. Nb. Avg.

Table 4 :

 4 Results of the solution of Model 2 with and without Conflict Detection (CD) on RTP instances with 20 aircraft. CD is performed using Algorithm 2. The time limit of Couenne is 300 seconds, all time measures are in seconds.

Table 5 :

 5 Results of Algorithm 3 on RCP problems with 10 aircraft and a radius of 100 NM. The time limit of Couenne is 300 seconds for the direct solution of Model 3 and 60 seconds per solve within Algorithm 3.

Table 6 :

 6 Results of Algorithm 3 on RCP with 20 aircraft and a radius of 200 NM. The time limit of Couenne is 300 seconds for the direct solution of Model 3 and 60 seconds per solve within Algorithm 3.

						Time	Obj.	Time		Nb. Nb.	Nb.	Total Time Nb.	Nb. Avg.
	Instance	|N | |P N S | |P | R P	CD	Max.CS+ Max.CS+ |A C | It. Add. Rem. Max.VC+ Acc. Dec. Dev.
	RTP 10 1	4	1	10 22.2	2.7	7	1.2	7	3	0	3	0.8	2	8	5.4
	RTP 10 2	5	0	13 28.9	0.6	7	0.5	6	5	1	4	0.9	3	7	2.5
	RTP 10 3	4	0	18 40.0	0.4	8	0.4	7	4	1	3	0.5	2	8	5.4
	RTP 10 4	4	0	11 24.4	0.6	10	0.3	10	0	0	0	0.9	6	4	4.0
	RTP 10 5	3	1	15 33.3	0.5	9	0.3	8	3	1	2	1.1	3	7	3.2
	RTP 10 6	2	0	11 24.4	0.6	10	0.2	7	4	1	3	0.6	3	7	4.1
	RTP 10 7	6	1	11 24.4	0.6	8	0.5	8	3	1	2	1.6	3	7	4.6
	RTP 10 8	5	1	14 31.1	0.6	7	0.3	7	4	1	3	1.1	3	7	5.1
	RTP 10 9	4	0	12 26.7	0.6	8	0.6	7	4	1	3	0.5	0	10	6.0
	RTP 10 10	6	0	18 40.0	2.5	6	3.3	6	4	0	4	0.4	0	10	6.0
	RTP 10 11	4	1	12 26.7	0.6	9	0.5	9	2	1	1	0.9	4	6	3.6
	RTP 10 12	4	0	9	20.0	0.6	8	1.6	8	3	1	2	1.0	4	6	4.6
	RTP 10 13	5	1	13 28.9	0.5	7	2.2	6	5	1	4	1.8	2	8	5.3
	RTP 10 14	5	0	16 35.6	0.5	7	2.0	6	5	1	4	1.2	5	5	4.0
	RTP 10 15	4	1	13 28.9	2.5	8	0.5	7	4	1	3	0.6	5	5	4.5
	RTP 10 16	5	0	15 33.3	0.5	8	0.9	8	3	1	2	1.1	4	6	4.8
	RTP 10 17	6	0	14 31.1	0.5	8	1.0	8	3	1	2	1.3	2	8	5.0
	RTP 10 18	4	0	15 33.3	0.5	9	33.1	8	2	0	2	1.0	3	7	4.5
	RTP 10 19	6	0	13 28.9	2.6	6	1.1	6	5	1	4	1.4	3	7	4.0
	RTP 10 20	1	0	9	20.0	0.5	10	0.2	10	1	1	0	0.9	5	5	4.3

Table 7 :

 7 Results of Algorithm 3 on RTP problems with 10 aircraft. The time limit of Couenne is 300 seconds for the direct solution of Model 4 and 60 seconds per solve within Algorithm 3. |P N S | |P | R P CD Max.CS+ Max.CS+ |A C | It. Add. Rem. Max.VC+ Acc. Dec. Dev.

					Time	Obj.	Time		Nb. Nb.	Nb.	Total Time Nb.	Nb. Avg.
	Instance |N | RTP 20 1 17	0	54 28.4	4.6	13	300.2	11	10	1	9	37.4	9	11	4.0
	RTP 20 2	10	1	49 25.8	4.6	17	10.6	15	6	1	5	15.9	7	13	4.0
	RTP 20 3	18	2	70 36.8	4.4	0	300.2	11	10	1	9	12.3	2	18	2.9
	RTP 20 4	20	1	64 33.7	4.6	12	300.3	10	11	1	10	14.7	4	16	3.0
	RTP 20 5	19	2	55 28.9	4.4	13	300.1	11	10	1	9	59.1	5	15	4.1
	RTP 20 6	13	2	61 32.1	4.4	15	300.2	13	8	1	7	13.8	5	15	3.9
	RTP 20 7	20	3	54 28.4	4.4	13	300.3	11	10	1	9	67.7	6	14	3.1
	RTP 20 8	16	0	53 27.9	4.6	13	300.5	12	9	1	8	25.9	2	18	4.9
	RTP 20 9	16	0	54 28.4	4.7	14	300.2	13	8	1	7	31.5	6	14	3.2
	RTP 20 10 21	0	55 28.9	4.5	15	300.5	13	8	1	7	10.0	3	17	3.6
	RTP 20 11 18	1	57 30.0	4.5	14	300.4	11	10	1	9	16.6	5	15	2.6
	RTP 20 12 23	0	66 34.7	4.3	0	300.4	12	9	1	8	137.6	9	11	3.6
	RTP 20 13 22	2	65 34.2	4.4	0	300.6	10	11	1	10	12.6	1	19	4.0
	RTP 20 14 14	2	52 27.4	4.4	15	300.5	13	8	1	7	25.1	4	16	4.7
	RTP 20 15 19	2	59 31.1	4.3	15	300.3	12	8	0	8	21.4	6	14	3.4
	RTP 20 16 21	1	55 28.9	4.4	13	300.5	12	9	1	8	16.8	3	17	4.0
	RTP 20 17 18	2	64 33.7	4.5	13	300.1	13	8	1	7	15.3	4	16	4.0
	RTP 20 18 22	2	68 35.8	4.4	12	300.3	8	13	1	12	15.2	3	17	3.1
	RTP 20 19 10	3	43 22.6	4.4	15	300.6	14	7	1	6	15.2	5	15	4.4
	RTP 20 20 17	1	45 23.7	4.5	14	7.4	12	9	1	8	25.1	6	14	3.0

Table 8 :

 8 Results of Algorithm 3 on RTP problems with 20 aircraft. The time limit of Couenne is 300 seconds for the direct solution of Model 4 and 60 seconds per solve within Algorithm 3.

Acknowledgment

Financial support by French National Research Agency (ANR) through grant ANR 12-JS02-009-01 "ATOMIC" is gratefully acknowledged.

Algorithm 3: Algorithm for finding the Largest Conflict-free Set

Input: A set of aircraft A with initial position x r0 ij and speed v r ij , separation norm d, speed control vector q and bounds [q, q] Output: A conflict-free aircraft set A C ⊆ A and an optimized speed control vector q for these aircraft

// if many, choose at random within the obtained subset r ← rand(arg max{ν i : i ∈ μ})