A note on relaxations of the choice network revenue management dynamic program

File Description SizeFormat 
upperBounds_final.pdfAccepted version180.58 kBAdobe PDFView/Open
Title: A note on relaxations of the choice network revenue management dynamic program
Authors: Talluri, KT
Kunnumkal, S
Item Type: Journal Article
Abstract: In recent years, several approximation methods have been proposed for the choice network revenue management problem. These approximation methods are proposed because the dynamic programming formulation of the choice network revenue management problem is intractable even for moderately sized instances. In this paper, we consider three approximation methods that obtain upper bounds on the value function, namely, the choice deterministic linear program (CDLP), the affine approximation (AF), and the piecewise-linear approximation (PL). It is known that the piecewise-linear approximation bound is tighter than the affine bound, which in turn is tighter than CDLP. In this paper, we prove bounds on how much the affine and piecewise-linear approximations can tighten CDLP. We show (i) the gap between the AF and CDLP bounds is at most a factor of 1+1/(mini{r1i}), where r1i>0 are the resource capacities, and (ii) the gap between the piecewise-linear and CDLP bounds is within a factor of 2. Moreover, we show that these gaps are essentially tight. Our results hold for any discrete-choice model and do not involve any asymptotic scaling. Our results are surprising because calculating the AF bound is NP-hard and CDLP is tractable for a single-segment multinomial logit model; our result implies that if a firm has all resource capacities of 100, the gap between the two bounds, however, is at most 1.01.
Issue Date: 21-Jan-2016
Date of Acceptance: 25-Sep-2015
ISSN: 1526-5463
Publisher: INFORMS (Institute for Operations Research and Management Sciences)
Start Page: 158
End Page: 166
Journal / Book Title: Operations Research
Volume: 64
Issue: 1
Copyright Statement: Copyright © 2016, INFORMS
Keywords: Operations Research
0102 Applied Mathematics
0802 Computation Theory And Mathematics
1503 Business And Management
Publication Status: Published
Appears in Collections:Imperial College Business School

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons