Solving the Hierarchical Data Selection Problem Arising In Airline Revenue Management Systems

In this paper, we describe an important optimization problem arising in airline revenue management systems. The problem is to select the maximum number of average fare data while keeping the selected data in strict hierarchical order. We first formulate the problem mathematically using 0-1 binary integer programming, and then further derive a stronger formulation using clique cuts. Moreover, an extension of the problem is studied where the relative importance of each data point can be derived from passenger count information. We develop an efficient dynamic programming-based algorithm to solve the problem optimally. The preliminary computational results using real airline data show that our approach can solve the problem efficiently and save significantly much information that are previously discarded