Seminars & Events

Mathematics and Computer Science Division
"Preprocessing Stochastic Shortest-Path Problems"

DATE: January 12, 2011
TIME: 10:30 AM - 11:30 AM
SPEAKER: Daniel Reich, The University of Arizona, LANS Postdoc Interviewee
LOCATION: Building 240 Seminar Room 4301, Argonne National Laboratory
HOST: Sven Leyffer

Description:
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.

Save the event to your calendar [schedule.ics]