On Bounds for Network Revenue Management

Network Revenue Management can be formulated as a stochastic dynamic programming problem ("optimal" solution) 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 the randomized linear programming (RLP) model, both of which give upper bounds on the optimal solution value. 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 [14] have proposed alternate upper bounds 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 Adelman's bound is weaker than the bound given by the RLP model (we call the perfect hind sight or PH bound), and that the RLP bound is weaker than Topaloglu's bound. To summarize our paper ranks the bounds as follows: DLP>/= Adelman's affine relaxation (AR) bound>/= PHIP and PHLP>/= Topaloglu's Lagrangian (LR) bound>/=Optimal Solution