dc.contributor |
Universitat Pompeu Fabra. Departament d'Economia i Empresa |
dc.contributor.author |
Kunnumkal, Sumit |
dc.contributor.author |
Talluri, Kalyan T. |
dc.date |
2014-01-01 |
dc.identifier.citation |
https://econ-papers.upf.edu/ca/paper.php?id=1409 |
dc.identifier.uri |
http://hdl.handle.net/10230/21809 |
dc.format |
application/pdf |
dc.language.iso |
eng |
dc.relation |
Economics and Business Working Papers Series; 1409 |
dc.rights |
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
dc.subject |
optimization techniques; programming models; dynamic analysis; air transportation ; sports; gambling; recreation; tourism; production management |
dc.subject |
Operations Management |
dc.title |
On the tractability of the piecewise-linear approximation for general discrete-choice network revenue management |
dc.type |
info:eu-repo/semantics/workingPaper |
dc.description.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. |