TY - JOUR

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

AU - Reich, Daniel

AU - Lopes, Leonardo

PY - 2011

Y1 - 2011

N2 - 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

AB - 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

UR - http://dreich.uai.cl/docs/preprocessing.pdf

U2 - 10.1287/ijoc.1100.0411

DO - 10.1287/ijoc.1100.0411

M3 - Article

VL - 23

SP - 460

EP - 469

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 3

ER -