A RELAXATION-BASED PRUNING TECHNIQUE FOR A CLASS OF STOCHASTIC SHORTEST-PATH PROBLEMS

In this paper a form of the stochastic shortest path problem is consid ered where the optimal path is one that maximizes the expected utility which is concave and quadratic. The principal contribution of this pa per is the development of a relaxation based pruning technique which i s incorporated into a label setting procedure. The basic label setting procedure solves the problem by generating all Pareto-optimal paths. However, the number of such paths can grow exponentially with the size of the problem. The relaxation based pruning technique developed here is able to recognize and discard most of the Pareto-optimal paths tha t do not contribute to the optimal path. Our computational results sho w that the label setting procedure that incorporates the pruning techn ique consistently outperforms the basic label setting procedure, and i s abbe to solve large problems very quickly.