Article ID: | iaor20082537 |
Country: | United States |
Volume: | 55 |
Issue: | 4 |
Start Page Number: | 647 |
End Page Number: | 661 |
Publication Date: | Jul 2007 |
Journal: | Operations Research |
Authors: | Adelman Daniel |
Keywords: | programming: dynamic |
We formally derive the standard deterministic linear program (LP) for bid-price control by making an affine functional approximation to the optimal dynamic programming value function. This affine functional approximation gives rise to a new LP that yields tighter bounds than the standard LP. Whereas the standard LP computes static bid prices, our LP computes a time trajectory of bid prices. We show that there exist dynamic bid prices, optimal for the LP, that are individually monotone with respect to time. We provide a column generation procedure for solving the LP within a desired optimality tolerance, and present numerical results on computational and economic performance.