Configuring the cut generation

As mentioned in Setting algorithmic parameters, we can choose between four general types of cut generation approaches, depending on the dual problem that is solved in the backward pass of SDDiP. For each approach, there exists a dedicated struct inheriting from DynamicSDDiP.AbstractDualityRegime.

Benders cuts

using DynamicSDDiP
mutable struct LinearDuality <: DynamicSDDiP.AbstractDualityRegime end

Using this type of struct to define a duality_regime within algo_params (see Setting algorithmic parameters) means that standard Benders cuts are generated by solving the LP duals of the subproblems.

Strengthened Benders cuts

using DynamicSDDiP
mutable struct StrengthenedDuality <: DynamicSDDiP.AbstractDualityRegime end

Using this type of struct to define a duality_regime within algo_params (see Setting algorithmic parameters) means that standard strengthened Benders cuts are generated by solving one Lagrangian relaxation for the coefficients of a standard Benders cut.

Standard Lagrangian cuts

using DynamicSDDiP
mutable struct LagrangianDuality <:  DynamicSDDiP.AbstractDualityRegime
    atol::Float64
    rtol::Float64
    iteration_limit::Int
    dual_initialization_regime:: DynamicSDDiP.AbstractDualInitializationRegime
    dual_bound_regime:: DynamicSDDiP.AbstractDualBoundRegime
    dual_solution_regime:: DynamicSDDiP.AbstractDualSolutionRegime
    dual_choice_regime:: DynamicSDDiP.AbstractDualChoiceRegime
    dual_status_regime:: DynamicSDDiP.AbstractDualStatusRegime
    copy_regime:: DynamicSDDiP.AbstractCopyRegime
    augmented::Bool
end

Using this type of struct to define a duality_regime within algo_params (see Setting algorithmic parameters) means that standard Lagrangian cuts as known from the original SDDiP work (see SDDiP paper) are generated. This is done by solving the Lagrangian dual problems obtained from relaxing the copy constraints within the subproblems.

This type of duality_regime can be configured with several parameters that are explained below.

New Lagrangian cuts

mutable struct UnifiedLagrangianDuality <: DynamicSDDiP.AbstractDualityRegime
    atol::Float64
    rtol::Float64
    iteration_limit::Int
    dual_initialization_regime::DynamicSDDiP.AbstractDualInitializationRegime
    dual_bound_regime::DynamicSDDiP.AbstractDualBoundRegime
    dual_solution_regime::DynamicSDDiP.AbstractDualSolutionRegime
    dual_choice_regime::DynamicSDDiP.AbstractDualChoiceRegime
    dual_status_regime::DynamicSDDiP.AbstractDualStatusRegime
    normalization_regime::DynamicSDDiP.AbstractNormalizationRegime
    dual_space_regime::DynamicSDDiP.AbstractDualSpaceRegime
    copy_regime::DynamicSDDiP.AbstractCopyRegime
    user_dual_objective_bound::Union{Nothing,Float64}
    user_dual_multiplier_bound::Union{Nothing,Float64}
end

Using this type of struct to define a duality_regime within algo_params (see Setting algorithmic parameters) means that the new Lagrangian cuts from our paper are generated, i.e. deep Lagrangian cuts or LN Lagrangian cuts. This is done by considering specific normalized Lagrangian dual problems.

Again, this type of duality_regime can be configured with several parameters that are explained below. Most importantly, we can choose a normalization_regime that defines which type of normalization is applied.

Normalizing the dual problem

When UnifiedLagrangianDuality is used, we can specify a normalization_regime that should be used. We have the following options:

• L₁_Deep: Normalization using the 1-norm.
• L₂_Deep: Normalization using the 2-norm. Note that we have not tested this case, as it requires to solve quadratic subproblems.
• L∞_Deep: Normalization using the supremum norm.
• L₁∞_Deep: Normalization using a convex combination of the 1-norm and the supremum norm (both weighted 50 percent). This can be interpreted as a linear approximation of the 2-norm.
• ChenLuedtke: Uses a special normalization from Chen and Luedtke's paper. This should be combined with a restriction of the dual space (see below).
• Core_Midpoint: Linear normalization in combination with the Mid heuristic from the paper to identify core points. This is based on computing the midpoint of the (confexified) state space, and thus requires that all state variables are bounded from below and above.
• Core_Epsilon: Linear normalization in combination with the Eps heuristic from the paper to identify core points. This is based on perturbation of the incumbent.
• Core_Relint: Linear normalization in combination with the Relint heuristic from the paper to identify core points. This uses the solution of an auxiliary feasibility problem.
• Core_In_Out: Linear normalization in combination with a heuristic not presented in the paper. This heuristic uses a convex combination of the previous core point and the current incumbent, similar to the in-out-strategy for cutting-plane methods.
• Core_Conv: Linear normalization in combination with the Conv heuristic from the paper to identify core points. This is based on considering convex combinations of feasible points and function values.

