A strong lagrangian relaxation for general discrete-choice network revenue management
File(s)
Published version
Author(s)
Kunnumkal, Sumit
Talluri, Kalyan
Type
Journal Article
Abstract
Discrete-choice network revenue management (DC-NRM) captures both customer behaviorand the resource-usage interaction of products, and is appropriate for airline and hotel revenuemanagement, dynamic sales of bundles in advertising, and dynamic assortment optimizationin retail. The state-space of the DC-NRM stochastic dynamic program explodes and approxi-mation methods such as the choice deterministic linear program (CDLP), the affine, and thepiecewise-linear approximations have been proposed to approximate it in practice. The affinerelaxation (and thereby, its generalization, the piecewise-linear approximation) is intractableeven for the simplest choice models such as the multinomial logit (MNL) choice model with asingle segment. In this paper we propose a new Lagrangian relaxation method for DC-NRMbased on an extended set of multipliers. An attractive feature of our method is that the numberof constraints in our formulation scales linearly with the resource capacities. While the num-ber of constraints in our formulation is an order of magnitude smaller that the piecewise-linearapproximation (polynomial vs exponential), it obtains a bound that is as tight as the piecewise-linear bound. If we assume that the consideration sets of the different customer segments aresmall in size—a reasonable modeling tradeoff in many practical applications—our method is anindirect way to obtain the piecewise-linear approximation on large problems effectively. Ourresults are not specific to a particular functional form (such as MNL), but hold for any discrete-choice model of demand. We show by numerical experiments that our Lagrangian relaxationmethod can provide substantial improvements over existing benchmark methods, both in termsof tighter upper bounds, as well as revenues from policies based on the relaxation.
Date Issued
2019-05-01
Date Acceptance
2019-01-22
Citation
Computational Optimization and Applications, 2019, 73 (1), pp.275-310
ISSN
0926-6003
Publisher
Springer (part of Springer Nature)
Start Page
275
End Page
310
Journal / Book Title
Computational Optimization and Applications
Volume
73
Issue
1
Copyright Statement
© 2019 The Author(s). This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution,
and reproduction in any medium, provided you give appropriate credit to the original author(s) and the
source, provide a link to the Creative Commons license, and indicate if changes were made.
and reproduction in any medium, provided you give appropriate credit to the original author(s) and the
source, provide a link to the Creative Commons license, and indicate if changes were made.
Subjects
Science & Technology
Technology
Physical Sciences
Operations Research & Management Science
Mathematics, Applied
Mathematics
Dynamic programming approximations
Transportation
Revenue management
Choice models
MODEL
Operations Research
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
Publication Status
Published
Date Publish Online
2019-03-22