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 language | English (US) |
---|---|
Pages (from-to) | 1344-1368 |
Number of pages | 25 |
Journal | SIAM Journal on Optimization |
Volume | 22 |
Issue number | 4 |
DOIs | |
State | Published - 2012 |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Applied Mathematics
Keywords
- Optimal learning
- Sequential learning
- Stochastic optimization
- Stochastic programming