Structured solvers

A stochastic program has a structure that can exploited in solver algorithms through decomposition. This can heavily reduce the computation time required to optimize the stochastic program, compared to solving the extensive form directly. Moreover, a distributed stochastic program is by definition decomposed and a structured solver that can operate in parallel will be much more efficient.

Solver interface

The structured solver interface mimics that of MathProgBase, and it needs to be implemented by any structured solver to be compatible with StochasticPrograms. Define a new structured solver as a subtype of AbstractStructuredModel. Moreoever, define a shallow object of type AbstractStructuredSolver. This object is intended to be the interface to end users of the solver and is what should be passed to optimize!. Next, implement StructuredModel, that takes the stochastic program and the AbstractStructuredSolver object and return and instance of AbstractStructuredModel which internal state depends on the given stochastic program. Next, the solver algorithm should be run when calling optimize_structured! on the AbstractStructuredModel. After successfuly optimizing the model, the solver must be able to fill in the optimal solution in the first stage and all second stages through fill_solution!.

Some procedures in StochasticPrograms require a MathProgBase solver. It is common that structured solvers rely internally on some MathProgBase solver. Hence, for convenience, a structured solver can implement internal_solver to return any internal MathProgBase solver. A stochastic program that has an loaded structured solver that implements this method can then make use of that solver for those procedures, instead of requiring an external solver to be supplied. Finally, a structured solver can optionally implement solverstr to return an informative description string for printouts.

As an example, a simplified version of the implementation of the structured solver interface in LShapedSolvers.jl is given below:

abstract AbstractLShapedSolver <: AbstractStructuredModel end

const MPB = MathProgBase

mutable struct LShapedSolver <: AbstractStructuredSolver
    lpsolver::MPB.AbstractMathProgSolver
    subsolver::MPB.AbstractMathProgSolver
    checkfeas::Bool
    crash::Crash.CrashMethod
    parameters::Dict{Symbol,Any}

    function (::Type{LShapedSolver})(lpsolver::MPB.AbstractMathProgSolver; crash::Crash.CrashMethod = Crash.None(), subsolver::MPB.AbstractMathProgSolver = lpsolver, checkfeas::Bool = false, kwargs...)
        return new(lpsolver, subsolver, checkfeas, crash, Dict{Symbol,Any}(kwargs))
    end
end

function StructuredModel(stochasticprogram::StochasticProgram, solver::LShapedSolver)
    x₀ = solver.crash(stochasticprogram, solver.lpsolver)
    return LShaped(stochasticprogram, x₀, solver.lpsolver, solver.subsolver, solver.checkfeas; solver.parameters...)
end

function internal_solver(solver::LShapedSolver)
    return solver.lpsolver
end

function optimize_structured!(lshaped::AbstractLShapedSolver)
    return lshaped()
end

function fill_solution!(stochasticprogram::StochasticProgram, lshaped::AbstractLShapedSolver)
    # First stage
    first_stage = StochasticPrograms.get_stage_one(stochasticprogram)
    nrows, ncols = first_stage_dims(stochasticprogram)
    StochasticPrograms.set_decision!(stochasticprogram, decision(lshaped))
    μ = try
        MPB.getreducedcosts(lshaped.mastersolver.lqmodel)[1:ncols]
    catch
        fill(NaN, ncols)
    end
    StochasticPrograms.set_first_stage_redcosts!(stochasticprogram, μ)
    λ = try
        MPB.getconstrduals(lshaped.mastersolver.lqmodel)[1:nrows]
    catch
        fill(NaN, nrows)
    end
    StochasticPrograms.set_first_stage_duals!(stochasticprogram, λ)
    # Second stage
    fill_submodels!(lshaped, scenarioproblems(stochasticprogram))
end

LShapedSolvers.jl

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 through the structured solver interface. It is available as an unregistered package on Github, ans can be installed as follows:

pkg> add https://github.com/martinbiel/LShapedSolvers.jl

As an example, we solve the simple problem introduced in the Quick start:

using LShapedSolvers
using GLPKMathProgInterface

optimize!(sp, solver = LShapedSolver(:ls, GLPKSolverLP()))

L-Shaped Gap  Time: 0:00:01 (6 iterations)
  Objective:       -855.8333333333358
  Gap:             0.0
  Number of cuts:  8
:Optimal

Note, that an LP capable AbstractMathProgSolver is required to solve emerging subproblems. The following variants of the L-shaped algorithm are implemented:

L-shaped with multiple cuts (default): LShapedSolver(:ls)
L-shaped with regularized decomposition: LShapedSolver(:rd)
L-shaped with trust region: LShapedSolver(:tr)
L-shaped with level sets: LShapedSolver(:lv)

Note, that LShapedSolver(:rd) and LShapedSolver(: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:

Distributed L-shaped with multiple cuts: LShapedSolver(:dls)
Distributed L-shaped with regularized decomposition: LShapedSolver(:drd)
Distributed L-shaped with trust region: LShapedSolver(:dtr)
Distributed L-shaped with level sets: LShapedSolver(:dlv)

which requires adding processes with addprocs prior to execution. The distributed variants are designed for StochasticPrograms, and are most efficient when run on distributed stochastic programs.

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.

ProgressiveHedgingSolvers.jl

ProgressiveHedgingSolvers includes implementations of the progressive-hedging algorithm for two-stage stochastic recourse problems. All algorithm variants are based on the original progressive-hedging algorithm by Rockafellar and Wets. ProgressiveHedgingSolvers interfaces with StochasticPrograms through the structured solver interface. It is available as an unregistered package on Github, ans can be installed as follows:

pkg> add https://github.com/martinbiel/LShapedSolvers.jl

As an example, we solve the simple problem introduced in the Quick start:

using ProgressiveHedgingSolvers
using Ipopt

optimize!(sp, solver = ProgressiveHedgingSolver(:ph, IpoptSolver(print_level=0)))

Progressive Hedging Time: 0:00:06 (1315 iterations)
  Objective:  -855.8332803469448
  δ:          9.570267362791345e-7
:Optimal

Note, that a QP capable AbstractMathProgSolver is required to solve emerging subproblems. In addition, there is a distributed variant of the algorithm: ProgressiveHedgingSolver(:dph), which requires adding processes with addprocs prior to execution. The distributed variant is designed for StochasticPrograms, and is most efficient when run on distributed stochastic programs.

The 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, ?ProgressiveHedging gives the parameter list of the sequential progressive-hedging algorithm. For a list of all solvers and their handle names, use ?ProgressiveHedgingSolver.