GitHub

API Documentation

API Manual

PlasmoBenders.BendersAlgorithm — Type
BendersAlgorithm

Optimizer object for dual dynamic programming with graphs. Currently only implemented for linear tree structures.

Attributes include the following (where noted as dictionaries, these are mappings from the Benders subproblems to the data described)

  • graph - Plasmo OptiGraph for appplying Benders
  • root_object - node or subgraph in graph indicating where to start the Benders algorithm
  • is_MIP = Boolean indicating if the problem is a MIP or not
  • solve_order - vector of OptiNodes in the order that they are solved by Benders
  • solve_order_dict - dictionary mapping to a vector of all the "next objects" for a given object
  • parent_objects - dictionary mapping to the previous subproblem
  • max_iters - maximum number of Benders iterations
  • time_limit - maximum time (seconds) allowed for running Benders
  • tol - (absolute) termination tolerance between upper and lower bounds
  • current_iter - current iteration of Benders algorithm
  • M - lower bound for the cost-to-go function at each iteration
  • dual_iters - dictionary mapping optinodes to the corresponding dual values at each iteration; dual values come from solution of following node
  • primal_iters - dictionary mapping optinodes to the primal solutions of the complicating variables on the given node
  • phis - dictionary mapping optinodes to the objective of the immediately following node
  • phis_LR - dictionary mapping optinodes to the objective of the lagrangean (used for strenghtened cuts) relaxation of the following node; used for strengthened Benders cuts in MIPs
  • time_forward_pass - time spent in the forward pass (seconds)
  • time_backward_pass - time spent in the backward pass (seconds)
  • time_init - time initializing the optimizer (seconds)
  • time_iterations - vector of the times spent in each Iteration
  • comp_vars - dictionary mapping the node to a vector of its complicating variables
  • comp_var_map - dictionary mapping the node to a dictionary of complicating variables mapped to their index in comp_vars
  • var_copy_map - dictionary mapping the node to a dictionary mapping the complicating variables to their copies on the following node
  • objective_value - the final objective value (from upper bound)
  • lower_bounds - vector of lower bounds at each iteration
  • upper_bounds - vector of upper bounds at each iteration
  • regularize_data - regularization data object
  • binary_map - dictionary mapping the nodes to a vector of binary variables on the node
  • integer_map - dictionary mapping the nodes to a vector of integer variables on the node
  • last_solutions - dictionary mapping the nodes to a vector of the last solutions
  • var_solution_map - dictionary mapping the variables to their index on the last_solutions vector
  • var_to_graph_map - dictionary mapping the variables to their owning subproblem subgraph
  • feasibility_map - dictionary matching solve_order for whether a problem was feasible or not
  • options - solver options for Benders algorithm
  • ext - Dictionary for extending certain procedures
source
PlasmoBenders.BendersAlgorithm — Method
BendersAlgorithm(graph, root_object; kwargs...)

