State Space Partitioning Methods for Solving a Class of Stochastic NetworkProblems

摘要

This study focuses on state space partitioning techniques for computing measuresrelated to the operation of stochastic systems. These methods iteratively decompose the system state space until the measure of interest has been determined. The information available in each iteration yields lower and upper bounds on this measure, and can be used to design efficient Monte Carlo estimation routines. We present here new theoretical results identifying strategies for significantly enhancing the performance of these algorithms. Using these results, we describe a generalized algorithm that can easily be tailored to address a variety of problems. We net use this algorithm to analyze two important models in the area of stochastic network optimization. The first concerns the probabilistic behavior of minimum spanning trees in graphs with discrete random arc weights. Specifically, we compute the probability distribution of the weight of a minimum spanning tree and the probability that a given arc is on a minimum spanning tree. Both of these problems are shown to be P-hard. The second model considers minimum cost flows in networks with discrete random arc costs and capacities.