### Technical Report ERGO 09-007

#### A multi-step interior point warm-start approach for large-scale stochastic linear programming

*Marco Colombo and Andreas Grothey*

##### Abstract:

Interior point methods (IPM) have been recognized as an efficient approach for
the solution of large scale stochastic programming problems by exploiting the
block-angular 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 warm-start information.

In this paper we present a multi-step warm-start scheme for stochastic
programming problems, where a sequence of problems defined over scenario
trees of differing sizes is given and an IPM warm-start 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
two-step scheme and give numerical results.

##### Keywords:

Stochastic programming, Interior point methods, Warm-starting, Structure exploitation

##### Download:

ERGO-09-007.pdf

##### History:

Written: 30 June 2009

Revised: 3 December 2010

##### Status:

Submitted for publication