L-shaped solvers

LShapedAlgorithm

Functor object for the L-shaped algorithm.

...

Algorithm parameters

• τ::AbstractFloat = 1e-6: Relative tolerance for convergence checks.
• debug::Bool = false: Specifies if extra information should be saved for debugging purposes. Defaults to false for memory efficiency.
• cut_scaling::AbstractFloat = 1.0: Rescaling factor for cutting planes to improve numerical stability.
• log::Bool = true: Specifices if L-shaped procedure should be logged on standard output or not.

...

AbstractLShapedAttribute

Abstract supertype for attribute objects specific to the L-shaped algorithm.

AggregationParameter

Abstract supertype for aggregation-specific attributes.

Aggregator

An optimizer attribute for specifying an aggregation procedure to be used in the L-shaped algorithm. Options are:

• NoAggregation: Multi-cut L-shaped algorithm (default)
• PartialAggregation: ?PartialAggregation for parameter descriptions.
• FullAggregation: ?FullAggregation for parameter descriptions.
• DynamicAggregation: ?DynamicAggregation for parameter descriptions.
• ClusterAggregation: ?ClusterAggregation for parameter descriptions.
• HybridAggregation: ?HybridAggregation for parameter descriptions.

ConsolidationParameter

Abstract supertype for consolidation-specific attributes.

Consolidator

An optimizer attribute for specifying a consolidation procedure to be used in the L-shaped algorithm. Options are:

• NoConsolidation
• Consolidation

FeasibilityCuts

An optimizer attribute for specifying if feasibility cuts should be used in the L-shaped algorithm. Options are true of false.

RegularizationParameter

Abstract supertype for regularization-specific attributes.

Regularizer

An optimizer attribute for specifying a regularization procedure to be used in the L-shaped algorithm. Options are:

• NoRegularization: L-shaped algorithm (default)
• RegularizedDecomposition: Regularized decomposition ?RegularizedDecomposition for parameter descriptions.
• TrustRegion: Trust-region ?TrustRegion for parameter descriptions.
• LevelSet: Level-set ?LevelSet for parameter descriptions.

Optimizer(; <keyword arguments>)

Return an L-shaped optimizer. ...

Arguments

• master_optimizer::AbstractOptimizer: MathOptInterface solver capable of solving linear (and possibly quadratic) programs.
• subproblem_optimizer::AbstractOptimizer: Optionally specify a different solver for the subproblems.
• feasibility_cuts::Bool = false: Specify if feasibility cuts should be used
• regularize::AbstractRegularizer = DontRegularize(): Specify regularization procedure (DontRegularize, RegularizedDecomposition/RD/WithRegularizedDecomposition, TrustRegion/TR/WithTrustRegion, LevelSet/LV/WithLevelSets).
• aggregate::AbstractAggregator = DontAggregate(): Specify aggregation procedure (DontAggregate, Aggregate, PartialAggregate, DynamicAggregate, ClusterAggregate, GranulatedAggregate, HybridAggregate)
• consolidate::AbstractConsolidator = DontConsolidate(): Specify consolidation procedure (DontConsolidate, Consolidate)
• execution::Execution = Serial: Specify how algorithm should be executed (Serial, Synchronous, Asynchronous). Distributed variants requires worker cores.
• <keyword arguments>: Algorithm specific parameters, See ?LShaped for list of possible arguments and default values.

...

get_aggregation_attribute(stochasticprogram::StochasticProgram, name::String)

Return the value associated with the aggregation-specific attribute named name in stochasticprogram.

See also: set_aggregation_attribute, set_aggregation_attributes.

get_consolidation_attribute(stochasticprogram::StochasticProgram, name::String)

Return the value associated with the consolidation-specific attribute named name in stochasticprogram.

See also: set_consolidation_attribute, set_consolidation_attributes.

get_regularization_attribute(stochasticprogram::StochasticProgram, name::String)

Return the value associated with the regularization-specific attribute named name in stochasticprogram.

See also: set_regularization_attribute, set_regularization_attributes.

set_aggregation_attribute(stochasticprogram::StochasticProgram, name::Union{Symbol, String}, value)

Sets the aggregation-specific attribute identified by name to value.

set_aggregation_attributes(stochasticprogram::StochasticProgram, pairs::Pair...)

