Interfaces

Abstract type for ProgressiveHedging penalty parameter.

Concrete subtypes determine how this penalty is used within the PH algorithm.

All concrete subtypes must implement the following methods:

• get_penalty_value(r::<ConcreteSubtype>, xhid::XhatID)::Float64
• is_initial_value_dependent(::Type{<ConcreteSubtype>})::Bool
• is_subproblem_dependent(::Type{<ConcreteSubtype>})::Bool
• is_variable_dependent(::Type{<ConcreateSubtype>})::Bool

If is_initial_value_dependent returns true, then the concrete subtype must implement

• process_penalty_initial_value(r::<ConcreteSubtype>, ph_data::PHData)::Nothing

If is_subproblem_dependent returns true, then the concrete subtype must implement

• process_penalty_subproblem(r::<ConcreteSubtype>, ph_data::PHData, scenario::ScenarioID, penalties::Dict{VariableID,Float64})::Nothing

Additionally, the concrete subproblem type must implement the function

• report_penalty_info(as::AbstractSubproblem, pp<:AbstractPenaltyParameter)::Dict{VariableID,Float64}

If is_variable_dependent returns true, then the concrete subtype must implement

• penalty_map(r::<ConcreteSubtype>)::Dict{XhatID,Float64}

If is_variable_dependent returns false, then the concrete subtype must implement

• get_penalty_value(r::<ConcreteSubtype>)::Float64

For more details, see the help on the individual functions.

Returns the constant penalty parameter value. Only required if is_variable_dependent returns false.

Returns the penalty value for the consensus variable associated with xhid.

Returns true if the penalty parameter value is dependent on the initial solutions of the subproblems.

Returns true if the penalty parameter value is dependent on any data or values in the subproblems (e.g., the coefficients in the objective function).

Returns true if the penalty parameter value may differ for different consensus variables.

Returns a mapping of consensus variable ids to penalty parameter values.

Only required if is_variable_dependent returns false.

Performs any computations for the penalty parameter based on the initial solutions of the subproblems.

Arguments

*r::AbstractPenaltyParameter : penalty parameter struct (replace with appropriate type) *phd::PHData : PH data structure used for obtaining any required variable values. See help on PHData for details on available functions.

Performs any computations for the penalty parameter based data or values from the subproblems.

This function is called before the initial solution of subproblems. Any accessing of variable values in this function may result in undefined behavior.

Arguments

• r::AbstractPenaltyParameter : penalty parameter struct (replace with appropriate type)
• phd::PHData : PH data structure used for obtaining any values or information not provided by scid and subproblem_dict
• scid::ScenarioID : scenario id from which subproblem_dict comes
• subproblem_dict::Dict{VariableID,Float64} : Mapping specifying a value needed from a subproblem used in the computation of the penalty parameter.

Abstract type for ProgressiveHedging subproblem types.

A concrete subtype handles all details of creating, solving and updating subproblems for ProgressiveHedging (PH). In particular, it handles all interaction with any modeling language that the subproblem is written in. See JuMPSubproblem for an implementation that uses JuMP as the optimization modeling language.

Variables and their values are identified and exchanged between PH and a Subproblem type using the VariableID type. A unique VariableID is associated with each variable in the subproblem by the Subproblem implementation by using the ScenarioID of the subproblem as well as the StageID to which this variable belongs. This combination uniquely identifies a node in the scenario tree to which the variable can be associated. Variables associated with the same node in a scenario tree and sharing the same name are assumed to be consensus variables whose optimal value is determined by PH. The final component of a VariableID is an Index which is just a counter assigned to a variable to differentiate it from other variables at the same node. See VariableID type for more details.

Any concrete subtype must implement the following functions:

• add_ph_objective_terms
• objective_value
• report_values
• report_variable_info
• solve_subproblem
• update_ph_terms

See help strings on each function for details on arguments, returned objects and expected performance of each function. See JuMPSubproblem for an example using JuMP.

To use warm_start=true the concrete subtype must also implement

• warm_start

See help on warm_start for more information. See JuMPSubproblem for an example using JuMP.

To use the extensive form functionality, the concrete subtype must implement

• ef_copy_model
• ef_node_dict_constructor

See the help on the functions for more details. See JuMPSubproblem for an example using JuMP. Note that the extensive form model is always constructed as a JuMP.Model object.

To use penalty parameter types other than ScalarPenaltyParameter, concrete subproblem types also need to implement

• report_penalty_info

See the help on individual penalty parameter types and report_penalty_info for more details.

To use lower bound computation functionality, the concrete subtype must also implement

