Technical Note—A Note on Relaxations of the Choice Network Revenue Management Dynamic Program

Sumit Kunnumkal () and Kalyan Talluri ()
Additional contact information
Sumit Kunnumkal: Indian School of Business, Hyderabad, India 500032
Kalyan Talluri: Imperial College Business School, South Kensington Campus, London SW7 2AZ, UK

Operations Research, 2016, vol. 64, issue 1, 158-166

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 / ( min i { r i 1 } ) , where r i 1 > 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.

Keywords: network revenue management; discrete choice models; dynamic programming (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1453 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:1:p:158-166

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().