Given a list of attribute => value pairs or a collection of keyword arguments, calls set_aggregation_attribute(stochasticprogram, attribute, value) for each pair.

set_consolidation_attribute(stochasticprogram::StochasticProgram, name::Union{Symbol, String}, value)

Sets the consolidation-specific attribute identified by name to value.

set_consolidation_attributes(stochasticprogram::StochasticProgram, pairs::Pair...)

Given a list of attribute => value pairs or a collection of keyword arguments, calls set_consolidation_attribute(stochasticprogram, attribute, value) for each pair.

set_regularization_attribute(stochasticprogram::StochasticProgram, name::Union{Symbol, String}, value)

Sets the regularization-specific attribute identified by name to value.

set_regularization_attributes(stochasticprogram::StochasticProgram, pairs::Pair...)

Given a list of attribute => value pairs or a collection of keyword arguments, calls set_regularization_attribute(stochasticprogram, attribute, value) for each pair.

SerialExecution

Functor object for using serial execution in a lshaped algorithm. Create by supplying a Serial object through execution in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

SynchronousExecution

Functor object for using synchronous execution in an L-shaped algorithm (assuming multiple Julia cores are available). Create by supplying a Synchronous object through execution in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

AsynchronousExecution

Functor object for using synchronous execution in an L-shaped algorithm (assuming multiple Julia cores are available). Create by supplying a Asynchronous object through execution in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

set_regularization_attribute(stochasticprogram::StochasticProgram, name::Union{Symbol, String}, value)

Sets the regularization-specific attribute identified by name to value.

set_regularization_attributes(stochasticprogram::StochasticProgram, pairs::Pair...)

Given a list of attribute => value pairs or a collection of keyword arguments, calls set_regularization_attribute(stochasticprogram, attribute, value) for each pair.

RawRegularizationParameter

An optimizer attribute used for raw parameters of the regularizer. Defers to RawParameter.

NoRegularization

Empty functor object for running an L-shaped algorithm without regularization.

DontRegularize

Factory object for NoRegularization. Passed by default to regularize in the LShapedSolver factory function.

RegularizedDecomposition

Functor object for using regularized decomposition regularization in an L-shaped algorithm. Create by supplying an RD object through regularize in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

...

Parameters

• σ::AbstractFloat = 1.0: Initial value of regularization parameter. Controls the relative penalty of the deviation from the current major iterate.
• σ̅::AbstractFloat = 4.0: Maximum value of the regularization parameter.
• σ̲::AbstractFloat = 0.5: Minimum value of the regularization parameter.
• log::Bool = true: Specifices if L-shaped procedure should be logged on standard output or not.
• penaltyterm::PenaltyTerm = Quadratic: Specify penaltyterm variant (Quadratic, Linearized, InfNorm, [ManhattanNorm][@ref])

...

RD

Factory object for RegularizedDecomposition. Pass to regularize in the LShapedSolver factory function. Equivalent factory calls: RD, WithRD, RegularizedDecomposition, WithRegularizedDecomposition. See ?RegularizedDecomposition for parameter descriptions.

TrustRegion

Functor object for using trust-region regularization in an L-shaped algorithm. Create by supplying a TR object through regularize in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

...

Parameters

• γ::T = 1e-4: Relative tolerance for deciding if a minor iterate should be accepted as a new major iterate.
• Δ::AbstractFloat = 1.0: Initial size of ∞-norm trust-region.
• Δ̅::AbstractFloat = 1000.0: Maximum size of ∞-norm trust-region.

...

TR

Factory object for TrustRegion. Pass to regularize in the LShapedSolver factory function. Equivalent factory calls: TR, WithTR, TrustRegion, WithTrustRegion. See ?TrustRegion for parameter descriptions.

LevelSet

Functor object for using level-set regularization in an L-shaped algorithm. Create by supplying an LV object through regularize in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

...

Parameters

• λ::AbstractFloat = 0.5: Controls the level position L = (1-λ)θ + λQ̃, a convex combination of the current lower and upper bound.
• penaltyterm::PenaltyTerm = Quadratic: Specify penaltyterm variant (Quadratic, Linearized, InfNorm, [ManhattanNorm][@ref])

...

LV

Factory object for LevelSet. Pass to regularize in the LShapedSolver factory function. Equivalent factory calls: LV, WithLV, LevelSet, WithLevelSets. See ?LevelSet for parameter descriptions.