For more details on the normalized dual problems that are solved we refer to our paper.

using DynamicSDDiP
mutable struct L₁_Deep <: DynamicSDDiP.AbstractNormalizationRegime end
mutable struct L₂_Deep <: DynamicSDDiP.AbstractNormalizationRegime end
mutable struct L∞_Deep <: DynamicSDDiP.AbstractNormalizationRegime end
mutable struct L₁∞_Deep <: DynamicSDDiP.AbstractNormalizationRegime end
mutable struct ChenLuedtke <: DynamicSDDiP.AbstractNormalizationRegime end

The normalization regimes using a linear normalization deserve some more attention, as they come with some parameters.

using DynamicSDDiP
mutable struct Core_Midpoint <: DynamicSDDiP.AbstractNormalizationRegime
    copy_regime::DynamicSDDiP.AbstractCopyRegime
    integer_regime::DynamicSDDiP.AbstractIntegerRegime
    unbounded_regime::DynamicSDDiP.AbstractUnboundedRegime
    improvement_regime::DynamicSDDiP.AbstractImprovementRegime
    normalize_direction::Bool
end

• copy_regime: This parameter defines which constraints are imposed for the local copy of the state variable when solving a subproblem to evaluate the value function for the core point candidate. We always used StateSpaceCopy in our experiments. See also Handling copy constraints.
• integer_regime: This parameter can be either set to IntegerRelax or to NoIntegerRelax. It defines whether integer requirements are relaxed when solving a subproblem to evaluate the value function for the core point candidate. This relaxation might be helpful to avoid that the auxiliary subproblem becomes infeasible, for instance if integer requirements are no longer satisfiable with the given core point candidate. This should only be relevant for integer or binary state variables.
• unbounded_regime: This parameter defines which mitigation approach is used whenever some checks indicate that the core point candidate might not be an actual core point of the epigraph. It can be chosen to
  • Unbounded_Opt_None: No mitigation approach is taken; we just proceed with the common procedure. The dual problem might become unbounded if the core point candidate is indeed no core point, which would result in the algorithm to terminate with an error.
  • Unbounded_Opt_SB: Instead of generating an LN Lagrangian cut, a strengthened Benders cut is generated. This is the option that we used in our experiments for the paper.
  • Unbounded_Opt_Bound: We introduce some user-defined bounds (either on the objective or the dual multipliers) to artificially bound the normalized dual problem and avoid unboundedness.
• improvement_regime: This parameter defines whether we try to improve the last component of the candidate core point to avoid infeasibilities. This can be either NoImprovement, EpiState (using $\theta_t^i$) or PrimalObj (using $\underline{Q}_n^{i+1}(x_{a(n)}^i)$).
• normalize_direction: This parameter defines whether the direction obtained from the core point candidate and the incumbent should be scaled to length 1 before using it to define the normalized dual problem.

Specifically for Core_Epsilon we have the additional Float64 parameter perturb which allows the user to specify the perturbation of the incumbent.

Specifically for Core_Conv we have the additional Float64 parameter lambda which allows the user to specify the convex combination that is used. In the paper, this parameter is called $\alpha$.

Initializing the dual problem

When UnifiedLagrangianDuality or LagrangianDuality is used, we can specify a dual_initialization_regime that should be used.

We have the following options:

• ZeroDuals: Dual multipliers are initialized to 0.
• LPDuals: The LP relaxation is solved first and the dual multipliers are initialized to the obtained optimal solution (Benders coefficients).

using DynamicSDDiP
mutable struct ZeroDuals <: DynamicSDDiP.AbstractDualInitializationRegime end
mutable struct LPDuals <: DynamicSDDiP.AbstractDualInitializationRegime end

Solving the dual problem

When UnifiedLagrangianDuality or LagrangianDuality is used, we can specify a dual_solution_regime that should be used.

We have the following options:

• Kelley: The Lagrangian dual is solved using Kelley's classical cutting-plane method.
• LevelBundle: The Lagrangian dual is solved using a level bundle method.

using DynamicSDDiP
mutable struct Kelley <: DynamicSDDiP.AbstractDualSolutionRegime
    use_subopt_sol::Bool
end

mutable struct LevelBundle <: DynamicSDDiP.AbstractDualSolutionRegime
    level_factor::Float64
    switch_to_kelley::Bool
    use_subopt_sol::Bool
end

Parameter use_subopt_sol allows to add additional cuts obtained from suboptimal solutions of the inner problem to the outer problem. We did not use this in our experiments for the paper.

Parameter level_factor is a standard parameter for level bundle methods. It was always chosen as 0.5 in our experiments.

