Linear Programming Solutions for Separable Markovian Decision Problems

This paper is concerned with the linear programming solutions to sequential decision (or control) problems in which the stochastic element is Markovian and in which the objective is to minimize the discounted sum of expected costs when a discount factor λ, 0 ≦ λ < 1, is used. In praticular, it deals with a class of “separable” problems for which it is possible to define a “reduced” linear programming problem which will yield the optimal policy and the shadow prices for this problem. The reduced problem involves a substantially smaller number (e.g., 3N vs. N²) of variables than the usual formulation of these problems. Two well-known example problems are solved to illustrate the wide applicability and the utility of these results.