Competitive Bidding Strategies for Online Linear Optimization with Inventory Management Constraints
Competitive Bidding Strategies for Online Linear Optimization with Inventory Management Constraints
复制标题
DOI：
10.1145/3529113.3529115
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Russell Lee;Yutao Zhou;Lin Yang;M. Hajiesmaili;R. Sitaraman
中科院分区：
文献类型：
--
作者：
Russell Lee;Yutao Zhou;Lin Yang;M. Hajiesmaili;R. Sitaraman
本文研究了在成本最小化和利润最大化两种情况下，具有库存管理约束的在线线性优化问题的竞价策略。在最小化问题中，决策者应该通过从市场上购买资产单位或从有限能力的本地库存中生产资产来满足其时变需求。在最大化问题中，决策者拥有随时间变化的资产供应，这些资产可以出售给市场，也可以储存在库存中，以便稍后出售。在这两种情况下，每个时隙的市场价格都是未知的，决策者可以提交有限数量的出价来买卖资产。一旦提交了所有投标，市场价格就会出清，买入/卖出的金额就会根据结算价格和提交的投标来确定。从这个设置，决策者必须最小化/最大化他们在市场上的成本/利润，同时还必须在面对未知的清算价格的情况下设计一个投标策略。针对这类带库存管理约束的线性在线优化问题，我们分别提出了最小化和最大化两种竞价策略DEMBID和SUPBID。然后，我们分析了所提出的算法的竞争比，结果表明，随着最大投标数量的增加，我们的算法的性能接近可能的最佳竞争比。作为案例研究，我们使用Akamai数据中心的能源数据跟踪、NREL的可再生能源产出和NYISO的能源价格来展示我们的投标策略在参与实时电力市场的大型能源客户的能源存储管理背景下的有效性。
This paper develops competitive bidding strategies for an online linear optimization problem with inventory management constraints in both cost minimization and profit maximization settings. In the minimization problem, a decision maker should satisfy its time-varying demand by either purchasing units of an asset from the market or producing them from a local inventory with limited capacity. In the maximization problem, a decision maker has a time-varying supply of an asset that may be sold to the market or stored in the inventory to be sold later. In both settings, the market price is unknown in each timeslot and the decision maker can submit a finite number of bids to buy/sell the asset. Once all bids have been submitted, the market price clears and the amount bought/sold is determined based on the clearing price and submitted bids. From this setup, the decision maker must minimize/maximize their cost/profit in the market, while also devising a bidding strategy in the face of an unknown clearing price. We propose DEMBID and SUPBID, two competitive bidding strategies for these online linear optimization problems with inventory management constraints for the minimization and maximization setting respectively. We then analyze the competitive ratios of the proposed algorithms and show that the performance of our algorithms approaches the best possible competitive ratio as the maximum number of bids increases. As a case study, we use energy data traces from Akamai data centers, renewable outputs from NREL, and energy prices from NYISO to show the effectiveness of our bidding strategies in the context of energy storage management for a large energy customer participating in a real-time electricity market.