Preprocessing Stochastic Shortest-Path Problems with Application to PERT Activity Networks

摘要

We present an algorithm for preprocessing a class of stochastic shortest-path problems on networks that have no negative cost cycles, almost surely. Our method adds utility to existing frameworks by significantly reducing input problem sizes and thereby increasing computational tractability. Given random costs with finite lower and upper bounds on each edge, our algorithm removes edges that cannot be in any optimal solution to the deterministic shortest-path problem, for any realization of the random costs. Although this problem is NP-complete, our algorithm efficiently preprocesses nearly all edges in a given network. We provide computational results both on sparse networks from PSPLIB—a well-known project evaluation and review technique library [Kolisch, R., A. Sprecher. 1996. PSPLIB—A project scheduling problem library. Eur. J. Oper. Res. 96(1) 205-216]—and dense synthetic ones: on average, less than 0.1% of the edges in the PSPLIB instances and 0.5% of the edges in the dense instances remain unclassified after preprocessing.