=Paper=
{{Paper
|id=Vol-1623/paperapp14
|storemode=property
|title=Valid Inequalities for Time-Indexed Formulations of the Runway Scheduling Problem
|pdfUrl=https://ceur-ws.org/Vol-1623/paperapp14.pdf
|volume=Vol-1623
|authors=Igor Vasilyev, Pasquale Avella, Maurizio Boccia, Carlo Mannino
|dblpUrl=https://dblp.org/rec/conf/door/VasilyevABM16
}}
==Valid Inequalities for Time-Indexed Formulations of the Runway Scheduling Problem==
https://ceur-ws.org/Vol-1623/paperapp14.pdf
Valid Inequalities for Time-indexed Formulations
of the Runway Scheduling Problem⋆
Pasquale Avella1 , Maurizio Boccia1 , Carlo Mannino2 , and Igor Vasilyev3
1
DING - Dipartimento di Ingegneria - Università del Sannio,
{avella,maboccia}@unisannio.it
2
SINTEF ICT, carlo.mannino@sintef.no
3
Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the
Russian Academy of Sciences, Lermontov 134, 664033, Irkutsk, Russia, vil@icc.ru.
Abstract. The problem of sequencing and scheduling airplanes landing and
taking off on a runway is under consideration. We propose a new family of valid
inequalities which are obtained from the study of the single machine scheduling
problem polytope.
1 Introduction and problem statement
In this paper we consider the integrated management of departures and arrivals on
a single runway, and we will refer to this problem as ADMAN (Arrival and Depar-
ture MANagement). In ADMAN, one wants to (jointly) schedule the take-offs and
the landings of a set of airplanes F . For each arrival and departure flight i ∈ F , an
arrival/departure window Ti is given, and the flight must land/takeoff in this time
window, however the departure can be canceled (at high cost). Two successive flights i
and j on the runway must be separated by a minimum time interval sij which depends
on the involved airplanes. The official timetable provides wanted arrival and departure
times. However, when one or more airplanes are delayed, a new schedule must be found,
so that (some measure of) the deviation from the official timetable is minimized.
For details on the different approaches for AMAN and DMAN we refer the reader
to a recent survey [1]. The great majority of the approaches presented in the literature
are heuristic or meta-heuristic - see again [1], but also the literature discussion in the
recent paper by [2].
As for MIP approaches, we observe first that ADMAN can be interpreted as a
classical single machine scheduling problem with sequence dependent setup times and
earliness/tardiness objective function (for a recent paper on this problem see [3]). The
runway corresponds to the machine, flights correspond to jobs and time separations
between flights on the runway to setup times. In this paper the Time Indexed (TI)
formulations is considered. In TI formulations, the time horizon is discretized in small
⋆
The research of I. Vasilyev is supported by the Russian Foundation for Basic Research,
research project No. 14-07-00382
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
788 Pasquale Avella, Maurizio Boccia, Carlo Mannino, and Igor Vasilyev
time periods. The schedule of a given flight (job) is modeled by a set of binary variables,
each associated with a feasible departure or arrival time period.
Let L and D be the sets of arriving and departure flights correspondingly, L∪D = F .
Let us associate a binary variable xit with every i ∈ F and every t ∈ Ti , which is 1
if and only if flight i arrives/departs at time t. Also, with every departure i ∈ D we
associate a binary variable yi which is 1 if i is dropped and 0 otherwise. Since every
flight is assigned (at most) one arrival/departure time in a feasible schedule, for every
i ∈ F and every k, l ∈ Ti , k ̸= l, we have xik + xil ≤ 1.
Consider now two distinct flights i, j ∈ F , and assume that the assignment k and
l violates the separation requirement between i and j, that is −sji < l − k < sij .
Then, we have either xik = 0 or xjl = 0 in any feasible solution. In turn, this can
be expressed by the constraint xik + xjl ≤ 1 and we say that the pair (of indices)
{ik, jl} is an incompatible pair. For an instance of the problem, we let I be the set of
all incompatible pairs (of indices).
With an instance of the problem, we associate an undirected graph G(V, E) called
conflict graph. The nodes of G are in one-to-one correspondence to the x variables
of the formulation and we have an edge between two nodes whenever the associated
variables cannot both assume value 1. More formally, we let
V = {it : i ∈ F, t ∈ Ti }
and
E = I ∪ {{ik, il} : ik, il ∈ V, k ̸= l}.
From the above discussion, it follows that x represents a feasible schedule, if and
only if x satisfies:
xik + xjl ≤ 1 {ik, jl} ∈ E (1)
A clique of an undirected graph is a subset of the nodes such that every two nodes
in the subset are adjacent. Incidently, observe that any pair of adjacent nodes is also
a clique (of cardinality 2). Let K be a clique of the conflict graph G(V, E), and let x
satisfy (1) then it is easy to see that x also satisfies the clique inequality:
∑
xit ≤ 1 (2)
it∈K
If K ⊆ V is a clique and u, v ∈ K, then the edge {u, v} is said to be covered by K.
An I-cover is a set of cliques K1 , K2 , . . . , such that every edge in I is covered by at
least one clique in the set. Let K = {K1 , K2 , . . . } be a I-cover. It is not difficult to see
that x satisfies (1) if and only if x satisfies the system of inequalities:
∑
(i) xi,l ≤ 1 i∈F (3)
l∈Ti
∑
(ii) xit ≤ 1 K∈K
it∈K
Title Suppressed Due to Excessive Length 789
We are finally able to write a 0,1 linear programming formulation of the problem:
∑ ∑∑
min ci yi + qit xit
i∈D i∈F t∈Ti
∑
(i) xit = 1, i ∈ L
t∈Ti
∑
(ii) xit + yi = 1, i ∈ D (4)
t∈Ti
∑
(iii) xit ≤ 1, K ∈ K
it∈K
(iv) xit ∈ {0, 1}, i ∈ F, t ∈ Ti yi ∈ {0, 1}, i ∈ D
where K = {K1 , K2 , . . . } is a I-cover and the (4.iii) define an I-cover system of in-
equalities.
Constraints (4.i) ensure that every arrival is assigned an arrival time from its time
window, whereas constraints (4.ii) ensure that every departure is either dropped or
assigned a departure time from its time window. Finally, constraints (4.iii) are the I-
cover inequalities which ensure that the schedule respects separation constraints. The
objective function represents the overall cost of the solution. Observe that constraints
(3.i) are implied by (4.i) and (4.ii), whereas 3.ii) are precisely (4.iii).
2 Valid inequalities
In order to keep the number of constraints at bay, it is important to carefully select the
cliques in the I-cover. In fact, typically most of the constraints (in real-life instances)
of (4) will belong to the I-cover system of constraints (4.iii).
One of the original and well studied example of I-cover system of inequalities (see,
e.g., [3] and [4]) is given by the family of inequalities:
∑
xjt + xik ≤ 1 i, j ∈ F, i ̸= j, t ∈ Tj (5)
k∈Ti ∩[t−sij +1,t]
Note that each clique inequality of system (5) can be strengthened by lifting in a
trivial fashion, giving the following system:
∑ ∑
xjl + xik ≤ 1 i, j ∈ F, i < j, t ∈ Tj ∪ Ti (6)
l∈Tj ∩[t−sji +1,t] k∈Ti ∩[t−sij +1,t]
In the sequel, for all Q ⊆ F , |Q| ≥ 2, and all i ∈ Q, we let si (Q) = min{sij : j ∈
Q \ i}. A family of clique inequalities valid for (4) has been recently introduced and by
Nogueira et al. in [3]:
∑ ∑
xil ≤ 1 t ∈ T. (7)
i∈F l∈[t−si (F )+1,t]∩Ti
790 Pasquale Avella, Maurizio Boccia, Carlo Mannino, and Igor Vasilyev
We refer to the formulation (4) where the I-cover system (4.iii) is given by (5) and
(7) as the Nogueira formulation.
With the aim of defining a stronger but also more compact time-indexed formu-
lation, we introduce a new family of clique inequalities - that we call (S, t)-clique
inequalities - generalizing (7):
Proposition 1. Let t ∈ T , S ⊆ F and, with |S| ≥ 2 and, for each i ∈ S, let si (S) =
min{sij : j ∈ S \ i}. The (S, t)-clique inequality:
∑ ∑
xil ≤ 1 (8)
i∈S l∈[t−si (S)+1,t]∩Ti
is valid for (4).
Proof. It follows directly from (7) and from the trivial observation that any con-
straint which is valid for a subset of flights and time periods, is also valid for the larger
sets.
Our preliminary computational experiments show, that with careful selection and
separation algorithm for (S, t)-clique inequalities (8) along with some special fixing and
lifting procedures, allow us to develop an efficient branch-and-cut method to solve the
real world instances to optimality.
References
1. J.A. Bennell, M. Mesgarpour, and C.N. Potts. Airport runway scheduling. 4OR, 9(2):115–
138, 2011.
2. F. Furini, M.P. Kidd, C.A. Persiani, and P. Toth. Improved rolling horizon approaches to
the aircraft sequencing problem. Journal of Scheduling, 18(5):435–447, 2015.
3. T. H. Nogueira, C.R.V. de Carvalho, and M.G. Ravetti. Analysis of mixed integer pro-
gramming formulations for single machine scheduling problems with sequence dependent
setup times and release dates. Optimization Online, 2014.
4. J.P. Sousa and L.A. Wolsey. A time indexed formulation of non-preemptive single machine
scheduling problems. Mathematical Programming, 54(1-3):353–367, 1992.