Transcription
Online Linear Optimization with Inventory ManagementConstraintsLIN YANG , The Chinese University of Hong Kong, ChinaMOHAMMAD H. HAJIESMAILI , University of Massachusetts Amherst, USARAMESH SITARAMAN, University of Massachusetts Amherst, USAADAM WIERMAN, California Institute of Technology, USAENRIQUE MALLADA, Johns Hopkins University, USAWING S. WONG, The Chinese University of Hong Kong, ChinaThis paper considers the problem of online linear optimization with inventory management constraints.Specifically, we consider an online scenario where a decision maker needs to satisfy her time-varying demandfor some units of an asset, either from a market with a time-varying price or from her own inventory. Ineach time slot, the decision maker is presented a (linear) price and must immediately decide the amount topurchase for covering the demand and/or for storing in the inventory for future use. The inventory has alimited capacity and can be used to buy and store assets at low price and cover the demand when the price ishigh. The ultimate goal of the decision maker is to cover the demand at each time slot while minimizing thecost of buying assets from the market. We propose ARP, an online algorithm for linear programming withinventory constraints, and ARPRate, an extended version that handles rate constraints to/from the inventory.Both ARP and ARPRate achieve optimal competitive ratios, meaning that no other online algorithm can achievea better theoretical guarantee. To illustrate the results, we use the proposed algorithms in a case study focusedon energy procurement and storage management strategies for data centers.CCS Concepts: Theory of computation Online algorithms; Linear programming; Hardware Energy generation and storage; Power estimation and optimization.Additional Key Words and Phrases: Online linear optimization; inventory management; competitive onlinealgorithms; energy procurement; data centerACM Reference Format:Lin Yang, Mohammad H. Hajiesmaili, Ramesh Sitaraman, Adam Wierman, Enrique Mallada, and Wing S.Wong. 2020. Online Linear Optimization with Inventory Management Constraints. Proc. ACM Meas. Anal.Comput. Syst. 4, 1, Article 16 (March 2020), 29 pages. https://doi.org/10.1145/3379482 Bothauthors contributed equally to this research.Authors’ addresses: Lin Yang, The Chinese University of Hong Kong, China, Hong Kong, linyang@cs.umass.edu; MohammadH. Hajiesmaili, hajiesmaili@cs.umass.edu, University of Massachusetts Amherst, USA, 140 Governors Dr. Amherst, MA,01002; Ramesh Sitaraman, University of Massachusetts Amherst, USA, 140 Governors Dr. Amherst, MA, 01002, ramesh@cs.umass.edu; Adam Wierman, California Institute of Technology, USA, 1200 E. California Blvd. Pasadena, CA, 91125, adamw@caltech.edu; Enrique Mallada, Johns Hopkins University, USA, 3400 N Charles St, Baltimore, MD, 21218, mallada@jhu.edu;Wing S. Wong, The Chinese University of Hong Kong, China, Hong Kong, wswong@ie.cuhk.edu.hk.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without feeprovided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice andthe full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requiresprior specific permission and/or a fee. Request permissions from permissions@acm.org. 2020 Association for Computing Machinery.2476-1249/2020/3-ART16 15.00https://doi.org/10.1145/3379482Proc. ACM Meas. Anal. Comput. Syst., Vol. 4, No. 1, Article 16. Publication date: March 2020.16
16:21Lin Yang et al.INTRODUCTIONOnline optimization and decision making under uncertainty are classical topics that have beenstudied in a broad set of applications using a wide range of theoretical tools. On the theoreticalside, the topic has been approached from the perspective of online algorithms using competitiveanalysis [17], online learning with the regret as the performance metric [37, 58], and reinforcementlearning with different modeling techniques such as Markov Decision Processes (MDPs) [51]. Onthe application side, recent scenarios where theoretical results have had an impact for real-worlddesign include data center optimization [10, 11, 41, 50, 53], energy systems [12, 34, 35, 40, 61, 65],cloud management [44, 62], and computer and communication networks [28, 36].This paper studies a variation of the classical online optimization formulation: online linearoptimization with inventory management constraints (OLIM). In this problem, in each slot, a decisionmaker should satisfy a demand of d(t) 0 units of an asset arriving online. The demand shouldbe satisfied either from a market with time-varying price or from her own inventory with a finitecapacity of B. In slot t, the decision maker is presented an online price p(t) 0, and must decidethe amount to procure from the market, x(t) 0, which can be used to cover the demand d(t) orto store in the inventory for future use. The goal of the decision maker is to cover the demandover the time horizon while minimizing the cost of buying from the market through the use of theinventory.While online linear optimization has been studied for decades [13, 23, 39, 48], progress ononline linear optimization with inventory constraints has only begun to occur in recent years,e.g., [21, 22, 42], with most work focusing on special cases. The reason is that inventory managementconstraints couple the decision of the online agent across rounds in an unavoidable way. So, withoutknowledge of future prices and demands, it is challenging to design online algorithms with provableworst-case guarantees.OLIM is of particular interest due to its relationships to classical problems in the online algorithmscommunity. Specifically, OLIM is a generalization of several classic online algorithmic problems inthe area of online search or conversion problems [45]. Notable examples include the time seriessearch and one-way trading problems [25], the multiple-choice secretary problem [14], the k-searchproblem [43], and online linear programs with covering constraints [18]. In contrast to theseproblems, in OLIM there is uncertainty not just in the arriving costs, but also in the arrival of thedemand. In addition, OLIM incorporates inventory management constraints to track the arrivaland departures to the inventory over time.Beyond its algorithmic interest, our interest in OLIM stems from its connection to the problemof energy storage management when procuring energy from the electricity markets. Energyprocurement and storage management is a challenging problem for large-scale electricity customerssuch as data centers, university campuses, or enterprise headquarters. Usually, these customers cansatisfy their energy demand from a portfolio of sources, including the electric grid, local renewablesources, and on-site energy storage systems. Notable examples are thermal energy storage inGoogle data center in Taiwan [4], Tesla batteries to power Amazon data center in California [7],Google data center with on-site renewable sources in Belgium [5], and large-scale batteries inApple Park’s microgrid [3]. However, the electricity pricing for large customers is moving towardreal-time pricing where price changes dynamically over time [31, 57, 61]. To counter this volatility,on-site storage systems are necessary, since they enable purchasing energy at low price periods.However, the management of such storage systems is challenging and can be captured via OLIM.Summary of Contributions. In this paper, we develop online algorithms for OLIM with provably the best possible competitive ratios. More specifically, we propose two new algorithms: ARP11 ARPis short for Adaptive Reservation Price.Proc. ACM Meas. Anal. Comput. Syst., Vol. 4, No. 1, Article 16. Publication date: March 2020.
Online Linear Optimization with Inventory Management Constraints16:3(§3.1) and ARPRate (§3.3). ARP is the simpler of the two, and works for OLIM problems that have norate constraints, i.e., no limit on input and output rate to/from the inventory at any slot. ARPRate ismore complex, but works in a more general context, where the input and output rates are bounded.The high-level intuition behind ARP is to store assets when prices are low and use the storedassets when the price rises. However, the fact that prices and demands are dynamic makes thischallenging. The main ideas in the design of ARP are: (i) adaptive reservation based on inventoryutilization that manages the challenges due to price dynamics; and (ii) the construction of virtualinventory that is used to tackle the challenges due to demand dynamics. The notion of virtualinventory is an algorithmic advance compared to previous work [21, 22]. In particular, given someback-up assets in the inventory, one can see satisfying the demand in each slot as the buying(minimization) version of an online k-search problem2 [43] with the current demand as the targetamount. However, the dynamic arrival of demands makes these online search problems coupledover time, and exacerbates the competitive analysis of the algorithms. Virtual inventory allows thisto be managed. The full details are provided in §3.1 with analysis in §3.2.ARPRate extends ARP to the case with rate constraints that limit the buying amount in each timeslot to respect the limits of the inventory. In the energy storage management example, the rateconstraints capture the charge/discharge limits of the batteries. Rate constraints add considerablecomplexity and have not been previously included in online optimization problems with inventoryconstraints. Two significant changes when generalizing from ARP to ARPRate are: (i) adaptivedetermination of the capacity of virtual inventories to reflect the output rate, and (ii) adaptivesetting of reservation price to reflect the input constraints. The full details are provided in §3.3.Our main technical results provide a competitive analysis and demonstrate that both ARP andARPRate achieve the optimal competitive ratio of α as 1θ 1α W 1 ,(1)θ exp(1)where θ is the price fluctuation ratio, and W (.) is Lambert-W function, defined as the inverseof f (z) z exp(z). Interestingly, the above competitive ratios for ARP and ARPRate are exactlythe same as the optimal competitive ratio for k-min search problem (see [43, Theorem 2]), whenk . However, OLIM is different since it comes with additional uncertainty about the demandas compared to [43] and includes an inventory management constraint that is not present in [43].For illustrative purposes, Figure 1 depicts the value of the optimal competitive ratio α as a functionof price fluctuation ratio θ , as compared to a sub-optimal competitive ratio of θ achieved in [22]in a slightly different setting, and log θ as a baseline, and it shows that its growth is less than theθ . However, series expansion of Lambert-W function shows that α as indicated in Equation (1) isΘ( θ ).To illustrate the performance of ARP and ARPRate outside of the worst-case setting, we alsoperform a case study centered on our motivating example: energy storage management. Morespecifically, we evaluate our algorithms using data traces of electricity prices from several electricitymarkets (CAISO [19], NYISO [47], ERCOT [26], and German Electricity Market [30]), energydemands from multiple data centers of Akamai’s CDN [46], and renewable energy productionfrom solar [24] and wind installations [2, 6]. This case study shows that ARP and ARPRate providesignificant improvements compared to state-of-the-art solutions. Specifically, in a broad set ofrepresentative scenarios that include different seasons and locations, we show that ARP achieves athe minimization version of online k-search problem, a player must buy k 1 units of an asset with the goal ofminimizing the cost. In each slot t {1, . . . , T }, the player is presented a price p(t ), and must immediately decide whetheror not to buy some units of the asset given p(t ). Details in [43].2 InProc. ACM Meas. Anal. Comput. Syst., Vol. 4, No. 1, Article 16. Publication date: March 2020.
16:4Lin Yang et al.Competitive Ratio1210864220406080100120140Fig. 1. An illustrationof competitive ratio in Equation (11) as a function of price fluctuation ratio θ in comparison with θ [22] and log θ .cost reduction of 15% in comparison with using no energy storage at all, establishing the valueof batteries for energy procurement. Further, ARP achieves an energy cost that is within 21–23%of the theoretically smallest achievable cost in an offline setting. In addition, ARP outperformsstate-of-the-art algorithms for energy procurement by 7.5–10%.2PRELIMINARIESIn this section, we present the system model and formulate the problem. The interpretation of themodel is illustrated using the cases study of storage-assisted energy procurement.We assume that the time-slotted model in which the time horizon is divided into T slots, indexedby t, each with fixed length, e.g., 5 minutes in California ISO (CAISO) and New York ISO (NYISO) [1].We consider the following scenario. At each slot, a demand d(t) 0 arrives online that must besatisfied from either the market with the real-time price p(t) 0 or from the local inventory, e.g.,the energy storage system. We note that while the demand and price values are known for thecurrent slot, those values are unknown for the future slots. Thus, the decision making has to beperformed in an online fashion. The decision maker can purchase excess from the market in orderto store in the inventory for future use. The goal is to design an algorithm to determine the valueof x(t), i.e., the procurement amount in each slot, so that the aggregate cost of purchases over thetime horizon is minimized and the demand is satisfied.2.1Inventory Management Constraints
Online Linear Optimization with Inventory Management Constraints 16:3 (§3.1) and ARPRate (§3.3). ARP is the simpler of the two, and works for OLIM problems that have no rate constraints, i.e., no limit on input and output rate to/from the inventory at any slot. ARPRate is
