A decomposition-based crash-start for stochastic programming

被引：0
作者：
Marco Colombo
Andreas Grothey
机构：
[1] The University of Edinburgh,School of Mathematics and Maxwell Institute
来源：
Computational Optimization and Applications | 2013年 / 55卷
关键词：
Stochastic programming; Interior point methods; Warm-starting;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper we propose a crash-start technique for interior point methods applicable to multi-stage stochastic programming problems. The main idea is to generate an initial point for the interior point solver by decomposing the barrier problem associated with the deterministic equivalent at the second stage and using a concatenation of the solutions of the subproblems as a warm-starting point for the complete instance. We analyse this scheme and produce theoretical conditions under which the warm-start iterate is successful. We describe the implementation within the OOPS solver and the results of the numerical tests we performed.
引用
收藏
页码：311 / 340
页数：29
相关论文
共 35 条
  • [1] Ariyawansa K.A.(2004)On a new collection of stochastic linear programming test problems INFORMS J. Comput. 16 291-299
  • [2] Felt A.J.(1985)Decomposition and partitioning methods for multistage stochastic linear programs Oper. Res. 33 989-1007
  • [3] Birge J.R.(2002)A Riccati-based primal interior point solver for multistage stochastic programming Eur. J. Oper. Res. 143 452-461
  • [4] Blomvall J.(2011)A warm-start approach for large-scale stochastic linear programs Math. Program. 127 371-397
  • [5] Lindberg P.O.(1974)On the speed of an iterative process Upravlaemye Sistemy 12 54-60
  • [6] Colombo M.(2002)Benchmarking optimization software with performance profiles Math. Program. 91 201-213
  • [7] Gondzio J.(2003)Scenario reduction in stochastic programming Math. Program. 95 493-511
  • [8] Grothey A.(2003)Reoptimization with the primal-dual interior point method SIAM J. Optim. 13 842-864
  • [9] Dikin I.I.(2008)A new unblocking technique to warmstart interior point methods based on sensitivity analysis SIAM J. Optim. 19 1184-1210
  • [10] Dolan E.(2003)Parallel interior point solver for structured linear programs Math. Program. 96 561-584
1234