A heuristic method to solve the Sales Based Integer Program for Airlines Network Revenue Management

Airline Revenue Management (RM) Departments pay remarkable attention to many different applications based on Sales Based Linear Program (SBLP). SBLP is mainly used by airlines to evaluate the performance of their RM systems, as well as it plays the role of optimization core for some RM Decision Support Systems. In this study, we consider Sales Based Integer Program (SBIP) formulation. We propose a new formulation based on Market-Service decomposition that allows to solve large instances of SBIP. We strengthen the linear relaxations of subproblems generated in LP-based branch-and-bound paradigm by introducing effective Chvatal-Gomory cuts. Main idea is to optimally allocate the capacity to the markets by transforming the market subproblems into a piecewise linear objective function. Major advantages are significant reduction of the problem size and the possibility of deriving a concave objective function which is strengthened dynamically.