Information Collection for Linear Programs with Uncertain Objective Coefficients
Information Collection for Linear Programs with Uncertain Objective Coefficients
复制标题
具有不确定目标系数的线性规划的信息收集
DOI：
--
复制
发表时间：
2012
影响因子：
3.1
通讯作者：
Warrren B Powell
中科院分区：
文献类型：
--
作者：
I. Ryzhov;Warrren B Powell
考虑一个目标系数不确定的线性规划（LP），我们有一个贝叶斯先验。我们可以收集信息来提高我们对这些系数的理解，但这可能是昂贵的，给我们一个单独的问题，优化信息的收集，以提高解决方案的质量相对于真实的成本系数。我们制定了这个信息收集问题的LP第一次，并得出一个知识梯度的政策，找到每个测量的边际值，通过解决一个序列的LP。我们证明了该策略是渐近最优的，并证明了其性能的网络流问题。
Consider a linear program (LP) with uncertain objective coefficients, for which we have a Bayesian prior. We can collect information to improve our understanding of these coefficients, but this may be expensive, giving us a separate problem of optimizing the collection of information to improve the quality of the solution relative to the true cost coefficients. We formulate this information collection problem for LPs for the first time and derive a knowledge gradient policy which finds the marginal value of each measurement by solving a sequence of LPs. We prove that this policy is asymptotically optimal and demonstrate its performance on a network flow problem.