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 (default)
• Consolidation

FeasibilityStrategy

An optimizer attribute for specifying a strategy for dealing with second-stage feasibility the L-shaped algorithm. Options are:

• IgnoreFeasibility (default)
• FeasibilityCuts

IntegerParameter

Abstract supertype for integer-specific attributes.

IntegerStrategy

An optimizer attribute for specifying a strategy for dealing with integers the L-shaped algorithm. Options are:

• IgnoreIntegers (default)
• CombinatorialCuts
• Convexification

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.

NoFeasibilityAlgorithm

Empty functor object for running an L-shaped algorithm without dealing with second-stage feasibility.

IgnoreFeasibility

Factory object for NoFeasibilityAlgorithm. Passed by default to feasibility_strategy in LShaped.Optimizer.

FeasibilityCutsMaster

Master functor object for using feasibility cuts in an L-shaped algorithm. Create by supplying a FeasibilityCuts object through feasibility_strategy in LShaped.Optimizer or set the FeasibilityStrategy attribute.

FeasibilityCutsWorker

Worker functor object for using feasibility cuts in an L-shaped algorithm. Create by supplying a FeasibilityCuts object through feasibility_strategy in LShaped.Optimizer or set the FeasibilityStrategy attribute.

IgnoreFeasibility

Factory object for using feasibility cuts in an L-shaped algorithm.

RawIntegerAlgorithmParameter

An optimizer attribute used for raw parameters of the integer algorithm. Defers to RawOptimizerAttribute.

IgnoreIntegers

Factory object for NoIntegerAlgorithm. Passed by default to integer_strategy in LShaped.Optimizer.

NoIntegerAlgorithm

Empty functor object for running an L-shaped algorithm without dealing with integer variables.

CombinatorialCuts

Factory object for CombinatorialCuts. Pass to integer_strategy in LShaped.Optimizer or set the IntegerStrategy attribute.

...

Parameters

• lower_bound::AbstractFloat = -1e10: Set a lower bound on the second-stage objective, removing the need to approximate it.
• alternate::Bool = false: Specify if algorithm should alternate between solving relaxed problems (generating regular optimality cuts) and unrelaxed problems (generating combinatorial cuts)
• update_L_every::Integer = 0: Set the frequency at which the lower bound approximation should be updated. Only approximate once if set to zero.
• optimizer = nothing: Optionally specify an optimizer used to solve auxilliary problems in the LiftAndProject or CuttingPlaneTree strategies.

...

CombinatorialCutsMaster

Master functor object for using weak optimality cuts in an integer L-shaped algorithm. Requires all first-stage decisions to be binary. Create by supplying a CombinatorialCuts object through integer_strategy in LShaped.Optimizer or set the IntegerStrategy attribute.

CombinatorialCutsWorker

Worker functor object for using weak optimality cuts in an integer L-shaped algorithm. Create by supplying a CombinatorialCuts object through integer_strategy in LShaped.Optimizer or set the IntegerStrategy attribute.

Convexification

Factory object for using convexification to handle integer recourse. Pass to integer_strategy in LShaped.Optimizer or set the IntegerStrategy attribute.

...

Parameters

• maximum_iterations::Integer = 1: Determines the number of iterations spent generating cutting-planes each time a subproblem is solved.
• strategy::ConvexificationStrategy = Gomory(): Specify convexification strategy (Gomory, LiftAndProject, CuttingPlaneTree)
• optimizer = nothing: Optionally specify an optimizer used to solve auxilliary problems in the LiftAndProject or CuttingPlaneTree strategies.

...

ConvexificationMaster

Master functor object for using weak optimality cuts in an integer L-shaped algorithm. Requires all first-stage decisions to be binary. Create by supplying a Convexification object through integer_strategy in LShaped.Optimizer or set the IntegerStrategy attribute.

ConvexificationWorker

Worker functor object for using weak optimality cuts in an integer L-shaped algorithm. Create by supplying a Convexification object through integer_strategy in LShaped.Optimizer or set the IntegerStrategy attribute.

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 RawOptimizerAttribute.

NoRegularization

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

DontRegularize

Factory object for NoRegularization. Passed by default to regularize in LShaped.Optimizer.

RegularizedDecomposition

Functor object for using regularized decomposition regularization in an L-shaped algorithm. Create by supplying an RD object through regularize in LShaped.Optimizer or by setting the Regularizer attribute.

...

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, InfNorm, [ManhattanNorm][@ref])

...

RD

Factory object for RegularizedDecomposition. Pass to regularize in LShaped.Optimizer or set the Regularizer attribute. 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 LShaped.Optimizer or by setting the Regularizer attribute.

...

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 LShaped.Optimizer or set the Regularizer attribute.. 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 LShaped.Optimizer or by setting the Regularizer attribute.

...

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, InfNorm, [ManhattanNorm][@ref])

...

LV

Factory object for LevelSet. Pass to regularize in LShaped.Optimizer or set the Regularizer attribute. 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 set the Aggregator attribute.

PartialAggregate

Factory object for PartialAggregation. Pass to aggregate in LShaped.Optimizer or set 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 set 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 set 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 set 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 LShaped.Optimizer or set the Consolidator attribute. 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 LShaped.Optimizer or by setting the Consolidator attribute.

...

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 LShaped.Optimizer.

NoConsolidation

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

RawConsolidationParameter

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

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 τ.