On the Tractability of the Piecewiselinear Approximation for General Discrete-Choice Network Revenue Management
AbstractThe 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Barcelona Graduate School of Economics in its series Working Papers with number 749.
Date of creation: Jan 2014
Date of revision:
optimization techniques; programming models; dynamic analysis; air transportation; sports; gambling; recreation; tourism; production management;
Find related papers by JEL classification:
- C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
- L93 - Industrial Organization - - Industry Studies: Transportation and Utilities - - - Air Transportation
- L83 - Industrial Organization - - Industry Studies: Services - - - Sports; Gambling; Restaurants; Recreation; Tourism
- M11 - Business Administration and Business Economics; Marketing; Accounting - - Business Administration - - - Production Management
This paper has been announced in the following NEP Reports:
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.:
- Summit Kunnumkal & Kalyan Talluri, 2012. "A New Compact Linear Programming Formulation for Choice Network Revenue Management," Working Papers 677, Barcelona Graduate School of Economics.
- 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.
- 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.
- 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.
- Joern Meissner & Arne Strauss, 2008. "Network Revenue Management with Inventory-Sensitive Bid Prices and Customer Choice," Working Papers MRG/0008, Department of Management Science, Lancaster University, revised Apr 2010.
- 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.
- 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.
- 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.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Bruno Guallar).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.