A strong lagrangian relaxation for general discrete-choice network revenue management

File Description SizeFormat 
A-strong-Lagrangian-relaxation-for-general.pdfPublished version2.26 MBAdobe PDFView/Open
Title: A strong lagrangian relaxation for general discrete-choice network revenue management
Authors: Kunnumkal, S
Talluri, K
Item 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.
Issue Date: 1-May-2019
Date of Acceptance: 22-Jan-2019
URI: http://hdl.handle.net/10044/1/67217
DOI: https://doi.org/10.1007/s10589-019-00068-y
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.
Keywords: Science & Technology
Physical Sciences
Operations Research & Management Science
Mathematics, Applied
Dynamic programming approximations
Revenue management
Choice models
Operations Research
0102 Applied Mathematics
0103 Numerical and Computational Mathematics
Publication Status: Published
Online Publication Date: 2019-03-22
Appears in Collections:Imperial College Business School

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commons