Robust Control of the Multi-armed Bandit Problem. F. Caro, A. Das Gupta. December 2012.
We study a robust model of the multi-armed bandit (MAB) problem in which the transition probabilities are ambiguous and belong to subsets of the probability simplex. We characterize the optimal policy as a project-by-project retirement policy but we show that arms become dependent so the Gittins index is not optimal. We propose a Lagrangian index policy that is computationally equivalent to evaluating the indices of a non-robust MAB. For a project selection problem we find that it performs near optimal.
The Assortment Packing Problem: Multiperiod Assortment Planning for Short-Lived Products. F. Caro, V. Martínez-de-Albéniz, P. Rusmevichientong. December 2012.
Motivated by retailers' frequent introduction of new items to refresh product lines and maintain their market shares, we present the assortment packing problem in which a firm must decide, in advance, the release date of each product in a given collection over a selling season. Our formulation models the trade-offs among profit margins, preference weights, and limited life cycles. A key aspect of the problem is that each product is short-lived in the sense that, once introduced, its attractiveness lasts only a few periods and vanishes over time. The objective is to determine when to introduce each product to maximize the total profit over the selling season. Even for two periods, the corresponding optimization problem is shown to be NP-complete. As a result, we study a continuous relaxation of the problem that approximates the problem well, when the number of products is large. When margins are identical and product preferences decay exponentially, its solution can be characterized: it is optimal to introduce products with slower decays earlier. The structural properties of the relaxation also help us to develop several heuristics, for which we establish performance guarantees. We test our heuristics with data on sales and release dates of woman handbags from an accessories retailer. The numerical experiments show that the heuristics perform very well and can yield significant improvements in profitability.
Double-Counting in Supply Chain Carbon Footprinting. F. Caro, C.J. Corbett, T. Tan, R. Zuidwijk. December 2012.
Carbon footprinting is a tool for firms to determine the total greenhouse gas (GHG) emissions associated with their supply chain or with a unit of final product or service. Carbon footprinting typically aims to identify where best to invest in emission reduction efforts, and/or to determine the proportion of total emissions that an individual firm is accountable for, whether financially and/or operationally. A major and under-recognized challenge in determining the appropriate allocation stems from the high degree to which GHG emissions are the result of joint efforts by multiple firms. We introduce a simple but general model of joint production of GHG emissions in general supply chains, decomposing the total footprint into processes, each of which can be influenced by any combination of firms. We analyze two main scenarios. In the first, the social planner allocates emissions to individual firms and charges them a carbon tax for the emissions allocated to them. In the second, a carbon leader voluntarily agrees to offset all emissions in the entire supply chain and then contracts with individual firms to recoup (part of) the costs of those offsets. In both cases, we find that, in order to induce the optimal effort levels, the emissions need to be over-allocated, in contrast to the usual focus in the life cycle assessment (LCA) and carbon footprinting literatures on avoiding double-counting. Our work aims to lay the foundation for a framework to integrate the economics- and LCA-based perspectives on supply chain carbon footprinting.
Clearance Pricing Optimization for a Fast-Fashion Retailer. F. Caro, J. Gallien. Operations Research. 60(6): 1404-1422. November-December 2012.
Fast-fashion retailers such as Zara offer continuously changing assortments and use minimal in-season promotions. Their clearance pricing problem is thus challenging because it involves comparatively more different articles of unsold inventory with less historical price data points. Until 2007, Zara used a manual and informal decision-making process for determining price markdowns. In collaboration with their pricing team, we designed and implemented since an alternative process relying on a formal forecasting model feeding a price optimization model. As part of a controlled field experiment conducted in all Belgian and Irish stores during the 2008 Fall-Winter season, this new process increased clearance revenues by approximately 6%. Zara is currently using this process worldwide for its markdown decisions during clearance sales.
Product and Price Competition with Satiation Effects. F. Caro, V. Martínez-de-Albéniz. Management Science. 58(7): 1357-1373. July 2012.
Consumers become satiated with a product when purchasing too much, too quickly. How much is too much, and how quick is too quick depends on the characteristics of the product relative to the time interval between consumption periods. Knowing that, consumers allocate their budget to products that generate less satiation effects. Retailers should then choose to sell products that induce minimal satiation, but usually this is operationally more costly. To study this trade-off, we provide an analytical model based on utility theory that relates customer consumption to price and satiation, in the context of multiple competing retailers. We determine the purchasing pattern over time and provide an explicit expression to determine the consumption level in steady state. We derive market shares and show that they take the form of an attraction model in which the attractiveness depends on price and product satiation. We use this to analyze the competition between firms that maximize long-term average profit. We characterize the equilibrium under three scenarios: (i) price-only competition, (ii) product-only competition, and (iii) price and product competition. The results reveal the interplay between a key marketing lever (price) and the firm's ability to offer products that generate less satiation. In particular, we show that when a firm becomes more efficient at reducing satiation, its competitor may benefit if competition is on product only, but not if it is on price and product. We also find that when satiation effects are not managed, a firm's profit may be significantly reduced while a strategic competitor can largely benefit.
Optimizing Long‐Term Production Plans in Underground and Open Pit Copper Mines. R. Epstein, M. Goic, A. Weintraub, J. Catalán, P. Santibáñez, R. Urrutia, R. Cancino, S. Gaete, A. Aguayo, F. Caro. Operations Research. 60(1): 4-17. January-February 2012.
We present a methodology for long-term mine planning based on a general capacitated multi-commodity network flow formulation. It considers underground and open pit ore deposits sharing multiple downstream processing plants over a long horizon. The purpose of the model is to optimize several mines in an integrated fashion, but real size instances are hard to solve due to the combinatorial nature of the problem. We tackle this by solving the relaxation of a tight linear formulation and we round the resulting near-integer solution with a customized procedure. The model has been implemented at Codelco, the largest copper producer in the world. Since 2001, the system is used on a regular basis and has increased the net present value (NPV) of the production plan for a single mine by 5%. Moreover, integrating multiple mines provided an additional increase of 3%. The system has allowed planners to evaluate more scenarios. In particular, the model was used to study the option of delaying by four years the conversion of Chiquicamata, Codelco's largest open pit mine, to underground operations.
Zara Uses Operations Research to Reengineer Its Global Distribution Process. F. Caro, J. Gallien, M. Díaz, J. García, J-M. Corredoira, M. Montes, J-A. Ramos, J. Correa. Interfaces. 40(1): 71-84. January–February 2010.
Overcoming significant technical and human difficulties, Zara recently deployed a new process that relies extensively on sophisticated operations research models to determine each inventory shipment it sends from its two central warehouses to its 1,500 stores worldwide. By taking a retail size-assortment view of a store’s inventory, the model incorporates the link between stock levels and demand to select store replenishment quantities. Through a rigorous, controlled field experiment, we estimate that this new process has increased sales by 3–4 percent; this corresponds to estimated profits of approximately $233 million and $353 million in additional revenues for 2007 and 2008, respectively.
Indexability of Bandit Problems With Response Delays. F. Caro, O.S. Yoo. Probability in the Engineering and Informational Sciences. 24(3): 349-374. July 2010.
This article considers an important class of discrete time restless bandits, given by the discounted multiarmed bandit problems with response delays. The delays in each period are independent random variables, in which the delayed responses do not cross over. For a bandit arm in this class, we use a coupling argument to show that in each state there is a unique subsidy that equates the pulling and nonpulling actions (i.e., the bandit satisfies the indexibility criterion introduced by Whittle (1988). The result allows for infinite or finite horizon and holds for arbitrary delay lengths and infinite state spaces. We compute the resulting marginal productivity indexes (MPI) for the Beta-Bernoulli Bayesian learning model, formulate and compute a tractable upper bound, and compare the suboptimality gap of the MPI policy to those of other heuristics derived from different closed-form indexes. The MPI policy performs near optimally and provides a theoretical justification for the use of the other heuristics.
The Effect of Assortment Rotation on Consumer Choice and Its Impact on Competition. F. Caro, V. Martínez-de-Albéniz. Consumer-Driven Demand and Operations Management Models. S. Netessine, C.S. Tang (eds.). Springer US. 2009.
The recent success of fast fashion retailers has changed the (affordable) fashion industry dramatically. These companies, such as Zara, are characterized by a flexible supply chain that has allowed them to reduce design and production lead times to just a few weeks, rather than months. More importantly, they are using these capabilities to change the assortment (i.e., introduce new products) more frequently, which many practitioners claim increases sales, since there is evidence showing that customers visit more often the stores with fresher products. We propose in this chapter a customer consumption model with satiation and multiple competing retailers. The model implies that the consumers will spend a higher share of their budget in retailers that renovate the assortment at a faster pace. Using the insights from the model, we determine how often retailers should change the assortment in the competitive equilibrium.
Process Location and Product Distribution with Uncertain Yields. F. Caro, K. Rajaram, J. Wollenweber. Operations Research. 60(5): 1050-1063. September-October 2012.
We present a framework to analyze the process location and product distribution problem with uncertain yields for a large multinational food processing company. This problem consists of selecting the location of processes, the assignment of products, and the distribution of production quantities to markets in order to minimize total expected costs. It differs from the traditional facility location problem due to characteristics that are inherent to process industry sectors. These include significant economies of scale at high volumes, large switchover times, and production yield uncertainty. We model the problem as a nonlinear mixed-integer program. A challenging aspect of this problem is that the objective function is neither convex nor concave. We develop an exact approach to linearize the objective function. We present heuristics to solve the problem and also construct lower bounds based on a reduction of the constraint set to evaluate the quality of the solutions. This framework has been used to make process choice and product allocation decisions at the food processing company, and the estimated annual cost savings are around 10%, or $50 million. In addition, the insights from the model have had a significant strategic and organizational impact at this company. Our framework and conclusions are relevant to other industrial sectors with similar characteristics, such as pharmaceuticals and specialty chemical manufacturers.
The Impact of Quick Response in Inventory-Based Competition. F. Caro, V. Martínez-de-Albéniz. Manufacturing & Service Operations Management. 12(3): 409-429. Summer 2010.
We propose an extension of the competitive newsvendor model to investigate the impact of quick response under competition. For this purpose, we consider two retailers that compete in terms of inventory: customers that face a stockout at their first-choice store will look for the product at the other store. Consequently, the total demand that each retailer faces depends on the competitor's inventory level. We allow for asymmetric reordering capabilities, and we are particularly interested in the case when one of the firms has a lower ordering cost but can only produce at the beginning of the selling season, whereas the second firm has higher costs but can replenish stock in a quick response manner, taking advantage of any incremental knowledge about demand (if it is available). We visualize this problem as the competition between a traditional make-to-stock retailer that builds up inventory before the season starts versus a retailer with a responsive supply chain that can react to early demand information. We provide conditions for this game to have a unique pure-strategy subgame-perfect equilibrium, which then allows us to perform numerical comparative statics. We confirm that quick response is more beneficial when demand uncertainty is higher or exhibits a higher correlation over time. We also find that the competitive advantage from quick response is larger when facing a slow response competitor, and interestingly, asymmetric competition can be desirable to both competitors.
Inventory Management of a Fast-Fashion Retail Network. F. Caro, J. Gallien. Operations Research. 58(2): 257-273. March-April 2010.
Working in collaboration with Spain-based retailer Zara, we address the problem of distributing, over time, a limited amount of inventory across all the stores in a fast-fashion retail network. Challenges specific to that environment include very short product life cycles, and store policies whereby an article is removed from display whenever one of its key sizes stocks out. To solve this problem, we first formulate and analyze a stochastic model predicting the sales of an article in a single store during a replenishment period as a function of demand forecasts, the inventory of each size initially available, and the store inventory management policy just stated. We then formulate a mixed-integer program embedding a piecewise-linear approximation of the first model applied to every store in the network, allowing us to compute store shipment quantities maximizing overall predicted sales, subject to inventory availability and other constraints. We report the implementation of this optimization model by Zara to support its inventory distribution process, and the ensuing controlled pilot experiment performed to assess the model’s impact relative to the prior procedure used to determine weekly shipment quantities. The results of that experiment suggest that the new allocation process increases sales by 3% to 4%, which is equivalent to $275 M in additional revenues for 2007, reduces transshipments, and increases the proportion of time that Zara’s products spend on display within their life cycle. Zara is currently using this process for all of its products worldwide.
Dynamic Assortment with Demand Learning for Seasonal Consumer Goods. F. Caro, J. Gallien. Management Science. 53(2): 276-292. February 2007.
Companies such as Zara and World Co. have recently implemented novel product development processes and supply chain architectures enabling them to make more product design and assortment decisions during the selling season, when actual demand information becomes available. How should such retail firms modify their product assortment over time in order to maximize overall profits for a given selling season? Focusing on a stylized version of this problem, we study a finite horizon multiarmed bandit model with several plays per stage and Bayesian learning. Our analysis involves the Lagrangian relaxation of weakly coupled dynamic programs (DPs), results contributing to the emerging theory of DP duality, and various approximations. It yields a closed-form dynamic index policy capturing the key exploration versus exploitation trade-off and associated suboptimality bounds. In numerical experiments its performance proves comparable to that of other closed-form heuristics described in the literature, but this policy is particularly easy to implement and interpret. This last feature enables extensions to more realistic versions of the motivating dynamic assortment problem that include implementation delays, switching costs, and demand substitution effects.
Optimal Static Pricing for a Tree Network. F. Caro, D. Simchi-Levi. Annals of Operations Research. 196(1): 137-152. July 2012.
We study the static pricing problem for a network service provider in a loss system with a tree structure. In the network, multiple classes share a common inbound link and then have dedicated outbound links. The motivation is from a company that sells phone cards and needs to price calls to different destinations. We characterize the optimal static prices in order to maximize the steady-state revenue. We report new structural findings as well as alternative proofs for some known results. We compare the optimal static prices versus prices that are asymptotically optimal, and through a set of illustrative numerical examples we show that in certain cases the loss in revenue can be significant. Finally, we show that static prices obtained using the reduced load approximation of the blocking probabilities can be easily obtained and have near-optimal performance, which makes them more attractive for applications.
Dynamic Assortment with Demand Learning for Short Life-Cycle Consumer Goods. F. Caro, J. Gallien. Manufacturing and Service Operations Management. 7(1): 94-97. Winter 2005. (Extended Abstracts Winners MSOM Student Paper Competition)
How should a retail firm modify its product assortment over time in order to maximize overall profits for a given selling season? We focus on this question in the context of "fast-fashion" companies (such as Zara and World Co.) with novel product development processes and supply chain architectures allowing them to make many more product design and assortment decisions during the selling season, when actual demand information becomes available. We formulate this problem as a dynamic optimization model under a number of assumptions that do not reduce its applicability. The model is equivalent to a version of the multiarmed bandit problem with finite horizon and several plays per stage. Our analysis involves the Lagrangian relaxation of weakly coupled dynamic programs; it yields a closed form near optimal index policy capturing the key exploration vs. exploitation trade-off, and associated suboptimality bounds. Numerical results show that the suggested index policy outperforms the associated greedy assortment policy with passive learning. We conclude that our policy with active learning is both, easily implementable in practice, and can yield a substantial profit increase in scenarios with little prior information.
School Redistricting: Embedding GIS Tools With Integer Programming. F. Caro, T. Shirabe, M. Guignard, A. Weintraub. The Journal of the Operational Research Society. 55(8): 836-850. April 2004.
The paper deals with a school redistricting problem in which blocks of a city must be assigned to schools according to diverse criteria. Previous approaches are reviewed and some desired properties of a good school districting plan are established. An optimization model together with a geographic information system (GIS) environment are then proposed for finding a solution that satisfies these properties. A prototype of the system is described, some implementation issues are discussed, and two real-life examples from the city of Philadelphia are studied, one corresponding to a relatively easy to solve problem, and the other, to a much harder one. The trade-offs in the solutions are analyzed and feasibility questions are discussed. The results of the study strongly suggest that ill-defined spatial problems, such as school redistricting, can be addressed effectively by an interaction between objective analysis and subjective judgment.
Evaluating the Economic Cost of Environmental Measures in Plantation Harvesting Through the Use of Mathematical Models. F. Caro, R. Andalaft, X. Silva, A. Weintraub, P. Sapunar, M. Cabello. Production & Operations Management. 12(3): 290-306. Fall 2003.
An important issue being discussed for Chilean pine plantation policies is the application of environmental protection measures when managing its timber areas. Typical measures, already in place in more developed countries, include imposing riparian strips and protecting fragile soils from the use of heavy machinery. While environmental protection measures have been considered vital for decades, so far there has been almost no attempt to quantify both the benefits and costs of these measures. This paper attempts to measure the costs associated to with the main measures. The importance of this analysis is to help both the forestry firms and the government evaluate,, the cost impact of the new environmental protection regulations being studied. To support this analysis we consider a mixed integer LP model currently used for tactical planning to evaluate the impact of the environmental constraints under study in terms of loss in net revenues and timber production. The analysis is carried out by modifying the model by changing its coefficients, and adding further constraints which represent the effect of these environmental measures. This allows quantifying the effect of environmental measures under different scenarios for one specific forest firm. This approach can be easily extended to other firms and countries. In addition, the modified model will allow a firm to plan harvesting when specific environmental regulations are in place.
A 2-Opt Tabu Search Procedure for the Multi-Period Forest Harvesting Problem with Adjacency, Green-up, Old Growth and Even Flow Constraints. F. Caro, M. Constantino, I. Martins, A. Weintraub. Forest Science. 49(5): 738-751. October 2003.
Due to environmental concerns, modern forest harvesting plans are being modified to address aesthetics and wildlife protection issues. In the literature, the most referenced are adjacency constraints with exclusion or “green-up” years. Also of interest are the concepts of old growth patch size and total old growth area restrictions. Typically, harvest blocks have been defined a priori. Recently, some have proposed a more complex approach in which basic cells are defined and the decision-making process includes forming harvest blocks from these cells. This has been called ARM (Area Restriction Model). Until now, no successful exact method has been reported for large-scale ARM problems, leaving heuristics as a viable option. In this work we present a multi-period harvest-scheduling ARM model with these spatial constraints. A tabu search procedure with 2-Opt moves (exchanging at most 2 units) was developed. For small size instances, the procedure found the optimal solution in most cases, and for a real-size problem an 8% optimality gap is provided.