Information collection for linear programs with uncertain objective coefficients

Ilya O. Ryzhov, Warren B. Powell

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1344-1368
Number of pages25
JournalSIAM Journal on Optimization
Volume22
Issue number4
DOIs
StatePublished - Dec 31 2012

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science

Keywords

  • Optimal learning
  • Sequential learning
  • Stochastic optimization
  • Stochastic programming

Fingerprint Dive into the research topics of 'Information collection for linear programs with uncertain objective coefficients'. Together they form a unique fingerprint.

  • Cite this