This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Topaloglu, H. Articles by Powell, W. B. Search for Related Content

Dynamic-Programming Approximations for Stochastic Time-Staged Integer Multicommodity-Flow Problems

School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853, USA
Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544, USA
topaloglu{at}orie.cornell.edu
powell{at}princeton.edu

In this paper, we consider a stochastic and time-dependent version of the min-cost integer multicommodity-flow problem that arises in the dynamic resource allocation context. In this problem class, tasks arriving over time have to be covered by a set of indivisible and reusable resources of different types. The assignment of a resource to a task removes the task from the system, modifies the resource, and generates a profit. When serving a task, resources of different types can serve as substitutes of each other, possibly yielding different revenues. We propose an iterative, adaptive dynamic-programming-based methodology that makes use of linear or nonlinear approximations of the value function. Our numerical work shows that the proposed method provides high-quality solutions and is computationally attractive for large problems.

Key words: dynamic programming; networks-graphs; multicommodity; transportation
History: received August 2003; revised February 2004; accepted March 2004.

This article has been cited by other articles:

				W. B. Powell Feature Article--Merging AI and OR to Solve High-Dimensional Stochastic Optimization Problems Using Approximate Dynamic Programming INFORMS Journal on Computing, January 1, 2010; 22(1): 2 - 17. [Abstract] [PDF]

				M. F. Gorman, D. Acharya, and D. Sellers CSX Railway Uses OR to Cash In on Optimized Equipment Distribution Interfaces, January 1, 2010; 40(1): 5 - 16. [Abstract] [PDF]

				H. P. Simao, J. Day, A. P. George, T. Gifford, J. Nienow, and W. B. Powell An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application Transportation Science, May 1, 2009; 43(2): 178 - 197. [Abstract] [PDF]

				A. L. Erera, J. C. Morales, and M. Savelsbergh Robust Optimization for Empty Repositioning Problems Operations Research, March 1, 2009; 57(2): 468 - 483. [Abstract] [PDF]

				J. M. Nascimento and W. B. Powell An Optimal Approximate Dynamic Programming Algorithm for the Lagged Asset Acquisition Problem Mathematics of Operations Research, February 1, 2009; 34(1): 210 - 237. [Abstract] [PDF]

				L. Schenk and D. Klabjan Intramarket Optimization for Express Package Carriers Transportation Science, November 1, 2008; 42(4): 530 - 545. [Abstract] [PDF]

				Y. Guan and A. J. Miller Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems Operations Research, September 1, 2008; 56(5): 1172 - 1183. [Abstract] [PDF]

				F. Papier and U. W. Thonemann Queuing Models for Sizing and Structuring Rental Fleets Transportation Science, August 1, 2008; 42(3): 302 - 317. [Abstract] [PDF]

				S. Kunnumkal and H. Topaloglu Exploiting the Structural Properties of the Underlying Markov Decision Problem in the Q-Learning Algorithm INFORMS Journal on Computing, January 1, 2008; 20(2): 288 - 301. [Abstract] [PDF]

				H. Topaloglu and W. Powell Incorporating Pricing Decisions into the Stochastic Dynamic Fleet Management Problem Transportation Science, August 1, 2007; 41(3): 281 - 301. [Abstract] [PDF]

				H. Topaloglu and W. B. Powell Sensitivity Analysis of a Dynamic Fleet Management Model Using Approximate Dynamic Programming Operations Research, March 1, 2007; 55(2): 319 - 331. [Abstract] [PDF]