Adaptive Learning Algorithms for Stochastic Resource Allocation

Thursday, September 26, 2002 - 1:00pm - 2:20pm
Keller 3-180
Warren Powell (Princeton University)
One of the challenges arising in supply chain management is the need to make decisions before all the information is in. This arises in freight transportation when companies have to move equipment to handle the needs of shippers before their demands become known. The same problem is faced by manufacturers who have to plan what products to make before the size of a market is known, or by the same companies who have to decide how much product to ship to a location. In some cases, a company might want to provide a discount if a customer books an order in advance, in which case the company needs to determine the appropriate size of the discount. In addition to the uncertainty, most real problems are characterized by different types of resources or products and substitutable demands.

We propose an algorithmic strategy based on approximate dynamic programming which replaces the value function with a special class of functional approximations. The method requires using an unusual dynamic programming recursion, and easily handles very large scale problems. The strategy is provably optimal for some special cases, and appears to outperform provably optimal algorithms for more general cases because it has a much faster rate of convergence. It also has the nice property of naturally producing integer solutions.

The talk will describe problems where the technique is being put into production, and outline some remaining research challenges.