Function for creating the BendersAlgorithm object from graph. root_object must be an OptiNode or subgraph on graph. key ward arguments include the following

  • max_iters = 100 - maximum number of iterations
  • tol = 1e-7 - termination tolerance between upper and lower bounds
  • M = 0 - lower bound on cost-to-go estimator for each node
  • is_MIP = nothing - indicates if the problem is a MIP. If it is passed as nothing, PlasmoBenders will check to see if it is a MIP, and will set is_MIP accordingly
  • solver = nothing - if defined, this solver will be set for all subproblems
  • strengthened = false - whether to use strengthened Benders cuts (see https://doi.org/10.1007/s10107-018-1249-5.)
  • multicut = true - whether to use multicuts (rather than aggregated cuts) when applicable
  • feasibility_cuts = false - whether to allow feasibility cuts
  • regularize = false - whether to regularize solution of next iterates
  • parallelize_benders = false - whether to parallelize subproblem solution when the problem has a Benders-type structure defined
  • parallelize_forward = false - whether to parallelize forward pass if possible; not yet supported
  • parallelize_backward = false - whether to parallelize backward pass
  • add_slacks::Bool = false - whether to add slack variables to the linking constraints to help ensure feasibility between solutions; slack variables are penalized in objective
  • fix_slacks = false - whether to fix the slack variables to zero they only relax if a problem is infeasible
  • warm_start::Bool = true - whether to set the previous iterations solutions as the starting values for the next iterations forward pass
  • relaxed_init_cuts = false - whether to generate initial cuts by relaxing the problem and solving the whole problem; only applies for MILPs
  • slack_penalty = 1e6 - coefficient on slack variables in objective
  • regularize_param = 0.5 - regularization parameter; must be between 0 and 1
source
PlasmoBenders.BendersOptions — Type
BendersOptions

Options object for dual dynamic programming with graphs

Attributes include

  • strengthened::Bool - whether to use strengthened cuts
  • multicut::Bool - whether the problem should use aggregated or multiple cuts when there are multiple objects generating information in the forward pass
  • feasibility_cuts::Bool - whether to allow feasibility cuts if infeasible
  • regularize::Bool - whether to used regularization for getting next cuts
  • parallelize_benders::Bool - whether to parallelize Benders problems if applicable
  • parallelize_forward::Bool - whether to parallelize the forward pass if possible
  • parallelize_backward::Bool - whether to parallelize the backward pass if possible
  • add_slacks::Bool - whether to add slack variables to linking constraints
  • fix_slacks::Bool - whether to fix the slack variables to zero; slacks will be relaxed if the problem is infeasible
  • warm_start::Bool - whether to warm start the problem using the previous best solution
  • relaxed_init_cuts::Bool - whether to create some initial cuts by relaxing the problem and solving the full problem as an LP; only applies if the problem is a MIP
  • slack_penalty::Real - penalty for nonzero slacks; only applies for add_slacks = true
  • regularize_param::Real - parameter for regularization; essentially how far from optimal the solution can end up being for choosing the next iterates.
source
PlasmoBenders.RegularizeData — Type
RegularizeData

Data structure for storing regularization data

All attributes include a dictionary which is indexed by the subproblem objects of Benders

  • objective_function - the objective function of an object
  • ubs - value of the object's objective (without theta)
  • lbs - value of the object's objective (with theta)
  • best_ub - best upper bound
source
JuMP.value — Method
JuMP.value(opt::BendersAlgorithm, var::NodeVariableRef)

Returns the value of var from the BendersAlgorithm object. The value corresponds to the best upper bound of the optimizer.

source
JuMP.value — Method
JuMP.value(opt::BendersAlgorithm, vars::Vector{NodeVariableRef})

Returns a vector of variables contained in the vars vector from the BendersAlgorithm object. The values correspond to the best upper bound of the optimizer.

source
PlasmoBenders._add_Benders_cuts! — Method
_add_Benders_cuts!(optimizer::BendersAlgorithm)

Add Benders cuts to each nested problem; uses results from the backward pass and forward pass to create cuts.

source
PlasmoBenders._add_strengthened_cuts! — Method
_add_strengthened_cuts!(optimizer::BendersAlgorithm)

Add strengthened Benders cuts to each nested problem; Follows the process described by Zou et al., 2019 (https://doi.org/10.1007/s10107-018-1249-5) where the cuts come from a Lagrangian relaxation where the lagrange multipliers are the dual variables of the backward pass.

source
PlasmoBenders._backward_pass! — Method
_backward_pass!(optimizer::BendersAlgorithm)

Perform backward pass for a MIP problem. Backward pass can be done in parallel. Binary and integer variables are relaxed and the problem is solved to get the dual and objective values for producing Benders cuts. If strengthened = true, the stengthened cuts are ALSO added using the approach of Zou et al. https://doi.org/10.1007/s10107-018-1249-5.

source
PlasmoBenders._forward_pass! — Method
_forward_pass!(optimizer::BendersAlgorithm)

Runs the forward pass for Benders. Follows the node order in solve_order attribute. Save the primal information for complicating variables on each node. If it is not a MIP, also saves the dual and objective value information and adds the Benders cut. Returns the upper and lower bounds, where lower bound is only valid if the problem is not a MIP (otherwise the lower bound comes from the backward pass)

source
PlasmoBenders.get_tol — Method
get_tol(optimizer::BendersAlgorithm)

Return the value of the tol attribute from the BendersAlgorithm

source
PlasmoBenders.get_upper_bounds — Method
get_upper_bounds(optimizer::BendersAlgorithm; monotonic = true)

Return the value of upper_bounds from the BendersAlgorithm object. This is a vector of the upper bounds at each iteration. The upper bound returned by each iteration is not guaranteed to decrease monotonically. If monotonic=true, this function returns the best upper bound seen up to each iteration (rather than the value of the feasible solution seen at that iteration)

source
PlasmoBenders.run_algorithm! — Method
run_algorithm!(optimizer::PB.BendersAlgorithm; output::Bool = true, run_gc::Bool = false)

Optimize the graph in BendersAlgorithm by using the Benders algorithm. Keyword argument output indicates whether to print the upper/lower bounds and gap and each iteraiton. run_gc indicates whether to run the garbage collector after each iteraiton.

source
PlasmoBenders.set_add_slacks! — Method
set_add_slacks!(optimizer::BendersAlgorithm, val::Bool)

Set the value of add_slacks from the options field of the BendersAlgorithm to val

source
PlasmoBenders.set_fix_slacks! — Method
set_fix_slacks!(optimizer::BendersAlgorithm, val::Bool)

Set the value of fix_slacks from the options field of the BendersAlgorithm to val

source
PlasmoBenders.set_multicut! — Method
set_multicut!(optimizer::BendersAlgorithm, val::Bool)

Set the value of multicut from the options field of the BendersAlgorithm to val

source
PlasmoBenders.set_regularize! — Method
set_regularize!(optimizer::BendersAlgorithm, val::Bool)

Set the value of regularize from the options field of the BendersAlgorithm to val

source
PlasmoBenders.set_slack_penalty! — Method
set_slack_penalty!(optimizer::BendersAlgorithm, val::Real)

Set the value of slack_penalty from the options field of the BendersAlgorithm to val

source
PlasmoBenders.set_strengthened! — Method
set_strengthened!(optimizer::BendersAlgorithm, val::Bool)

Set the value of strengthened from the options field of the BendersAlgorithm to val

source
PlasmoBenders.set_warm_start! — Method
set_warm_start!(optimizer::BendersAlgorithm, val::Bool)

Set the value of warm_start from the options field of the BendersAlgorithm to val

source