Preprocessing stochastic shortest-path problems with application to PERT activity networks

Daniel Reich, Leonardo Lopes

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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
Original languageEnglish
Pages (from-to)460 - 469
Number of pages10
JournalINFORMS Journal on Computing
Volume23
Issue number3
DOIs
Publication statusPublished - 2011

Cite this