Warmstarting techniques for stochastic programming problems solved by interior point methods.

We have
• Assembled a test problem collection. This is based on existing test problem sets,
expanded by financial planning problems, electricity swing option valuation problems,
as well as stochastic capacity assignment and capacitated multi-product feed
mix problems in collaboration with our project partners.
• Developed a stochastic programming extension to the structured modelling language
SML (http://www.maths.ed.ac.uk/ERGO/sml/), to aid the formulation of
new problem classes in a format that allows easy communication with structure
exploiting solvers (and crash-start generators).
• Explored suitable tree approximation algorithms, including clustering and scenario
and stage aggregation schemes.
• Implemented a multi-level stochastic warmstart procedure, where the reduced tree
itself is warmstarted from a further aggregated tree. This procedure has demonstrated
a further time-saving over the simple one-level reduced-tree warmstart and
achieves a sustained speed-up of a factor of 2 compared to a cold start on a wide
range of large-scale problems (up to 5 million variables/40000 scenarios).
• Implemented a decomposition based warmstart procedure in which the reduced
tree is used to estimate the first stage decision and the full warmstart point is
obtained by solving scenario subproblems.
• Analysed both of the above algorithms, to give conditions under which they lead
to successful warmstarts and to give complexity results for the algorithms.
• Demonstrated the numerical superiority of our warmstart procedure, by showing
sustained savings of 50% of IPM iterations on a wide range of testproblems.