在线算法
线性规划
数学优化
动态规划
计算机科学
栏(排版)
约束(计算机辅助设计)
集合(抽象数据类型)
算法
功能(生物学)
列生成
对偶(语法数字)
最优化问题
基质(化学分析)
数学
帧(网络)
文学类
艺术
复合材料
生物
材料科学
进化生物学
程序设计语言
电信
几何学
作者
Shipra Agrawal,Zizhuo Wang,Yinyu Ye
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:2014-06-13
卷期号:62 (4): 876-890
被引量:301
标识
DOI:10.1287/opre.2014.1289
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI