On the Tractability of the Piecewiselinear Approximation for General Discrete-Choice Network Revenue Management
The choice network revenue management (RM) model incorporates customer purchase behavior as customers purchasing products with certain probabilities that are a function of the offered assortment of products, and is the appropriate model for airline and hotel network revenue management, dynamic sales of bundles, and dynamic assortment optimization. The underlying stochastic dynamic program is intractable and even its certainty-equivalence approximation, in the form of a linear program called Choice Deterministic Linear Program (CDLP) is difficult to solve in most cases. The separation problem for CDLP is NP-complete for MNL with just two segments when their consideration sets overlap; the affine approximation of the dynamic program is NP-complete for even a single-segment MNL. This is in contrast to the independent-class (perfect-segmentation) case where even the piecewise-linear approximation has been shown to be tractable. In this paper we investigate the piecewise-linear approximation for network RM under a general discrete-choice model of demand. We show that the gap between the CDLP and the piecewise-linear bounds is within a factor of at most 2. We then show that the piecewise-linear approximation is polynomially-time solvable for a fixed consideration set size, bringing it into the realm of tractability for small consideration sets; small consideration sets are a reasonable modeling tradeoff in many practical applications. Our solution relies on showing that for any discrete-choice model the separation problem for the linear program of the piecewise-linear approximation can be solved exactly by a Lagrangian relaxation. We give modeling extensions and show by numerical experiments the improvements from using piecewise-linear approximation functions.
|Date of creation:||Jan 2014|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: +34 93 542-1222
Fax: +34 93 542-1223
Web page: http://www.barcelonagse.eu
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Sumit Kunnumkal & Kalyan Talluri, 2011. "Equivalence of Piecewise-Linear Approximation and Lagrangian Relaxation for Network Revenue Management," Working Papers 608, Barcelona Graduate School of Economics.
- Summit Kunnumkal & Kalyan Talluri, 2012. "A New Compact Linear Programming Formulation for Choice Network Revenue Management," Working Papers 677, Barcelona Graduate School of Economics.
- Tudor Bodea & Mark Ferguson & Laurie Garrow, 2009. "Data Set--Choice-Based Revenue Management: Data from a Major Hotel Chain," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 356-361, December.
- Joern Meissner & Arne Strauss, 2008.
"Network Revenue Management with Inventory-Sensitive Bid Prices and Customer Choice,"
MRG/0008, Department of Management Science, Lancaster University, revised Apr 2010.
- Meissner, Joern & Strauss, Arne, 2012. "Network revenue management with inventory-sensitive bid prices and customer choice," European Journal of Operational Research, Elsevier, vol. 216(2), pages 459-468.
- Hauser, John R & Wernerfelt, Birger, 1990. " An Evaluation Cost Model of Consideration Sets," Journal of Consumer Research, University of Chicago Press, vol. 16(4), pages 393-408, March.
- Qian Liu & Garrett van Ryzin, 2008. "On the Choice-Based Linear Programming Model for Network Revenue Management," Manufacturing & Service Operations Management, INFORMS, vol. 10(2), pages 288-310, October.
- Gustavo Vulcano & Garrett van Ryzin & Wassim Chaar, 2010. "OM Practice--Choice-Based Revenue Management: An Empirical Study of Estimation and Optimization," Manufacturing & Service Operations Management, INFORMS, vol. 12(3), pages 371-392, February.
- Constantinos Maglaras & Joern Meissner, 2006.
"Dynamic Pricing Strategies for Multiproduct Revenue Management Problems,"
Manufacturing & Service Operations Management,
INFORMS, vol. 8(2), pages 136-148, July.
- Constantinos Maglaras & Joern Meissner, 2003. "Dynamic Pricing Strategies for Multi-Product Revenue Management Problems," Working Papers MRG/0002, Department of Management Science, Lancaster University, revised Nov 2005.
- Kalyan Talluri & Garrett van Ryzin, 2004. "Revenue Management Under a General Discrete Choice Model of Consumer Behavior," Management Science, INFORMS, vol. 50(1), pages 15-33, January.
When requesting a correction, please mention this item's handle: RePEc:bge:wpaper:749. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Bruno Guallar)
If references are entirely missing, you can add them using this form.