The Experts below are selected from a list of 20622 Experts worldwide ranked by ideXlab platform
Sumit Kunnumkal - One of the best experts on this subject based on the ideXlab platform.
-
A strong Lagrangian relaxation for general discrete-choice Network Revenue management
Computational Optimization and Applications, 2019Co-Authors: Sumit Kunnumkal, Kalyan TalluriAbstract:Discrete-choice Network Revenue management (DC-NRM) captures both customer behavior and the resource-usage interaction of products, and is appropriate for airline and hotel Revenue management, dynamic sales of bundles in advertising, and dynamic assortment optimization in retail. The state-space of the DC-NRM stochastic dynamic program explodes and approximation methods such as the choice deterministic linear program, the affine, and the piecewise-linear approximations have been proposed to approximate it in practice. The affine relaxation (and thereby, its generalization, the piecewise-linear approximation) is intractable even for the simplest choice models such as the multinomial logit (MNL) choice model with a single segment. In this paper we propose a new Lagrangian relaxation method for DC-NRM based on an extended set of multipliers. An attractive feature of our method is that the number of constraints in our formulation scales linearly with the resource capacities. While the number of constraints in our formulation is an order of magnitude smaller that the piecewise-linear approximation (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 are small in size—a reasonable modeling tradeoff in many practical applications—our method is an indirect way to obtain the piecewise-linear approximation on large problems effectively. Our results 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 relaxation method can provide substantial improvements over existing benchmark methods, both in terms of tighter upper bounds, as well as Revenues from policies based on the relaxation.
-
Choice Network Revenue Management Based on New Tractable Approximations
Transportation Science, 2019Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract:The choice Network Revenue management model incorporates customer purchase behavior as probability of purchase as a function of the offered products and is appropriate for airline and hotel Network...
-
technical note a note on relaxations of the choice Network Revenue management dynamic program
Operations Research, 2016Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract: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{ri1}), where ri1>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 thes...
-
On a piecewise-linear approximation for Network Revenue management
Mathematics of Operations Research, 2016Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract:The Network Revenue management (RM) problem arises in airline, hotel, media, and other industries where the sale products use multiple resources. It can be formulated as a stochastic dynamic program, but the dynamic program is computationally intractable because of an exponentially large state space, and a number of heuristics have been proposed to approximate its value function. In this paper we show that the piecewise-linear approximation to the Network RM dynamic program is tractable; specifically we show that the separation problem of the approximation can be solved as a relatively compact linear program. Moreover, the resulting compact formulation of the approximate dynamic program turns out to be exactly equivalent to the Lagrangian relaxation of the dynamic program, an earlier heuristic method proposed for the same problem. We perform a numerical comparison of solving the problem by generating separating cuts or as our compact linear program. We discuss extensions to versions of the Network RM prob...
-
Technical Note—A Note on Relaxations of the Choice Network Revenue Management Dynamic Program
Operations Research, 2016Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract: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{ri1}), where ri1>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 thes...
Kalyan T Talluri - One of the best experts on this subject based on the ideXlab platform.
-
Choice Network Revenue Management Based on New Tractable Approximations
Transportation Science, 2019Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract:The choice Network Revenue management model incorporates customer purchase behavior as probability of purchase as a function of the offered products and is appropriate for airline and hotel Network...
-
technical note a note on relaxations of the choice Network Revenue management dynamic program
Operations Research, 2016Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract: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{ri1}), where ri1>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 thes...
-
On a piecewise-linear approximation for Network Revenue management
Mathematics of Operations Research, 2016Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract:The Network Revenue management (RM) problem arises in airline, hotel, media, and other industries where the sale products use multiple resources. It can be formulated as a stochastic dynamic program, but the dynamic program is computationally intractable because of an exponentially large state space, and a number of heuristics have been proposed to approximate its value function. In this paper we show that the piecewise-linear approximation to the Network RM dynamic program is tractable; specifically we show that the separation problem of the approximation can be solved as a relatively compact linear program. Moreover, the resulting compact formulation of the approximate dynamic program turns out to be exactly equivalent to the Lagrangian relaxation of the dynamic program, an earlier heuristic method proposed for the same problem. We perform a numerical comparison of solving the problem by generating separating cuts or as our compact linear program. We discuss extensions to versions of the Network RM prob...
-
Technical Note—A Note on Relaxations of the Choice Network Revenue Management Dynamic Program
Operations Research, 2016Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract: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{ri1}), where ri1>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 thes...
-
On the tractability of the piecewise-linear approximation for general discrete-choice Network Revenue management
2014Co-Authors: Sumit Kunnumkal, Kalyan T TalluriAbstract: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 independent-class (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 piecewise-linear 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.
Huseyin Topaloglu - One of the best experts on this subject based on the ideXlab platform.
-
Network Revenue Management with Dependent Demands
International Series in Operations Research & Management Science, 2019Co-Authors: Guillermo Gallego, Huseyin TopalogluAbstract:Network Revenue management models have traditionally been developed under the independent demand assumption. In the independent demand setting, customers arrive into the system with the intention to purchase a particular product. If this product is available, they purchase it. Otherwise, they leave the system. This model is reasonable when products are well differentiated so that customers do not substitute between products. The independent demand model is harder to justify when there are few differences, other than price, between fares. Indeed, a more general setting is needed when the demand for each product depends heavily on whether or not other products are available for sale. This setting gives the firms the opportunity to shape the demand for each product by adjusting the offer set made available to the customer.
-
On the Approximate Linear Programming Approach for Network Revenue Management Problems
INFORMS Journal on Computing, 2014Co-Authors: Chaoxu Tong, Huseyin TopalogluAbstract:One method to obtain high-quality bid prices for Network Revenue management problems involves using the approximate linear programming approach on the dynamic programming formulation of the problem. This approach ends up with a linear program whose number of constraints increases exponentially with the number of flight legs in the airline Network. The linear program is solved using constraint generation, where each constraint can be generated by solving a separate integer program. The necessity to solve integer programs and the slow convergence behavior of constraint generation are generally recognized as drawbacks of this approach. In this paper, we show how to effectively eliminate these drawbacks. In particular, we establish that constraint generation can actually be carried out by solving minimum-cost Network flow problems with natural integer solutions. Furthermore, using the structure of minimum-cost Network flow problems, we a priori reduce the number of constraints in the linear program from expon...
-
A Randomized Linear Programming Method for Network Revenue Management with Product-Specific No-Shows
Transportation Science, 2012Co-Authors: Sumit Kunnumkal, Kalyan T Talluri, Huseyin TopalogluAbstract:Revenue management practices often include overbooking capacity to account for customers who make reservations but do not show up. In this paper, we consider the Network Revenue management problem with no-shows and overbooking, where the show-up probabilities are specific to each product. No-show rates differ significantly by product (for instance, each itinerary and fare combination for an airline) as sale restrictions and the demand characteristics vary by product. However, models that consider no-show rates by each individual product are difficult to handle because the state-space in dynamic programming formulations (or the variable space in approximations) increases significantly. In this paper, we propose a randomized linear program to jointly make the capacity control and overbooking decisions with product-specific no-shows. We establish that our formulation gives an upper bound on the optimal expected total profit, and our upper bound is tighter than a deterministic linear programming upper bound that appears in the existing literature. Furthermore, we show that our upper bound is asymptotically tight in a regime where the leg capacities and the expected demand is scaled linearly with the same rate. We also describe how the randomized linear program can be used to obtain a bid price control policy. Computational experiments indicate that our approach is quite fast, is able to scale to industrial problems, and can provide significant improvements over standard benchmarks.
-
A stochastic approximation algorithm for making pricing decisions in Network Revenue management problems
Journal of Revenue and Pricing Management, 2010Co-Authors: Sumit Kunnumkal, Huseyin TopalogluAbstract:In this article, we develop a stochastic approximation algorithm (SAA) for making pricing decisions in Network Revenue management problems. In the setting we consider, the probability of observing a request for an itinerary depends on the price for the itinerary. We are interested in finding a set of prices that maximize the total expected Revenue. Our approach is based on visualizing the total expected Revenue as a function of the prices and using the stochastic gradients of the total Revenue to search for a good set of prices. To compute the stochastic gradients of the total Revenue, we use a construction that decouples the prices for the itineraries from the probability distributions of the itinerary requests. This construction ensures that the probability distributions of the underlying random variables do not change when we change the prices for the itineraries. We establish the convergence of our SAA. Computational experiments indicate that the prices obtained by our SAA perform significantly better than those obtained by standard benchmark strategies, especially when the leg capacities are tight and there are large differences between the price sensitivities of the different market segments.
-
Network Revenue management with product-specific no-shows
2010Co-Authors: Sumit Kunnumkal, Kalyan T Talluri, Huseyin TopalogluAbstract:Revenue management practices often include overbooking capacity to account for customerswho make reservations but do not show up. In this paper, we consider the Network Revenuemanagement problem with no-shows and overbooking, where the show-up probabilities are specificto each product. No-show rates differ significantly by product (for instance, each itinerary andfare combination for an airline) as sale restrictions and the demand characteristics vary byproduct. However, models that consider no-show rates by each individual product are difficultto handle as the state-space in dynamic programming formulations (or the variable space inapproximations) increases significantly. In this paper, we propose a randomized linear program tojointly make the capacity control and overbooking decisions with product-specific no-shows. Weestablish that our formulation gives an upper bound on the optimal expected total profit andour upper bound is tighter than a deterministic linear programming upper bound that appearsin the existing literature. Furthermore, we show that our upper bound is asymptotically tightin a regime where the leg capacities and the expected demand is scaled linearly with the samerate. We also describe how the randomized linear program can be used to obtain a bid price controlpolicy. Computational experiments indicate that our approach is quite fast, able to scale to industrialproblems and can provide significant improvements over standard benchmarks.
Gustavo Vulcano - One of the best experts on this subject based on the ideXlab platform.
-
a column generation algorithm for choice based Network Revenue management
Operations Research, 2009Co-Authors: Juan Jose Miranda Bront, Isabel Mendezdiaz, Gustavo VulcanoAbstract:During the past few years, there has been a trend to enrich traditional Revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based, deterministic, linear programming model (CDLP) of Gallego et al. (2004) [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a Network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York], and the follow-up dynamic programming decomposition heuristic of van Ryzin and Liu (2008) [van Ryzin, G. J., Q. Liu. 2008. On the choice-based linear programming model for Network Revenue management. Manufacturing Service Oper. Management10(2) 288--310]. We focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size Networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-hard and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective and that the overall approach leads to high-quality, practical solutions.
-
computing virtual nesting controls for Network Revenue management under customer choice behavior
Manufacturing & Service Operations Management, 2008Co-Authors: Garrett Van Ryzin, Gustavo VulcanoAbstract:We consider a Revenue management, Network capacity control problem in a setting where heterogeneous customers choose among the various products offered by a firm (e.g., different flight times, fare classes, and/or routings). Customers may therefore substitute if their preferred products are not offered. These individual customer choice decisions are modeled as a very general stochastic sequence of customers, each of whom has an ordered list of preferences. Minimal assumptions are made about the statistical properties of this demand sequence. We assume that the firm controls the availability of products using a virtual nesting control strategy and would like to optimize the protection levels for its virtual classes accounting for the (potentially quite complex) choice behavior of its customers. We formulate a continuous demand and capacity approximation for this problem, which allows for the partial acceptance of requests for products. The model admits an efficient calculation of the sample path gradient of the Network Revenue function. This gradient is then used to construct a stochastic steepest ascent algorithm. We show the algorithm converges in probability to a stationary point of the expected Revenue function under mild conditions. The algorithm is relatively efficient even on large Network problems, and in our simulation experiments it produces significant Revenue increases relative to traditional virtual nesting methods. On a large-scale, real-world airline example using choice behavior models fit to actual booking data, the method produced an estimated 10% improvement in Revenue relative to the controls used by the airline. The examples also provide interesting insights into how protection levels should be adjusted to account for choice behavior. Overall, the results indicate that choice behavior has a significant impact on both capacity control decisions and Revenue performance and that our method is a viable approach for addressing the problem.
-
Simulation-Based Optimization of Virtual Nesting Controls for Network Revenue Management
Operations Research, 2008Co-Authors: Garrett Van Ryzin, Gustavo VulcanoAbstract:Virtual nesting is a popular capacity control strategy in Network Revenue management. In virtual nesting, products (itinerary-fare-class combinations) are mapped (“indexed”) into a relatively small number of “virtual classes” on each resource (flight leg) of the Network. Nested protection levels are then used to control the availability of these virtual classes; specifically, a product request is accepted if and only if its corresponding virtual class is available on each resource required. Bertsimas and de Boer proposed an innovative simulation-based optimization method for computing protection levels in a virtual nesting control scheme [Bertsimas, D., S. de Boer. 2005. Simulation-based booking-limits for airline Revenue management. Oper. Res.53 90--106]. In contrast to traditional heuristic methods, this simulation approach captures the true Network Revenues generated by virtual nesting controls. However, because it is based on a discrete model of capacity and demand, the method has both computational and theoretical limitations. In particular, it uses first-difference estimates, which are computationally complex to calculate exactly. These gradient estimates are then used in a steepest-ascent-type algorithm, which, for discrete problems, has no guarantee of convergence. In this paper, we analyze a continuous model of the problem that retains most of the desirable features of the Bertsimas-de Boer method, yet avoids many of its pitfalls. Because our model is continuous, we are able to compute gradients exactly using a simple and efficient recursion. Indeed, our gradient estimates are often an order of magnitude faster to compute than first-difference estimates, which is an important practical feature given that simulation-based optimization is computationally intensive. In addition, because our model results in a smooth optimization problem, we are able to prove that stochastic gradient methods are at least locally convergent. On several test problems using realistic Networks, the method is fast and produces significant performance improvements relative to the protection levels produced by heuristic virtual nesting schemes. These results suggest it has good practical potential.
He Wang - One of the best experts on this subject based on the ideXlab platform.
-
a re solving heuristic with uniformly bounded loss for Network Revenue management
Management Science, 2020Co-Authors: Pornpawee Bumpensanti, He WangAbstract:We consider a canonical quantity-based Network Revenue management problem where a firm accepts or rejects incoming customer requests irrevocably in order to maximize expected Revenue given limited ...
-
a re solving heuristic with uniformly bounded loss for Network Revenue management
arXiv: Optimization and Control, 2018Co-Authors: Pornpawee Bumpensanti, He WangAbstract:We consider the canonical (quantity-based) Network Revenue management problem, where a firm accepts or rejects incoming customer requests irrevocably in order to maximize expected Revenue given limited resources. Due to the curse of dimensionality, the exact solution to this problem by dynamic programming is intractable when the number of resources is large. We study a family of re-solving heuristics that periodically re-optimize an approximation to the original problem known as the deterministic linear program (DLP), where random customer arrivals are replaced by their expectations. We find that, in general, frequently re-solving the DLP produces the same order of Revenue loss as one would get without re-solving, which scales as the square root of the time horizon length and resource capacities. By re-solving the DLP at a few selected points in time and applying thresholds to the customer acceptance probabilities, we design a new re-solving heuristic whose Revenue loss is uniformly bounded by a constant that is independent of the time horizon and resource capacities.
-
Network Revenue Management under a Spiked Multinomial Logit Choice Model
SSRN Electronic Journal, 2018Co-Authors: Yufeng Cao, Anton J. Kleywegt, He WangAbstract:Airline data have shown that the fraction of customers who choose the cheapest available fare class often is much greater than that predicted by the multinomial logit (MNL) choice model calibrated with the data. For example, the fraction of customers who choose the cheapest available fare class is much greater than the fraction of customers who choose the next cheapest available one, even if the price difference is small. To model this spike in demand for the cheapest available fare class, scholars proposed a choice model called the spiked multinomial logit (spiked-MNL) model. We study a Network Revenue management problem under the spiked-MNL choice model. We show that efficient sets, i.e., assortments that offer a Pareto-optimal trade-off between Revenue and resource usage, are nested by Revenue. We use this structural result to show how a deterministic approximation of the stochastic dynamic program can be solved efficiently by solving a small linear program. We use the solution of the small linear program to construct a booking limit policy and prove that the policy is asymptotically optimal. This is the first such result for a booking limit policy under a choice model, and our proof uses an approach that is different from those used for previous asymptotic optimality results. Finally, we evaluate different assortment policies in numerical experiments using both synthetic and airline data.
-
Online Network Revenue Management Using Thompson Sampling
Operations Research, 2018Co-Authors: Kris Johnson Ferreira, David Simchi-levi, He WangAbstract:Thompson sampling is a randomized Bayesian machine learning method, whose original motivation was to sequentially evaluate treatments in clinical trials. In recent years, this method has drawn wide...
-
Online Network Revenue Management Using Thompson Sampling
SSRN Electronic Journal, 2015Co-Authors: Kris Johnson Ferreira, David Simchi-levi, He WangAbstract:We consider a Network Revenue management problem where an online retailer aims to maximize Revenue from multiple products with limited inventory constraints. As common in practice, the retailer does not know the consumer's purchase probability at each price and must learn the mean demand from sales data. We propose an efficient and effective dynamic pricing algorithm, which builds upon the Thompson sampling algorithm used for multi-armed bandit problems by incorporating inventory constraints into the model and algorithm. Our algorithm proves to have both strong theoretical performance guarantees as well as promising numerical performance results when compared to other algorithms developed for the same setting. More broadly, our paper contributes to the literature on the multi-armed bandit problem with resource constraints, since our algorithm applies directly to this setting when the inventory constraint is interpreted as general resource constraints.