Advanced Search
MyIDEAS: Login to save this article or follow this journal

On the Choice-Based Linear Programming Model for Network Revenue Management


Author Info

  • Qian Liu

    (Industrial Engineering and Logistics Management Department, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong)

  • Garrett van Ryzin

    (Graduate School of Business, Columbia University, New York, New York 10027)

Registered author(s):


    Gallego et al. [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. CORC Technical Report TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York.] recently proposed a choice-based deterministic linear programming model (CDLP) for network revenue management (RM) that parallels the widely used deterministic linear programming (DLP) model. While they focused on analyzing "flexible products"--a situation in which the provider has the flexibility of using a collection of products (e.g., different flight times and/or itineraries) to serve the same market demand (e.g., an origin-destination connection)--their approach has broader implications for understanding choice-based RM on a network. In this paper, we explore the implications in detail. Specifically, we characterize optimal offer sets (sets of available network products) by extending to the network case a notion of "efficiency" developed by Talluri and van Ryzin [Talluri, K. T., G. J. van Ryzin. 2004. Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50 15-33.] for the single-leg, choice-based RM problem. We show that, asymptotically, as demand and capacity are scaled up, only these efficient sets are used in an optimal policy. This analysis suggests that efficiency is a potentially useful approach for identifying "good" offer sets on networks, as it is in the case of single-leg problems. Second, we propose a practical decomposition heuristic for converting the static CDLP solution into a dynamic control policy. The heuristic is quite similar to the familiar displacement-adjusted virtual nesting (DAVN) approximation used in traditional network RM, and it significantly improves on the performance of the static LP solution. We illustrate the heuristic on several numerical examples.

    Download Info

    If 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.
    File URL:
    Download Restriction: no

    Bibliographic Info

    Article provided by INFORMS in its journal Manufacturing & Service Operations Management.

    Volume (Year): 10 (2008)
    Issue (Month): 2 (October)
    Pages: 288-310

    as in new window
    Handle: RePEc:inm:ormsom:v:10:y:2008:i:2:p:288-310

    Contact details of provider:
    Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA
    Phone: +1-443-757-3500
    Fax: 443-757-3515
    Web page:
    More information through EDIRC

    Related research

    Keywords: network revenue management; choice behavior; multinomial logit choice model; dynamic programming; linear programming;


    No references listed on IDEAS
    You can help add them by filling out this form.


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as in new window

    Cited by:
    1. Gönsch, Jochen & Koch, Sebastian & Steinhardt, Claudius, 2014. "Revenue management with flexible products: The value of flexibility and its incorporation into DLP-based approaches," International Journal of Production Economics, Elsevier, vol. 153(C), pages 280-294.
    2. Summit Kunnumkal & Kalyan Talluri, 2012. "A New Compact Linear Programming Formulation for Choice Network Revenue Management," Working Papers 677, Barcelona Graduate School of Economics.
    3. Steinhardt, Claudius & Gönsch, Jochen, 2012. "Integrated revenue management approaches for capacity control with planned upgrades," European Journal of Operational Research, Elsevier, vol. 223(2), pages 380-391.
    4. Meissner, Joern & Strauss, Arne, 2012. "Improved bid prices for choice-based network revenue management," European Journal of Operational Research, Elsevier, vol. 217(2), pages 417-427.
    5. Jochen Goensch & Claudius Steinhardt, 2013. "Using Dynamic Programming Decomposition for Revenue Management with Opaque Products," BuR - Business Research, German Academic Association for Business Research, vol. 6(1), pages 94-115, May.
    6. Sumit Kunnumkal & Kalyan Talluri, 2014. "On the Tractability of the Piecewiselinear Approximation for General Discrete-Choice Network Revenue Management," Working Papers 749, Barcelona Graduate School of Economics.
    7. Weaver, Robert D. & Moon, Yongma, 2011. "Pricing Perishables," 2011 International European Forum, February 14-18, 2011, Innsbruck-Igls, Austria 122007, International European Forum on Innovation and System Dynamics in Food Networks.
    8. Joern Meissner & Arne Strauss & Kalyan Talluri, 2011. "An Enhanced Concave Program Relaxation for Choice Network Revenue Management," Working Papers MRG/0020, Department of Management Science, Lancaster University, revised Jan 2011.
    9. Sumit Kunnumkal & Kalyan Talluri, 2014. "On the tractability of the piecewise-linear approximation for general discrete-choice network revenue management," Economics Working Papers 1409, Department of Economics and Business, Universitat Pompeu Fabra.
    10. Arne Strauss & Kalyan Talluri, 2012. "A tractable consideration set structure for network revenue management," Economics Working Papers 1303, Department of Economics and Business, Universitat Pompeu Fabra, revised Oct 2012.
    11. Houyuan Jiang & Zhan Pang, 2011. "Network capacity management under competition," Computational Optimization and Applications, Springer, vol. 50(2), pages 287-326, October.
    12. Sumit Kunnumkal & Kalyan Talluri, 2012. "A new compact linear programming formulation for choice network revenue management," Economics Working Papers 1349, Department of Economics and Business, Universitat Pompeu Fabra.


    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.


    Access and download statistics


    When requesting a correction, please mention this item's handle: RePEc:inm:ormsom:v:10:y:2008:i:2:p:288-310. 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: (Mirko Janc).

    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.