Uniform Loss Algorithms for Online Stochastic Decision-Making With Applications to Bin Packing
Uniform Loss Algorithms for Online Stochastic Decision-Making With Applications to Bin Packing
复制标题
在线随机决策的统一损失算法及其在装箱中的应用
DOI：
10.1145/3410048.3410050
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Freund, Daniel
中科院分区：
文献类型：
--
作者：
Banerjee, Siddhartha;Freund, Daniel
我们考虑了一类一般的有限时间在线决策问题，其中在每个周期中，控制器是随机到达的，并且必须从一组允许的动作中选择一个动作，并且最终目标仅取决于集合类型动作的计数。这种框架封装了许多常见优化问题的在线随机变量，包括装箱、广义分配和网络收入管理。在这样的背景下，我们研究了一种自然模型预测控制算法，该算法在每个阶段基于更新的确定性等价优化问题而贪婪地行动。我们引入了一个简单而一般的条件，在这种条件下，与完全知道到达的最优解相比，该算法获得了一致的附加损失(与视界无关)。我们的条件满足于上述问题，以及涉及分段线性目标和离线指数策略的更一般设置，包括航空公司超售问题。
We consider a general class of finite-horizon online decision-making problems, where in each period a controller is presented a stochastic arrival and must choose an action from a set of permissible actions, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems including bin packing, generalized assignment, and network revenue management. In such settings, we study a natural model-predictive control algorithm that in each period, acts greedily based on an updated certainty-equivalent optimization problem. We introduce a simple, yet general, condition under which this algorithm obtains uniform additive loss (independent of the horizon) compared to an optimal solution with full knowledge of arrivals. Our condition is fulfilled by the above-mentioned problems, as well as more general settings involving piece-wise linear objectives and offline index policies, including an airline overbooking problem.
影响因子：
5.4
作者：
Vera, Alberto;Banerjee, Siddhartha
通讯作者：
Banerjee, Siddhartha
基于拉格朗日的在线随机装箱
DOI：
--
发表时间：
2015
期刊：
Measurement and Modeling of Computer Systems
影响因子：
--
作者：
Varun Gupta;A. Radovanovic
通讯作者：
A. Radovanovic