INFORMS Dallas 1997 Cluster: Stochastic & Robust Optimization; Parallel & Supercomputing

TB29.1 Performance Study of Parallel Shortest Path Algorithms Michelle R. Hribar, Valerie Taylor, David E. Boyce --- Northwestern Univ., 2145 Sheridan Rd., ECE Dept., Evanston, IL 60208-3118, (michelle@ece.nwu.edu)

The performance of parallel labeling shortest path algorithms is¨ affected by both the algorithm choice and the network decomposition.¨ We identify factors of the decomposition which determine the¨ performance of the different algorithms. We use these factors to¨ identify good decompositions and to predict the best algorithm for a¨ given decomposition.

TB29.2 Parallel Computation of Shortest Paths for Transportation Applications Ismail Chabini, Michael Florian, Eric Le Saux, Nicolas Tremblay --- MIT, Dept. of Civil & Environ. Eng., 77 Mass. Ave., Rm. 1-263, Cambridge, MA 02139 , (chabini@mit.edu)

We present several parallel computing implementations of static and¨ time dependent shortest path algorithms for use in network¨ equilibrium models and mesoscopic traffic simulations. The computing¨ platforms used are distributed SUN SPARC Ultra 1 workstations and a¨ SUN SPARC Center 1000 shared memory machine.

TB29.3 Parallel Computing Approaches for Real-Time Fleet Management Michel Gendreau --- Univ. de Montreal, CRT/DIRO, CP 6128, Succ. Centre-ville, Montreal, Quebec, H3C 3J7 , Canada (michelg@crt.umontreal.ca)

Situations where vehicles must be dispatched in real-time to satisfy¨ service requests over some territory are numerous and quite varied:¨ ambulance dispatching, pick-up and delivery operations, etc. We¨ discuss 2 parallel computing approaches which may be used to¨ implement in real-time sophisticated heuristic procedures for¨ managing large fleets.

TB29.4 Parallel Computation of Dynamic Elastic & Fixed Demand Traffic Network Problems Anna Nagurney, Ding Zhang --- Univ. of MA, Sch. of Mgmt., Dept. of Finance & Op. Mgmt., Amherst, MA 01003 , (nagurney@gbfin.umass.edu)

We present algorithms for the solution of dynamic traffic network¨ problems modeled as projected dynamical systems. We provide¨ convergence results as well as numerical results for the¨ implementations on the Thinking Machines' CM-5 architecture.

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.

TD29.1 PANEL: Parallel & Supercomputing Anna Nagurney, Robert Bixby, Robert W. Ashford, Greg Astfalk --- Univ. of MA, Sch. of Mgmt., Dept. of Finance & Op. Mgmt., Amherst, MA 01003 , (nagurney@gbfin.umass.edu)

The parallel and supercomputer industry is advancing rapidly with¨ quite a bit of turmoil. We discuss recent developments in the area,¨ as well as future directions in hardware paradigms and in software¨ issues, such as ease of development and porting. We represent both¨ hardware manufacturers and software developers.

TE29.1 Creating Customized Financial Securities via Multi-Stage Stochastic Programs John M. Mulvey --- Princeton Univ., Dept. of Civil Eng. & OR, E-407 E Quad., Princeton, NJ 08544 , (mulvey@macbeth.princeton.edu)

A multi-stage stochastic program is structured to identify scenarios¨ that cause difficulties for a long-term investor. We re-shape the¨ wealth path by purchasing/selling customized financial products with¨ payoffs conditional on several economic factors, such as interest¨ rate and inflation trends. An example is presented for a large¨ re-insurance company.

TE29.2 Comparisons of Static & Dynamic Asset Allocation Models John R. Birge --- Univ. of MI, Dept. of IOE, 1205 Beal Ave., Ann Arbor, MI 48109-2117, (jrbirge@umich.edu)

The classical Markowitz portfolio model assumes a static environment¨ in creating an efficient portfolio. We compare this approach with a¨ stochastic program that optimizes asset allocation over a fixed time¨ horizon with given liabilities and transaction fees. We use¨ historical data for a collection of asset indices.

TE29.3 Financial Planning Model via Multistage Stochastic Programming Yuan-An Fan, Steve Murray, Andy Turner --- Frank Russell Co., 909 A St., Tacoma, WA 98402 , (yfan@mail.russell.com)

We describe the implementation of a retail level Italian financial¨ planning model. We include a description of the real world setting¨ from a consumer view point, issues regarding its simplification into¨ a large scale stochastic programming model and subsequent¨ translation of the solution to the consumer's original context.