A Dynamic Near-Optimal Algorithm for Online Linear Programming
A Dynamic Near-Optimal Algorithm for Online Linear Programming
复制标题
DOI：
10.1287/opre.2014.1289
复制
发表时间：
2014-07-01
影响因子：
2.7
通讯作者：
Ye, Yinyu
中科院分区：
文献类型：
--
作者：
Agrawal, Shipra;Wang, Zizhuo;Ye, Yinyu
制定许多在线资源分配问题的自然优化模型是在线线性编程（LP）问题，其中约束矩阵按列以及相应的客观系数揭示了约束矩阵。在这样的模型中，必须在每次揭示列时设置决策变量而不观察未来的输入，而目标是最大化整体目标函数。在本文中，我们建议在随机到达顺序的假设和LP右侧输入大小的某些轻度条件下，为这类在线问题提供了一种近乎理想的算法。具体而言，我们基于学习的算法通过以几何时间间隔动态更新阈值价格向量来工作，其中使用上一个时期中揭示的列中学到的双重价格用于确定当前时期的顺序决策。通过动态学习，我们算法的竞争力改善了过去对同一问题的研究。我们还提供了一个最坏的案例，表明我们的算法的性能几乎是最佳的。
A natural optimization model that formulates many online resource allocation problems is the online linear programming ( LP) problem in which the constraint matrix is revealed column by column along with the corresponding objective coefficient. In such a model, a decision variable has to be set each time a column is revealed without observing the future inputs, and the goal is to maximize the overall objective function. In this paper, we propose a near-optimal algorithm for this general class of online problems under the assumptions of random order of arrival and some mild conditions on the size of the LP right-hand-side input. Specifically, our learning-based algorithm works by dynamically updating a threshold price vector at geometric time intervals, where the dual prices learned from the revealed columns in the previous period are used to determine the sequential decisions in the current period. Through dynamic learning, the competitiveness of our algorithm improves over the past study of the same problem. We also present a worst case example showing that the performance of our algorithm is near optimal.