`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:

- L-shaped with multiple cuts (default):
`regularization = :none (default)`

- L-shaped with regularized decomposition:
`regularization = :rd`

- L-shaped with trust region:
`regularization = :tr`

- L-shaped with level sets:
`regularization = :lv`

Note, that `:rd`

and `: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 `LShapedSolver`

.

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 `?LShapedSolver`

.

`LShapedSolvers.jl`

includes a set of crash methods that can be used to generate the initial decision by supplying functor objects to `LShapedSolver`

. Use `?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.

04/06/2018

6 months ago

129 commits