• add_lagrange_terms
• update_lagrange_terms

See the help on these functions for more details.

Struct containing all information needed by PH about a variable (along with the variable id) to run the PH algorithm.

Fields

• name::String : User specified name of the variable
• is_integer::Bool : True if the variable is an integer or binary

add_ph_objective_terms(as::AbstractSubproblem,
                       vids::Vector{VariableID},
                       r::Union{Float64,Dict{VariableID,Float64}}
                       )::Dict{VariableID,Float64}

Create model variables for Lagrange multipliers and hat variables and add Lagrange and proximal terms to the objective function.

Returns mapping of the variable to any information needed from the subproblem to compute the penalty parameter. Only used if is_subproblem_dependent(typeof(r)) returns true.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)
• vids::Vector{VariableID} : list of VariableIDs which need ph terms created
• r::AbstractPenaltyParameter : penalty parameter on quadratic term

objective_value(as::AbstractSubproblem)::Float64

Return the objective value of the solved subproblem.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)

report_values(as::AbstractSubproblem,
              vars::Vector{VariableID}
              )::Dict{VariableID, Float64}

Return the variable values specified by vars.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)
• vars::Vector{VariableID} : collection of VariableIDs to gather values for

report_variable_info(as::AbstractSubproblem,
                     st::ScenarioTree
                     )::Dict{VariableID, VariableInfo}

Assign VariableIDs to all model variables and build a map from those ids to the required variable information (e.g., variable name). See VariableInfo help for details on required variable information.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)
• st::ScenarioTree : scenario tree for the entire PH problem

solve_subproblem(as::AbstractSubproblem)::MOI.TerminationStatusCode

Solve the subproblem specified by as and return the status code.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)

update_ph_terms(as::AbstractSubproblem,
                w_vals::Dict{VariableID,Float64},
                xhat_vals::Dict{VariableID,Float64}
                )::Nothing

Update the values of the PH variables in this subproblem with those given by w_vals and xhat_vals.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)
• w_vals::Dict{VariableID,Float64} : Values to update Lagrangian variables with
• xhat_vals::Dict{VariableID,Float64} : Values to update proximal variables with

warm_start(as::AbstractSubproblem)::Nothing

Use the values of previous solves non-PH variables as starting points of the next solve.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)

ef_copy_model(destination::JuMP.Model,
              original::AbstractSubproblem,
              scid::ScenarioID,
              scen_tree::ScenarioTree,
              node_dict::Dict{NodeID, Any}
              )

Copy the subproblem described by original to the extensive form model destination.

Arguments

• destination::JuMP.Model : extensive form of the model that is being built
• original::AbstractSubproblem : subproblem object (replace with appropriate type)
• scid::ScenarioID : ScenarioID corresponding to this subproblem
• scen_tree::ScenarioTree : scenario tree for the entire PH problem
• node_dict::Dict{NodeID, Any} : dictionary for transferring nodal information from one submodel to another

ef_node_dict_constructor(::Type{S}) where S <: AbstractSubproblem

Construct dictionary that is used to carry information between subproblems for ef_copy_model.

Arguments

• ::Type{S} : Subproblem type

report_penalty_info(as::AbstractSubproblem,
                    pp<:AbstractPenaltyParameter,
                    )::Dict{VariableID,Float64}

Returns mapping of variable to a value used to compute the penalty parameter.

This function must be implemented for any concrete penalty parameter type for which is_subproblem_dependent returns true and any concrete subproblem type wishing to use that penalty parameter. The mapping must contain all subproblem values needed for processing by process_penalty_subproblem. The returned mapping is handed unaltered to process_penalty_subproblem as the subproblem_dict argument.

Arguments

*as::AbstractSubproblem : subproblem object (replace with appropriate type) *pp<:AbstractPenaltyParameter : penalty parameter type

add_lagrange_terms(as::AbstractSubproblem,
                   vids::Vector{VariableID}
                   )::Nothing

Create model variables for Lagrange multipliers and adds the corresponding terms to the objective function.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)
• vids::Vector{VariableID} : list of VariableIDs which need Lagrange terms

See also add_ph_objective_terms.

update_lagrange_terms(as::AbstractSubproblem,
                      w_vals::Dict{VariableID,Float64}
                      )::Nothing

Update the values of the dual variables in this subproblem with those given by w_vals.

Arguments

• as::AbstractSubproblem : subproblem object (replace with appropriate type)
• w_vals::Dict{VariableID,Float64} : values to update Lagrange dual variables with

See also update_ph_terms.