set_aggregation_attribute(stochasticprogram::StochasticProgram, name::Union{Symbol, String}, value)

Sets the aggregation-specific attribute identified by name to value.

set_aggregation_attributes(stochasticprogram::StochasticProgram, pairs::Pair...)

Given a list of attribute => value pairs or a collection of keyword arguments, calls set_aggregation_attribute(stochasticprogram, attribute, value) for each pair.

DontAggregate

Factory object for NoAggregation. Passed by default to aggregate in LShaped.Optimizer.

NoAggregation

Empty functor object for running an L-shaped algorithm without aggregation (multi-cut L-shaped).

Aggregate

Factory object for FullAggregation. Pass to aggregate in LShaped.Optimizer or by setting the Aggregator attribute.

PartialAggregate

Factory object for PartialAggregation. Pass to aggregate in LShaped.Optimizer or by setting the Aggregator attribute. See ?PartialAggregation for parameter descriptions.

PartialAggregation

Functor object for using partial aggregation in an L-shaped algorithm. Create by supplying a PartialAggregate object through aggregate in LShaped.Optimizer or by setting the Aggregator attribute.

...

Parameters

• size::Int: Number of cuts in each aggregate

...

FullAggregation

Functor object for using complete aggregation in an L-shaped algorithm. Create by supplying an Aggregate object through aggregate in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

DynamicAggregate(num_aggregates::Integer, rule::AbstractSelectionRule; lock_after::Function = (τ,n)->false)

Factory object for DynamicAggregation. Pass to aggregate in LShaped.Optimizer or by setting the Aggregator attribute. See ?DynamicAggregation for parameter descriptions.

DynamicAggregation

Functor object for using dynamic aggregation in an L-shaped algorithm. Create by supplying a DynamicAggregate object through aggregate in LShaped.Optimizer or by setting the Aggregator attribute.

The following selection rules are available

