Imperial College London

Professor Kalyan Talluri

Business School

Munjal Chair in Global Business and Operations
 
 
 
//

Contact

 

kalyan.talluri Website CV

 
 
//

Location

 

387ABusiness School BuildingSouth Kensington Campus

//

Summary

 

Publications

Publication Type
Year
to

6 results found

Chen N, Li A, Talluri K, Reviews and Self-selection Bias with Operational Implications, Management Science, ISSN: 0025-1909

Journal article

Kunnumkal S, Talluri K, 2019, A strong lagrangian relaxation for general discrete-choice network revenue management, Computational Optimization and Applications, Vol: 73, Pages: 275-310, ISSN: 0926-6003

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.

Journal article

Kunnumkal S, Talluri KT, 2018, Choice network revenue management based on new tractable approximations, Transportation Science, Vol: 53, Pages: 1501-1799, ISSN: 0041-1655

The choice network revenue management model incorporates customer purchase behavioras probability of purchase as a function of the offered products, and is appropriate for air-line and hotel network revenue management, dynamic sales of bundles, and dynamic assort-ment optimization. The optimization problem is a stochastic dynamic program and is in-tractable. Consequently, a linear programming approximation called choice deterministic linearprogram (CDLP) is usually used to generate controls. Tighter approximations such as affineand piecewise-linear relaxations have been proposed, but it was not known if they can be solvedefficiently even for simple models such as the multinomial logit (MNL) model with a singlesegment. We first show that the affine relaxation (and hence the piecewise-linear relaxation) isNP-hard even for a single-segment MNL choice model. By analyzing the affine relaxation wederive a new linear programming approximation that admits a compact representation, implyingtractability, and prove that its value falls between theCDLPvalueandtheaffinerelaxationvalue. This is the firsttractablerelaxation for the choice network revenue management problemthat is provably tighter thanCDLP. This approximation in turn leads to new policies that,in our numerical experiments, show very good promise: a 2% increase in revenue on averageoverCDLP; and the values typically coming very close to the affine relaxation. We extendour analysis to obtain other tractable approximations that yield even tighter bounds. We alsogive extensions to the case with multiple customer segments with overlapping consideration setswhere choice by each segment is according to the MNL model.

Journal article

Strauss AK, Talluri K, 2017, Tractable consideration set structures for assortment optimization and network revenue management, Production and Operations Management, Vol: 26, Pages: 1359-1368, ISSN: 1059-1478

Discrete-choice models are widely used to model consumer purchase behavior in assortment optimization and revenue management. In many applications, each customer segment is associated with a consideration set that represents the set of products that customers in this segment consider for purchase. The firm has to make a decision on what assortment to offer at each point in time without the ability to identify the customer's segment. A linear program called the Choice-based Deterministic Linear Program (CDLP) has been proposed to determine these offer sets. Unfortunately, its size grows exponentially in the number of products and it is NP-hard to solve when the consideration sets of the segments overlap. The Segment-based Deterministic Concave Program with some additional consistency equalities (SDCP+) is an approximation of CDLP that provides an upper bound on CDLP's optimal objective value. SDCP+ can be solved in a fraction of the time required to solve CDLP and often achieves the same optimal objective value. This raises the question under what conditions can one guarantee equivalence of CDLP and SDCP+. In this study, we obtain a structural result to this end, namely that if the segment consideration sets overlap with a certain tree structure or if they are fully nested, CDLP can be equivalently replaced with SDCP+. We give a number of examples from the literature where this tree structure arises naturally in modeling customer behavior.

Journal article

Talluri KT, Kunnumkal S, 2016, A note on relaxations of the choice network revenue management dynamic program, Operations Research, Vol: 64, Pages: 158-166, ISSN: 1526-5463

In recent years, several approximation methods have been proposed for the choice network revenue management problem. These approximation methods are proposed because the dynamic programming formulation of the choice network revenue management problem is intractable even for moderately sized instances. In this paper, we consider three approximation methods that obtain upper bounds on the value function, namely, the choice deterministic linear program (CDLP), the affine approximation (AF), and the piecewise-linear approximation (PL). It is known that the piecewise-linear approximation bound is tighter than the affine bound, which in turn is tighter than CDLP. In this paper, we prove bounds on how much the affine and piecewise-linear approximations can tighten CDLP. We show (i) the gap between the AF and CDLP bounds is at most a factor of 1+1/(mini{r1i}), where r1i>0 are the resource capacities, and (ii) the gap between the piecewise-linear and CDLP bounds is within a factor of 2. Moreover, we show that these gaps are essentially tight. Our results hold for any discrete-choice model and do not involve any asymptotic scaling. Our results are surprising because calculating the AF bound is NP-hard and CDLP is tractable for a single-segment multinomial logit model; our result implies that if a firm has all resource capacities of 100, the gap between the two bounds, however, is at most 1.01.

Journal article

Talluri KT, Kunnumkal S, 2016, On a piecewise-linear approximation for network revenue management, Mathematics of Operations Research, Vol: 41, Pages: 72-91, ISSN: 0364-765X

The network revenue management (RM) problem arises in airline, hotel, media, and other industries where the sale productsuse multiple resources. It can be formulated as a stochastic dynamic program, but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristics have been proposed to approximateits value function. In this paper we show that the piecewise-linear approximation to the network RM dynamic program istractable; specifically we show that the separation problem of the approximation can be solved as a relatively compact linearprogram. Moreover, the resulting compact formulation of the approximate dynamic program turns out to be exactly equivalentto the Lagrangian relaxation of the dynamic program, an earlier heuristic method proposed for the same problem. We performa numerical comparison of solving the problem by generating separating cuts or as our compact linear program. We discussextensions to versions of the network RM problem with overbooking as well as the difficulties of extending it to the choicemodel of network revenue RM.

Journal article

This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.

Request URL: http://wlsprd.imperial.ac.uk:80/respub/WEB-INF/jsp/search-html.jsp Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: respub-action=search.html&id=00823618&limit=30&person=true