Integer programming models for ground-holding in air traffic flow management

In this dissertation, integer programming models are applied to combinatorial problems in air traffic flow management. For the two problems studied, models are developed and analyzed both theoretically and computationally. This dissertation makes contributions to integer programming while providing efficient tools for solving air traffic flow management problems.; Currently, a constrained arrival capacity situation at an airport in the United States is alleviated by holding inbound aircraft at their departure gates. The ground holding problem (GH) decides which aircraft to hold on the ground and for how long. This dissertation examines the GH from two perspectives. First, the hubbing operations of the airlines are considered by adding side constraints to GH. These constraints enforce the desire of the airlines to temporally group banks of flights. Five basic models and several variations of the ground holding problem with banking constraints (GHB) are presented. A particularly strong, facet-inducing model of the banking constraints is presented which allows one to solve large instances of GHB in less than half-an-hour of CPU time.; Secondly, the stochastic nature of arrival capacity is modeled by an integer program that provides the optimal trade-off between ground delay and airborne delay. The dual network properties of the integer program allow one to obtain integer solutions directly from the linear programming relaxation.; This model is designed to work in close conjunction with the most recent operational paradigms developed by the joint venture between the FAA and the airlines known as collaborative decision making (CDM). Both these paradigms and the impact of CDM on the decision making process in air traffic flow management are thoroughly discussed.; The work on banking constraints analyzes several alternative formulations. It involves the use of auxiliary decision variables, the application of special branching techniques and the use of facet-inducing constraints. The net result is to reduce by several orders of magnitude the computation time and resources necessary to solve the integer program to optimality. The work on the stochastic ground holding problem shows that the model's underlying matrix is totally unimodular by transforming the dual into a network flow model.