Stochastic Programming

TC29.1 Multi-Vehicle Routing on a Stochastic Network Astrid Kenyon, David P. Morton --- Univ. of TX, Dept. of Mech. Eng., Austin, TX 78712 ,

We consider a MVRP on a network with random travel times. The¨ problem is modeled as a stochastic integer program. Stochastic¨ programming methods and heuristics are used to find near-optimal¨ solutions. We discuss the practicality of the solutions for¨ real-world implementation.

TC29.2 New Bounds on the Expected Values of Superadditive & Subadditive Functions Chang Yu --- Northern Telecom Inc., PO Box 833871, Richardson, TX 75083-3871,

Bounds using O(n^2) function evaluations are developed for¨ superadditive and subadditive functions; standard Edmundson-Madansky¨ bounds would require 2^n function evaluations. Computational¨ examples show that the new bounds can be refined within a sequential¨ approximation algorithm to solve 2-stage stochastic programs with¨ recourse.

TC29.3 A Polynomial-Time Solution to a Stochastic Maximum Flow Problem David P. Morton, Kevin R. Wood --- Univ. of TX, Dept. of Mech. Eng., Austin, TX 78712 , (morton@mail.utexas.edu)

The 'restricted stochastic maximum flow problem,' an example of¨ 'restricted recourse,' finds the maximum expected flow in a network¨ with unreliable arcs given that flow cannot be rerouted after arcs¨ fail. We prove that the problem is solveable in polynomial time and¨ give computational results on some real-world networks.