Powerful Modelling Using Monotone Binary Variables: An Application to Air Traffic Flow Management *
Decanato - Facoltà di scienze informatiche
Data d'inizio: 24 Marzo 2010
Data di fine: 25 Marzo 2010
The Faculty of Informatics is pleased to announce a seminar given by Guglielmo Lulli
DATE: Wednesday, March 24th, 2010
PLACE: USI Università della Svizzera italiana, room SI-008, Informatics building (Via G. Buffi 13)
Many decision problems can be framed in the context of a set of requests requiring a complex time-based interaction amongst a set of available resources. For instance scheduling, one of the classic problem in Operations Research, belongs to this class.
For this class of problem we present a new formulation approach which uses monotone binary variables. After presenting some polyhedral insights on formulating decision problems with monotone binary variables we present a successful application to Air Traffic Flow Management.
For this decision problem, we present a new Integer Programming (IP) model for large-scale instances of the Air Traffic Flow Management (ATFM) problem. The model covers all the phases of each flight, i.e., take-off, en route cruising and landing, and solves for an optimal combination of flow management actions, including ground-holding, rerouting, speed control and airborne holding on a flight-by-flight basis. A distinguishing feature of the model is that it allows for rerouting decisions. This is achieved through the imposition of sets of "local" conditions, which make it possible to represent rerouting options in a compact way by only introducing some new constraints. Moreover, three classes of valid inequalities are incorporated into the model to strengthen the polyhedral structure of the underlying relaxation.
A wide computational analysis on realistic instances demonstrated the viability of the proposed model. We report short computational times (less than 15 minutes) on instances of the size of the US air traffic control system that make it realistic that our approach can be used as the main engine of managing air traffic in the US. Given that our approach includes all the air traffic control decisions (ground holding, air holding, adjusting speed of aircraft and rerouting) combined with the attractive computational times, makes us optimistic that this approach may succeed in becoming the main air traffic control engine.
* This work is joint with D. Bertsimas and A. Odoni.
Guglielmo Lulli is Assistant Professor of Operations Research at University of Milano-Bicocca. He received a PhD in Operations Research in 2003 from the University of Rome "La Sapienza". During his studies, he visited the NEXTOR center at University of Maryland and the System and Industrial Engineering Department at University of Arizona, both for one year appointment. In 2007, he was recipient of a Fulbright Fellowship at Massachusetts Institute of Technology. His research interests focus on mathematical programming and stochastic programming particularly as applied to transportation and logistic operations, air traffic flow management and bio-computational problems.
HOST: Prof. Evanthia Papadopoulou