Warmstarting Techniques for Stochastic Programming Problems solved by Interior Point Methods

Uncertainty in the data is a commonly observed phenomenon inoptimization problems with an application background. Commonlyoccurrences of uncertainty is the use of forecasted prices ordemands. It can be argued that nearly all practical optimizationproblems display uncertainty in the data, even if this is not madeexplicit in the chosen solution method. Applications such as networkoptimization in telecommunications, production planning and portfoliooptimization are of special interest to us.The stochastic programming approach to optimization under uncertaintyaims to take all possible future outcomes into account, weighing themwith their respective probabilities. This is achieved by use of anevent tree to approximate the underlying stochastic process. Itsstrength lies in the possibility to model risk-exposure, leading tomore robust model solutions. One of its weaknesses is the fact thatstochastic programming leads to problems with very large dimensions,making their solution challenging.Interior point methods (IPM) have emerged as a powerful solutionapproach for stochastic programming problems, being applicable togeneral formulations and making nonlinear problems tractable. Anappealing idea to speed up the solution of stochastic programmingproblems is to exploit the structure of the problem to construct andsolve an approximation (which is faster to solve) and use this toguide the solution process of the full problem. Unfortunately IPMsare well known for their difficulty in exploiting such advancedstarting point information. Despite progress in the theory andpractice of warmstarting IPMs further work is needed; it is our beliefthat major improvements can only be achieved by exploiting the problemstructure in applications like stochastic programming.The aim of this project is to speed up the solution of stochasticprograms by IPMs through a crash-starting scheme that uses asimplification of the original problem to construct a near-optimalsolution of the full problem and uses this to warmstart the interiorpoint method.The developed methodology will also be applied to dynamically adaptthe event tree during the solution process. The solution of a first coarseapproximation can be used to identify regions in which the event treeneeds to be refined and this refined model can be solved quickly fromthe coarse solution using the techniques developed earlier.Our emphasis will be on the development of a practical algorithm forthe fast solution of stochastic programms as well as theoreticalanalysis leading to a bound on the complexity of the resultingwarmstarted algorithm, improving on the known, more general results.The exploitation of parallelism in solution algorithms will becomeincreasingly more important as microprocessor manufacturers are forcedto move to multi-core architectures rather than increasing processorspeed. Therefore the efficient parallelisation of the developedalgorithms will be a focus point of our research.It is anticipated that this research will lead to faster solutionmethods for large stochastic programming problems while keeping theflexibility in modelling offered by using an interior point approachto solve the problem.A further consequence of this research will be a better understandingof the warmstarting properties of interior point methods. This area isof direct interest in many related research areas such as integerprogramming, nonlinear programming, and multicriteria optimization,where IPM have not yet had as large an impact due to theirwarmstarting difficulties.Ultimately the availability of better solution methods for largenonlinear stochastic programming problems will lead to wider adoptionof this methodology in applications, in turn leading to more robustsolutions being implemented.