Solving large-scale nonlinear stochastic network problems

Recent advances in computing technologies, has led to the development of stochastic programming as a promising field to handle uncertainty in a dynamic setting. Stochastic programming models constitute one of the most challenging areas of mathematical programming and can be used to model a rich variety of applications in finance, transportation, engineering, management and economics.; This research focuses on solution techniques for stochastic models formulated as generalized nonlinear network problems. In the first part, a hybrid dual algorithm is developed for solving large-scale quadratic network problems. The fast initial convergence properties of a new dual preflow algorithm and fast final convergence of the conjugate gradient algorithm are combined to obtain a hybrid dual algorithm with excellent convergence properties for all problem types. Object oriented programming constructs are used to develop arc adjacency list data structures with dynamic memory management for implementation on personal computers. Computational study of transshipment problems show that the hybrid algorithm outperforms the existing methods by a significant margin.; The second part of this research studies the adaptation of the hybrid dual algorithm to stochastic networks with discretely distributed random parameters. This is accomplished by using a scenario decomposition scheme based on the progressive hedging method. The solutions of the various scenario subproblems are aggregated using a logarithmic potential function instead of the traditional augmented Lagrangian function. The advantage of the potential function is that it eliminates the sensitivity to the augmented penalty parameter by dynamically penalizing constraints based on their violation. Computational results of several existing problems related to financial portfolio management show significant speedup over existing algorithms.; The potential for parallelism is exploited by developing a hybrid multilevel implementation based on message passing and multithreading for distributed shared memory environments. Portable MPI message passing library is used for coarse grained scenario level parallelism and universal POSIX threads are used to exploit fine grained parallelism of the conjugate gradient line search routine. Computational results of various problems show that the performance is significantly enhanced by full exploitation of parallel processing capabilities.