Disruption recovery at airports: Integer programming formulations and polynomial time algorithms

We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground holding or to be cancelled. We present polynomial time algorithms based on the primal-dual schema and show that the algorithms find an optimal solution if the problem is feasible. These algorithms return an optimal mix of which flights to be ground-held and which ones to be cancelled.