Approximate Dynamic Programming for Stochastic Combinatorial Problems

David Castanon


Consider the problem of selecting a sequence of tests to diagnose specific failed components which are part of an overall system. In such problems, there is initial uncertainty as to which components are still in working order. In addition, there is uncertainty associated with the outcome of any selected test, since this outcome will depend, at a minimum, on the status of the components being tested. As data from each test is collected, information about the status of each component increases. A plan is a strategy which maps the possible states of information about component status into the selected sequence of tests. The planning problem consists of selecting plans which lead to optimal performance (such as minimizing a tradeoff of test costs and diagnosis accuracy) when averaged over the possible uncertain contingencies. The above problem is an example of a stochastic control problem in which the decision options at any one time are discrete. If one restricts the strategies to be open-loop (independent of the collected information), the resulting optimization problem is a combinatorial sequencing problem. In order to obtain feedback strategies which exploit the arrival of information, Bellman’s Principle of Optimality and the associated stochastic dynamic programming methodology can be used to reduce the computational complexity associated with optimization over time. This procedure has two principal drawbacks: it requires enumeration of all possible future stochastic realizations of the process, and it requires an enumerative search over possible options for decisions for each realization. These drawbacks make exact dynamic programming a formidable task for all but the simplest of problems. In this talk, I will discuss ideas for approximate solution of stochastic combinatorial problems, based on approximations of the stochastic dynamic programming algorithm. The talk will include some recent results, as well as speculative research directions and limitations.