Article ID: | iaor20091271 |
Country: | United Kingdom |
Volume: | 59 |
Issue: | 3 |
Start Page Number: | 372 |
End Page Number: | 380 |
Publication Date: | Mar 2008 |
Journal: | Journal of the Operational Research Society |
Authors: | Jiang H. |
Keywords: | inventory, lagrange multipliers, programming: mathematical, programming: probabilistic, yield management |
Airline seat inventory control is the allocation of seats in the same cabin to different fare classes such that the total revenue is maximized. Seat allocation can be modelled as dynamic stochastic programs, which are computationally intractable in network settings. Deterministic and probabilistic mathematical programming models are therefore used to approximate dynamic stochastic programs. The probabilistic model, which is the focus of this paper, has a nonlinear objective function, which makes the solution of large-scale practical instances with off-the-shelf solvers prohibitively time consuming. In this paper, we propose a Lagrangian relaxation (LR) method for solving the probabilistic model by exploring the fact that LR problems are decomposable. We show that the solutions of the LR problems admit a simple analytical expression which can be resolved directly.