• SelectUniform
• SelectDecaying
• [SelectRandom](@ref
• SelectClosest
• SortByReference

...

Parameters

• num_aggregates::Int: Number of aggregates
• rule::SelectionRule: Rule that determines which aggregate an incoming cut should be placed in
• lock_after::Function = (τ,n)->false: Function that determines if the current aggregation scheme should be fixed, based on the current optimality gap τ and the number of iterations n

...

ClusterAggregate(rule::AbstractClusterRule; lock_after::Function = (τ,n)->false)

Factory object for ClusterAggregation. Pass to aggregate in LShaped.Optimizer or by setting the Aggregator attribute. See ?ClusterAggregation for parameter descriptions.

ClusterAggregation

Functor object for using cluster aggregation in an L-shaped algorithm. Create by supplying a ClusterAggregate object through aggregate in LShaped.Optimizer or by setting the Aggregator attribute.

The following cluster rules are available

• StaticCluster
• ClusterByReference
• [Kmedoids](@ref
• Hierarchical

...

Parameters

• rule::ClusterRule: Rule that determines how cuts should be sorted into clusters
• lock_after::Function = (τ,n)->false: Function that determines if the current aggregation scheme should be fixed, based on the current optimality gap τ and the number of iterations n

...

GranulatedAggregate

Factory object for GranulatedAggregation. Pass to aggregate in LShaped.Optimizer or by setting the Aggregator attribute. See ?GranulatedAggregation for parameter descriptions.

GranulatedAggregation

Functor object for using partial aggregation in an L-shaped algorithm. Create by supplying a GranulatedAggregate object through aggregate in LShaped.Optimizer or by setting the Aggregator attribute.

...

Parameters

• size::Int: Number of cuts in each aggregate

...

HybridAggregate(initial::AbstractAggregator, final::AbstractAggregator, τ::AbstractFloat)

Factory object for HybridAggregation. Pass to aggregate in LShaped.Optimizer or by setting the Aggregator attribute. See ?HybridAggregation for parameter descriptions.

HybridAggregation

Functor object for using hybrid aggregation in an L-shaped algorithm. Create by supplying a HybridAggregate object through aggregate in LShaped.Optimizer or by setting the Aggregator attribute.

...

Parameters

• initial::AbstractAggregator: Initial aggregation scheme
• final::AbstractAggregator: Final aggregation scheme
• τ::T: The active aggregation scheme is switched from initial to final when the optimality gap decreases below τ

...

SelectClosest(τ::AbstractFloat; distance::Function = absolute_distance)

Incoming cuts are placed into the closest aggregate, according the supplied distance function. An empty aggregate is chosen if no aggregate is within the tolerance τ

The following distance measures are available

• absolute_distance
• angular_distance
• [spatioangular_distance](@ref

SelectDecaying(T₀::Integer, T̲::Integer = 1, γ::T)

Behaves like SelectUniform, but the uniform aggregate size decays by γ each iteration, starting from T₀. T̲ is an optional lower bound on the aggregate size.

SelectRandom(max = Inf)

Incoming cuts are placed into aggregates randomly. An optional maximum number of cuts max can be specified.

SelectUniform(n::Integer)

Incoming cuts are placed into aggregates uniformly, so that each aggregate has at most n cuts. Behaves as PartialAggregation.

SortByReference(τ::AbstractFloat; distance::Function = absolute_distance)

Incoming cuts are placed into an aggregate based on the distance to a reference cut, according the supplied distance function. Behaves as SelectClosest if not withing the tolerance τ to the reference cut.

The following distance measures are available

• absolute_distance
• angular_distance
• [spatioangular_distance](@ref

ClusterByReference(τ::AbstractFloat; distance::Function = absolute_distance)

Buffered cuts are aggregated if within the tolerance τ to a reference cut, according the supplied distance function. Behaves as multi-cut otherwise.

The following distance measures are available

• absolute_distance
• angular_distance
• [spatioangular_distance](@ref

Hierarchical(nclusters::Int; distance::Function = absolute_distance, linkage::Symbol = :single)

Buffered cuts are sorted into nclusters clusters, using a Hierarchical algorithm, with the given linkage, over a generalized distance matrix.

The following distance measures are available

• absolute_distance
• angular_distance
• [spatioangular_distance](@ref

Kmedoids(nclusters::Int; distance::Function = absolute_distance)

Buffered cuts are sorted into nclusters clusters, using a K-medoids algorithm over a generalized distance matrix.

The following distance measures are available

• absolute_distance
• angular_distance
• [spatioangular_distance](@ref

StaticCluster(clusters::Vector{Float64})

Buffered cuts are sorting according to the supplied weights clusters

absolute_distance(c₁::AnyOptimalityCut, c₂::AnyOptimalityCut)

Absolute distance between two optimality cuts

angular_distance(c₁::AnyOptimalityCut, c₂::AnyOptimalityCut)

Angular distance between two optimality cuts

spatioangular_distance(c₁::AnyOptimalityCut, c₂::AnyOptimalityCut)

Spatioangular distance between two optimality cuts.

set_consolidation_attribute(stochasticprogram::StochasticProgram, name::Union{Symbol, String}, value)

Sets the consolidation-specific attribute identified by name to value.

set_consolidation_attributes(stochasticprogram::StochasticProgram, pairs::Pair...)

Given a list of attribute => value pairs or a collection of keyword arguments, calls set_consolidation_attribute(stochasticprogram, attribute, value) for each pair.

Consolidate

Factory object for Consolidation. Pass to consolidate in the LShapedSolver factory function. See ?Consolidation for parameter descriptions.

Consolidation

Functor object for using consolidation in an L-shaped algorithm. Create by supplying a Consolidate object through consolidate in the LShapedSolver factory function and then pass to a StochasticPrograms.jl model.

...

Algorithm parameters

• tresh::T = 0.95: Relative amount of redundant cuts in a former iteration required to consider the iteration redundant
• at::Int = 5.0: Number of times an iteration can be redundant before consolidation is triggered
• rebuild::Function = at_tolerance(): Function deciding when the master model should be rebuilt according to performed consolidations

...

DontConsolidate

Factory object for NoConsolidation. Passed by default to consolidate in the LShapedSolver factory function.

NoRegularization

Empty functor object for running the L-shaped algorithm without consolidation.

RawConsolidationParameter

An optimizer attribute used for raw parameters of the consolidator. Defers to RawParameter.

at_tolerance(τ = 0.4, miniter = 0)

Rebuild master when at least nconsolidations*miniter iterations has passed and the ratio of number of cuts in the consolidated collection and the number of cuts in the master model has decreased below τ.