Parameter switch_to_kelley allows to switch to a standard cutting-plane method once we detect numerical issues in the quadratic auxiliary problem. This was always set to true in our experiments for the paper.

Handling numerical issues

Cutting-plane methods can be prone to numerical issues. To avoid that SDDiP stops because a single Lagrangian dual problem cannot be solved, the user can define a dual_status_regime accordingly.

We have the following options:

• Rigorous: This means that whenever a dual problem cannot be solved, the algorithm terminates with an error.
• Lax: This means that whenever a dual problem cannot be solved, e.g. due to numerical issues, the last values of the multipliers are used to define a cut for the value function. Then SDDiP proceeds as usual. Recall that Lagrangian cuts are not guaranteed to be tight but still valid for any choice of dual multipliers.

using DynamicSDDiP
mutable struct Rigorous <: DynamicSDDiP.AbstractDualStatusRegime end
mutable struct Lax <: DynamicSDDiP.AbstractDualStatusRegime end

In our experiments for the paper, we always used option Lax.

Handling degeneracy

Lagrangian dual problems for mixed-integer problems tend to degeneracy, i.e. having infinitely many optimal solutions. However, different optimal solutions can yield cuts of quite different approximation strength. It is a topic of ongoing research to select dual solutions that yield the strongest possible cuts.

To address the issue of degeneracy, our code allows to define a dual_choice_regime.

We have the following options:

• StandardChoice: The Lagrangian dual is solved using the method defined in dual_solution_regime. The obtained solution (possibly degenerate) is used to define a Lagrangian cut.
• MinimalNormChoice: After the Lagrangian dual is solved, we solve a second auxiliary problem where we minimize the 1-norm of the dual multipliers over all optimal solutions. Whereas this can help to yield stronger Lagrangian cuts in the light of degeneracy, it also comes with substantial additional effort.

using DynamicSDDiP
mutable struct StandardChoice <: DynamicSDDiP.AbstractDualChoiceRegime end
mutable struct MinimalNormChoice <: DynamicSDDiP.AbstractDualChoiceRegime end

In our experiments for the paper, we only used MinimalNormChoice when choosing L∞_Deep as the normalization_regime. This decision was based on preliminary tests.

Restricting the dual space

Our code allows to follow the proposition from Chen and Luedtke's paper to restrict the dual space to a span of Benders cut coefficients. To this end, we can define a dual_space_regime.

We have the following options:

• NoDualSpaceRestriction: The standard Lagrangian dual is solved.
• BendersSpanSpaceRestriction: The feasible space in the Lagrangian dual is restricted to a span of the last K Benders multipliers, where K is a parameter defined by the user.

using DynamicSDDiP
mutable struct NoDualSpaceRestriction <: DynamicSDDiP.AbstractDualSpaceRegime end
mutable struct BendersSpanSpaceRestriction <: DynamicSDDiP.AbstractDualSpaceRegime
    K::Int64
    cut_type::Symbol #:Benders or :Lagrange
end

User bounds

The user is also allowed to specify bounds on the dual multipliers user_dual_multiplier_bound or the objective of the dual user_dual_objective_bound.

The parameter dual_bound_regime is then used to control how these bounds are used.

• ValueBound: This means that the optimal value of the Lagrangian dual is bounded using the optimal value of the primal problem (as it is done in SDDP.jl). However, the dual multipliers are not bounded.
• NormBound: This means that each component of the dual multipliers is bounded from below and above. This makes most sense when using a regularization and choosing a dual bound related to the regularization parameter sigma.
• BothBounds: This means that both approaches are combined.

using DynamicSDDiP
abstract type AbstractDualBoundRegime end
mutable struct ValueBound <: DynamicSDDiP.AbstractDualBoundRegime end
mutable struct NormBound <: DynamicSDDiP.AbstractDualBoundRegime end
mutable struct BothBounds <: DynamicSDDiP.AbstractDualBoundRegime end

When no user_dual_multiplier_bound or user_dual_objective_bound are specified, the bounds are set to trivial default values.

In our experiments, we usually used BothBounds but with trivial bounds.

Dealing with numerical issues

We have added a few measures to avoid redundant cuts and numerical issues within SDDiP.

• cut_away: Per default we use cut_away_approach = true in CutGenerationRegime. This way, a new cut is only added to the subproblem if the previous incumbent $(x_{a(n)}^i, \theta_n^i)$ is cut away by at least cut_away_tol, which is set to 1e-4 per default.
• add_cut_flag: Cuts are also not added if

  • \[\pi_{n0} \approx 0\]

    because a very small scaling factor in the cut can lead to numerical issues,
  • the optimal value of the normalized Lagrangian dual is very close to 0,
  • the coefficients of the linear normalization satisfy $(u_n, u_{n0}) \approx 0$.

This page was generated using Literate.jl.