Duality in Integer Programming and its Application to Integrated Airline Planning

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The strength of linear programming duality is well known and it is one of the most acclaimed results in theory and practice. On the other hand, it is usually taken for granted that duality is not doable for integer programs. The objective of this proposal is to break the perception barrier by showing that indeed it is possible to compute an analog to the linear programming dual vector for an integer program. A new family of dual functions for integer programs is proposed. Several properties and many results with linear programming counterparts are given. More importantly, an algorithm is proposed that computes such a function for an integer program and it is shown that in a reasonable amount of time an optimal dual function can be computed. The proposed dual functions apply only to pure integer programs and their extension to mixed integer programs is required. In addition, the framework for an algorithm that computes a dual function from the branch-and-cut tree is given. One of the applications of dual functions is in decomposition algorithms. We design a novel decomposition approach to integrated airline planning. Many decision support systems require sensitivity analysis of the underlying optimization models. For example, decision makers like to get estimates on the change of profitability if a unit of a resource is changed or price of a product is modified by a small amount. Existing tools use ad-hoc techniques to perform sensitivity analysis. In this proposal we explore the area of more scientific and practical approaches to sensitivity analysis. The proposed theory and algorithms also yield new methodology for solving large-scale models deemed so far intractable.