On the Tractability of the Piecewiselinear Approximation for General Discrete-Choice Network Revenue Management

Sumit Kunnumkal and Kalyan Talluri

No 749, Working Papers from Barcelona School of Economics

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 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.

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: 2015-09
New Economics Papers: this item is included in nep-dcm
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://bw.bse.eu/wp-content/uploads/2015/09/749-file.pdf (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:bge:wpaper:749

Access Statistics for this paper

More papers in Working Papers from Barcelona School of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Bruno Guallar ().