On Bounds for Network Revenue ManagementKalyan Talluri ()
Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra Abstract: The Network Revenue Management problem can be formulated as a stochastic dynamic programming problem (DP or the “optimal” solution V*) whose exact solution is computationally intractable. Consequently, a number of heuristics have been proposed in the literature, the most popular of which are the deterministic linear programming (DLP) model, and a simulation based method, the randomized linear programming (RLP) model. Both methods give upper bounds on the optimal solution value (DLP and PHLP respectively). These bounds are used to provide control values that can be used in practice to make accept/deny decisions for booking requests. Recently Adelman [1] and Topaloglu [17] have proposed alternate upper bounds, the affine relaxation(AR) bound and the Lagrangian relaxation (LR) bound respectively, and showed that their bounds are tighter than the DLP bound. Tight bounds are of great interest as it appears from empirical studies and practical experience that models that give tighter bounds also lead to better controls (better in the sense that they lead to more revenue). In this paper we prove relationships between all these bounds. Specifically, we show that the RLP bound is weaker than LR bound, and a variation of the AR bound that we call strong AR bound (sAR) is tighter than the LR bound. To summarize, our paper ranks the bounds as follows: DLP?PHLP?LR?sAR?V*. Keywords: Revenue management; bid-prices; relaxations; bounds (search for similar items in EconPapers) Downloads: (external link) Related works: Access Statistics for this paper More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
Econpapers is hosted by the
Swedish Business School at Örebro University.