LShapedSolvers is a collection of structured optimization algorithms for two-stage (L-shaped) stochastic recourse problems. All algorithm variants are based on the L-shaped method by Van Slyke and Wets.
LShapedSolvers interfaces with StochasticPrograms.jl, and a given recourse model
sp is solved effectively through
julia> using LShapedSolvers julia> solve(sp,solver=LShapedSolver(ClpSolver())) L-Shaped Gap Time: 0:00:01 (4 iterations) Objective: -855.8333333333358 Gap: 2.1229209144670507e-15 Number of cuts: 5 :Optimal
Note, that an LP capable
AbstractMathProgSolver is required to solve emerging subproblems. Solver objects are obtained through the factory method
LShapedSolver. The following variants of the L-shaped algorithm are implemented:
regularization = :none (default)
regularization = :rd
regularization = :tr
regularization = :lv
:lv both require a QP capable
AbstractMathProgSolver for the master problems. If not available, setting the
linearize keyword to
true is an alternative.
In addition, there is a distributed variant of each algorithm, which requires adding processes with
addprocs prior to execution. The distributed variants are obtained by supplying
distributed = true to
Each algorithm has a set of parameters that can be tuned prior to execution. For a list of these parameters and their default values, use
? in combination with the solver object. For example,
?LShaped gives the parameter list of the default L-shaped algorithm. For a list of all solvers and their handle names, use
LShapedSolvers.jl includes a set of crash methods that can be used to generate the initial decision by supplying functor objects to
?Crash for a list of available crashes and their usage.
Van Slyke, R. and Wets, R. (1969), L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming, SIAM Journal on Applied Mathematics, vol. 17, no. 4, pp. 638-663.
Ruszczyński, A (1986), A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming, vol. 35, no. 3, pp. 309-333.
Linderoth, J. and Wright, S. (2003), Decomposition Algorithms for Stochastic Programming on a Computational Grid, Computational Optimization and Applications, vol. 24, no. 2-3, pp. 207-250.
Fábián, C. and Szőke, Z. (2006), Solving two-stage stochastic programming problems with level decomposition, Computational Management Science, vol. 4, no. 4, pp. 313-353.
6 months ago