Séminaire MOCOSY : Mixed Integer Programing, Branch-and-Cut and Constraint Programing: A comparison of three different approaches to solve the runway sequencing problem.
Intervenant:    
Philippe Baptiste
Ecole Polytechnique et CNRS
Web: http://www.lix.polytechnique.fr/~baptiste/
Date : 12 juin 2009
Heure : 11h00
Lieu :
 Salle Europe
LAAS, 7 Av. de Colonel Roche
Résumé :

 In this talk we compare the efficiency of three different exact optimization techniques on a simple problem coming from Air Traffic Control: When aircraft reach the final descent in the ``terminal radar approach control'', a set of disjoint time windows in which the landing is possible, can be automatically assigned to each aircraft. Our goal is  to compute  landing times (within these time windows) that are spaced as much as possible to avoid wake vortex effect.

We first study the complexity of the problem and we identify some special cases that are polynomially solvable. We then provide a brief overview of discrete optimization techniques such as Mixed Integer Programing (MIP) or Constraint Programing (CP) that are used to model and to solve our problem. Within the CP framework, we rely on a global constraint, the "inter-distance constraint" and we describe the first algorithm that achieves Arc-B-Consistency on this constraint. We also introduce a hybrid branch and cut relying both on MIP and CP.