Projects per year
Abstract / Description of output
Interior point methods (IPM) have been recognized as an efficient approach for the solution of large scale stochastic programming problems by exploiting the blockangular structure of the augmented system resulting from this problem class. Stochastic programming problems, however, have exploitable structure beyond simple matrix shape: namely the scenarios are typically a discrete sampling of an underlying (continuous) probability distribution. An appealing way of exploiting this would be to initially use a coarser discretization, i.e. less scenarios to obtain an approximate solution, which could then be used to warmstart the solver on the full problem. Unfortunately IPMs are well known for their difficulties in exploiting warmstart information.
In this paper we present a multistep warmstart scheme for stochastic programming problems, where a sequence of problems defined over scenario trees of differing sizes is given and an IPM warmstart point is constructed by successively finding approximations to the central path of the problems defined over the given trees. We analyse the resulting algorithm, argue that it yields improved complexity over either the coldstart or a naive twostep scheme and give numerical results.
In this paper we present a multistep warmstart scheme for stochastic programming problems, where a sequence of problems defined over scenario trees of differing sizes is given and an IPM warmstart point is constructed by successively finding approximations to the central path of the problems defined over the given trees. We analyse the resulting algorithm, argue that it yields improved complexity over either the coldstart or a naive twostep scheme and give numerical results.
Original language  English 

Pages  126 
Number of pages  26 
Publication status  Unpublished  30 Jun 2009 
Fingerprint
Dive into the research topics of 'A multistep interior point warmstart approach for largescale stochastic linear programming'. Together they form a unique fingerprint.Projects
 1 Finished

Warmstarting techniques for stochastic programming problems solved by interior point methods.
1/04/07 → 31/03/09
Project: Research