L-shaped solvers

Documentation for StochasticPrograms.jl's L-shaped solvers.

Index

API

StochasticPrograms.LShaped.LShapedAlgorithmType
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.

...

source
StochasticPrograms.LShaped.AggregatorType
Aggregator

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

source
StochasticPrograms.LShaped.OptimizerType
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.

...

source
StochasticPrograms.LShaped.set_aggregation_attributesMethod
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.

source
StochasticPrograms.LShaped.set_consolidation_attributesMethod
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.

source
StochasticPrograms.LShaped.set_regularization_attributesMethod
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.

source

Execution

StochasticPrograms.LShaped.SerialExecutionType
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.

source
StochasticPrograms.LShaped.SynchronousExecutionType
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.

source
StochasticPrograms.LShaped.AsynchronousExecutionType
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.

source

Feasibility

Integers

StochasticPrograms.LShaped.CombinatorialCutsType
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.

...

source
StochasticPrograms.LShaped.ConvexificationType
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.

...

source

Regularization

StochasticPrograms.LShaped.set_regularization_attributesFunction
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.

source
StochasticPrograms.LShaped.RegularizedDecompositionType
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])

...

source
StochasticPrograms.LShaped.TrustRegionType
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.

...

source
StochasticPrograms.LShaped.LevelSetType
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])

...

source

Aggregation

StochasticPrograms.LShaped.set_aggregation_attributesFunction
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.

source
StochasticPrograms.LShaped.FullAggregationMethod
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.

source
StochasticPrograms.LShaped.DynamicAggregationType
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

...

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

...

source
StochasticPrograms.LShaped.ClusterAggregationType
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

...

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

...

source
StochasticPrograms.LShaped.HybridAggregationType
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 τ

...

source

Selection rules

StochasticPrograms.LShaped.SelectClosestType
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

source

Cluster rules

StochasticPrograms.LShaped.HierarchicalType
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

source

Distance measures

Consolidation

StochasticPrograms.LShaped.set_consolidation_attributesFunction
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.

source
StochasticPrograms.LShaped.ConsolidationType
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

...

source
StochasticPrograms.LShaped.at_toleranceMethod
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 τ.

source