EconPapers    
Economics at your fingertips  
 

On the tractability of the piecewise-linear approximation for general discrete-choice network revenue management

Sumit Kunnumkal and Kalyan Talluri ()

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

Abstract: 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 independentclass (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 piecewiselinear 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.

Keywords: Optimization Techniques; Programming Models; Dynamic Analysis; Air Transportation; Sports; Gambling; Recreation; Tourism; Production Management (search for similar items in EconPapers)
JEL-codes: C61 L83 L93 M11 (search for similar items in EconPapers)
Date: 2014-01
New Economics Papers: this item is included in nep-dcm and nep-tur
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://econ-papers.upf.edu/papers/1409.pdf Whole Paper (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:upf:upfgen:1409

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by ( this e-mail address is bad, please contact ).

 
Page updated 2024-06-15
Handle: RePEc:upf:upfgen:1409