The sales based integer program for post-departure analysis in airline revenue management: model and solution

Airline revenue management (RM) departments pay remarkable attention to many different applications based on sales-based linear program (SBLP). SBLP is mainly used as the optimization core to solve network revenue management problems in RM decision support systems. In this study we consider a post-departure analysis, when there is no more randomness in the problem and we can tackle SBLP with integrality constraints on the variables (SBIP) in order to understand which should be the best possible solution. We propose a new formulation based on a market-service decomposition that allows to solve large instances of SBIP using LP-based branch-and-bound paradigm. We strengthen the bound obtained with the linear relaxations by introducing effective Chvàtal-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. Numerical results are reported. Providing realistic integral solutions move forward the network revenue management state of the art.