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

File Description SizeFormat 
COAP-D-17-00325_R2.pdfFile embargoed for 12 months after publication date 631.29 kBAdobe PDF    Request a copy
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.
Date of Acceptance: 22-Jan-2019
URI: http://hdl.handle.net/10044/1/67217
ISSN: 0926-6003
Publisher: Springer (part of Springer Nature)
Journal / Book Title: Computational Optimization and Applications
Keywords: 0102 Applied Mathematics
0103 Numerical And Computational Mathematics
Operations Research
Publication Status: Accepted
Appears in Collections:Imperial College Business School

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

Creative Commonsx