A Semidefinite Relaxation for Air Traffic Flow Scheduling

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
Submitted to RIVF 2007

Keywords

Computational Engineering, Finance, and Science

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/116179

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0609145
 http://arxiv.org/abs/cs/0609145

Collections

arXiv