GitHub

EAGO Optimizer

The Optimizer object holds all algorithm solution information. A description of all user-facing options has been provided in the docstring.

EAGO.Optimizer

EAGO.Optimizer — Type
mutable struct Optimizer{Q, S, T} <: MathOptInterface.AbstractOptimizer

The highest level optimizer object used by EAGO to solve problems during the optimization routine. Additional options and temporary storage are located in the _global_optimizer::GlobalOptimizer{Q,S,T} field. Parameters which are expected to be constant over the entire solve are stored in the _parameters::EAGOParameters field. Some user-facing keywords not in the EAGOParameters field include:

  • relaxed_optimizer::MOI.AbstractOptimizer: An instance of the optimizer used to solve the relaxed subproblems (default = Cbc.Optimizer()). Located in subsolver_block::SubSolvers{Q,S,T}.
  • upper_optimizer::MOI.AbstractOptimizer: Optimizer used to solve upper bounding problems (default = Ipopt.Optimizer()). Located in subsolver_block::SubSolvers{Q,S,T}.
  • ext::ExtensionType: Holds an instance of a subtype of EAGO.ExtensionType, used to define new custom subroutines (default = DefaultExt()). Located in subsolver_block::SubSolvers{Q,S,T}.
  • enable_optimize_hook::Bool: Specifies that the user-defined optimize_hook! function should be called rather than use the standard EAGO optimization routines. Located in Optimizer and _global_optimizer::GlobalOptimizer{Q,S,T}.
  • obbt_variable_values::Vector{Bool}: Variables to perform OBBT on (default: all variables in nonlinear expressions). Located in _global_optimizer::GlobalOptimizer{Q,S,T}.

Descriptions of all Optimizer fields available in extended help.

Extended Help

  • subsolver_block::SubSolvers{Q, S, T} where {Q, S, T}: Holds definitions of the relaxed and upper optimizers, as well as any user-defined extension types

  • enable_optimize_hook::Bool: Specifies that the optimize_hook! function should be called rather than throw the problem to the standard routine

  • ext::Union{Nothing, T} where T: (Deprecated, use subsolver_block instead) Storage for custom extension types

  • _auxiliary_variable_info::Union{Nothing, EAGO._AuxVarData}: Information on any auxiliary variables

  • _global_optimizer::GlobalOptimizer{Q, S, T} where {Q, S, T}: Additional options and temporary storage for solving optimization problems

  • _input_problem::InputProblem: Expressions and constraints added to the EAGO model (not directly used for relaxations)

  • _working_problem::ParsedProblem: Expressions and problem descriptions that EAGO uses to formulate relaxed problems

  • _parameters::EAGOParameters: Parameters that do not change during a global solve

  • _optimizer_attributes_set::Vector{MathOptInterface.AbstractOptimizerAttribute}: Set of optimizer attributes

  • _termination_status_code::MathOptInterface.TerminationStatusCode: The MathOptInterface-compliant completion status code

  • _result_status_code::MathOptInterface.ResultStatusCode: Value indicating the feasibility status of the result

  • _run_time::Float64: Optimization run time

  • _objective_value::Float64: The objective value of the primal solution

  • _objective_bound::Float64: The best-known bound on the optimal objective value

  • _relative_gap::Float64: The gap between the upper and lower bound, relative to the bound with the larger magnitude

  • _iteration_count::Int64: The number of iterations the branch-and-bound algorithm has completed

  • _node_count::Int64: The number of nodes in the stack

source

EAGO Specific Functions and Operators

EAGO supports a number of functions and operators that for which specialized relaxation routines are available. These can be registered and added to a JuMP model using the function:

EAGO.register_eago_operators! — Method

registereagooperators!

Registers all nonstandard nonlinear terms available in EAGO in a JuMP. Uses of these is generally preferable in EAGO as the relaxations EAGO will generate will usually be tighter (speeding up convergence time). Note that this will work can be used by other nonlinear solvers (Ipopt for instance).

source

Storage for Input Parameters

EAGO.EAGOParameters — Type
mutable struct EAGOParameters

Storage for parameters that do not change during a global solve.

  • presolve_scrubber_flag::Bool: Should EAGO attempt to remove type-assert issues for user-defined functions (default = false)

  • presolve_to_JuMP_flag::Bool: Create and use DAG representations of user-defined functions (default = false)

  • presolve_flatten_flag::Bool: Rerrange the DAG using registered transformations (default = false)

  • conic_convert_quadratic::Bool: Attempt to bridge convex constraint to second-order cone (default = false)

  • log_on::Bool: Turn logging on; record global bounds, node count, and run time. Additional options are available for recording information specific to subproblems (default = false)

  • log_subproblem_info::Bool: Turn on logging of times and feasibility of subproblems (default = false)

  • log_interval::Int64: Log data every log_interval iterations (default = 1)

  • verbosity::Int64: The amount of information that should be printed to console while solving. Values range from 0 - 4: 0 is silent, 1 shows iteration summary statistics only, 2-4 show varying degrees of detail about calculations within each iteration (default = 1)

  • output_iterations::Int64: Display summary of iteration to console every output_iterations (default = 1000)

  • header_iterations::Int64: Display header for summary to console every output_iterations (default = 100000)

  • branch_cvx_factor::Float64: Convex coefficient used to select branch point. Branch point is given by branch_cvx_factor*xmid + (1-branch_cvx_factor)*xsol (default = 0.25)

  • branch_offset::Float64: Minimum distance from bound to have branch point, normalized by width of dimension to branch on (default = 0.15)

  • branch_pseudocost_on::Bool: Indicate that pseudocost branching should be used (default = false)

  • branch_variable::Vector{Bool}: Variables to branch on (default is all nonlinear)

  • branch_max_repetitions::Int64: [FUTURE FEATURE, NOT CURRENTLY IMPLEMENTED] Number of times to repeat node processing prior to branching (default = 4)

  • branch_repetition_tol::Float64: [FUTURE FEATURE, NOT CURRENTLY IMPLEMENTED] Volume ratio tolerance required to repeat processing the current node (default = 0.9)

  • node_limit::Int64: Maximum number of nodes (default = 1E7)

  • time_limit::Float64: Maximum CPU time in seconds (default = 3600)

  • iteration_limit::Int64: Maximum number of iterations (default 1E9)

  • absolute_tolerance::Float64: Absolute tolerance for termination (default = 1E-3)

  • relative_tolerance::Float64: Relative tolerance for termination (default = 1E-3)

  • absolute_constraint_feas_tolerance::Float64: Absolute constraint feasibility tolerance (default = 1E-8)

  • cp_depth::Int64: Depth in B&B tree above which constraint propagation should be disabled (default = 0)

  • cp_repetitions::Int64: Number of times to repeat forward-reverse pass routine (default = 0)

  • cp_tolerance::Float64: Disable constraint propagation if the ratio of new node volume to beginning node volume exceeds this number (default = 0.99)

  • cp_interval_only::Bool: Use only valid interval bounds during constraint propagation (default = false)

  • obbt_depth::Int64: Depth in B&B tree above which OBBT should be disabled (default = 6)

  • obbt_repetitions::Int64: Number of repetitions of OBBT to perform in preprocessing (default = 3)

  • obbt_aggressive_on::Bool: Turn on aggresive OBBT (default = true)

  • obbt_aggressive_max_iteration::Int64: Maximum iteration to perform aggresive OBBT (default = 2)

  • obbt_aggressive_min_dimension::Int64: Minimum dimension to perform aggresive OBBT (default = 2)

  • obbt_tolerance::Float64: Tolerance to consider bounds equal (default = 1E-10)

  • fbbt_lp_depth::Int64: Depth in B&B tree above which linear FBBT should be disabled (default = 1000)

  • fbbt_lp_repetitions::Int64: Number of repetitions of linear FBBT to perform in preprocessing (default = 3)

  • dbbt_depth::Int64: Depth in B&B tree above which duality-based bound tightening should be disabled (default = 1E10)

  • dbbt_tolerance::Float64: New bound is considered equal to the prior bound if within dbbt_tolerance (default = 1E-8)

  • relax_tag::RelaxTag: RelaxTag used to specify type of McCormick operator (default = NS())

  • subgrad_tighten::Bool: Perform tightening of interval bounds using subgradients at each factor in each nonlinear tape during a forward pass (default = true)

  • reverse_subgrad_tighten::Bool: Perform tightening of interval bounds using subgradients at each factor in each nonlinear tape during a reverse pass (default = false)

  • subgrad_tol::Float64: Outer-round computed subgradient bounds by this amount (default = 1E-10)

  • mul_relax_style::Int64: Select the type of relaxation to use for the bilinear term (multiplication): 0 corresponds to a standard McCormick arithmetic approach. Settings 1-3 augment the standard McCormick relaxation with implied apriori relaxations: (1) corresponds to a subgradient-based apriori relaxation approach; (2) corresponds to an affine arithmetic-based apriori approach; and (3) corresponds to a enumerative apriori relaxation-based approach (default = 0)

  • cut_min_iterations::Int64: Minimum number of cuts at each node to attempt (unsafe cuts not necessarily added) (default = 2)

  • cut_max_iterations::Int64: Maximum number of cuts at each node to attempt (default = 8)

  • cut_tolerance_abs::Float64: Absolute tolerance checked for continuing cut (default = 1E-6)

  • cut_tolerance_rel::Float64: Relative tolerance checked for continuing cut (default = 1E-3)

  • cut_safe_on::Bool: Use tolerances to determine safe cuts in a Khajavirad 2018 manner (default = true)

  • cut_safe_l::Float64: Lower tolerance for safe-lp cut, Khajavirad 2018 (default = 1E-7)

  • cut_safe_u::Float64: Upper tolerance for safe-lp cut, Khajavirad 2018 (default = 1E7)

  • cut_safe_b::Float64: Constant tolerance for safe-lp cut, Khajavirad 2018 (default = 1E9)

  • upper_bounding_depth::Int64: Solve upper problem for every node with depth less than upper_bounding_depth, and otherwise solve upper problems with a probability of (1/2)^(depth-upper_bounding_depth) (default = 8)

  • domain_violation_guard_on::Bool: (Unused) Protect against domain violation (default = false)

  • domain_violation_ϵ::Float64: (Unused) Amount about a domain violation to ignore when propagating bounds (default = 1E-9)

  • user_solver_config::Bool: If true, EAGO forgoes its default configuration process for subsolvers (default = false)

  • integer_abs_tol::Float64: Absolute tolerance used to check for integrality of decision variables (default = 1E-9)

  • integer_rel_tol::Float64: Relative tolerance used to check for integrality of decision variables (default = 1E-9)

  • force_global_solve::Bool: Ignore EAGO's ability to parse problem types and force it to run global optimization (default = false)

  • unbounded_check::Bool: Check that all branching variables have finite bounds and set them to +/- 1E10 if not (default = true)

source

Internal Storage Structures

EAGO.VariableInfo — Type
struct VariableInfo{T<:AbstractFloat}

A structure used to store information related to the bounds assigned to each variable.

  • is_integer::Bool: Is the variable integer valued?

  • has_lower_bound::Bool: Boolean indicating whether a finite lower bound exists.

  • has_upper_bound::Bool: Boolean indicating whether a finite upper bound exists.

  • is_fixed::Bool: Boolean indicating if variable is fixed to a finite value.

  • has_constraints::Bool: Boolean indicating that constraints have been set

  • lower_bound::AbstractFloat: Lower bound. May be -Inf.

  • upper_bound::AbstractFloat: Upper bound. May be Inf.

source
EAGO.ExtensionType — Type
abstract type ExtensionType

An abstract type the subtypes of which are associated with functions method overloaded for new extensions. An instance of this is the DefaultExt <: ExtensionType structure in the ext_type field of the Optimizer.

source

Internal Problem Representations

EAGO.InputProblem — Type
mutable struct InputProblem

A structure used to hold objectives and constraints added to the EAGO model. The constraints generally aren't used for relaxations.

All field information available in extended help.

Extended Help

  • _variable_count::Int64: Count for the number of variables

  • _variable_names::Dict{MathOptInterface.VariableIndex, String}: Dictionary containing variable indices and their names

  • _constraint_count::Int64: Count for the number of constraints

  • _vi_leq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.LessThan{Float64}}, Tuple{MathOptInterface.VariableIndex, MathOptInterface.LessThan{Float64}}}

  • _vi_geq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.GreaterThan{Float64}}, Tuple{MathOptInterface.VariableIndex, MathOptInterface.GreaterThan{Float64}}}

  • _vi_eq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.EqualTo{Float64}}, Tuple{MathOptInterface.VariableIndex, MathOptInterface.EqualTo{Float64}}}

  • _vi_it_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64}}, Tuple{MathOptInterface.VariableIndex, MathOptInterface.Interval{Float64}}}

  • _vi_zo_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.ZeroOne}, Tuple{MathOptInterface.VariableIndex, MathOptInterface.ZeroOne}}

  • _vi_int_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.Integer}, Tuple{MathOptInterface.VariableIndex, MathOptInterface.Integer}}

  • _linear_leq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, Tuple{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}}

  • _linear_geq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, Tuple{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}}

  • _linear_eq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.EqualTo{Float64}}, Tuple{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.EqualTo{Float64}}}

  • _quadratic_leq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.LessThan{Float64}}, Tuple{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.LessThan{Float64}}}

  • _quadratic_geq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, Tuple{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.GreaterThan{Float64}}}

  • _quadratic_eq_constraints::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.EqualTo{Float64}}, Tuple{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.EqualTo{Float64}}}

  • _conic_second_order::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.SecondOrderCone}, Tuple{MathOptInterface.VectorOfVariables, MathOptInterface.SecondOrderCone}}

  • _linear_leq_primal::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, Float64}

  • _linear_geq_primal::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, Float64}

  • _linear_eq_primal::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.EqualTo{Float64}}, Float64}

  • _quadratic_leq_primal::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.LessThan{Float64}}, Float64}

  • _quadratic_geq_primal::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, Float64}

  • _quadratic_eq_primal::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.EqualTo{Float64}}, Float64}

  • _linear_leq_prob_to_ip::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}}

  • _linear_geq_prob_to_ip::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}}

  • _linear_eq_prob_to_ip::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.EqualTo{Float64}}, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.EqualTo{Float64}}}

  • _quadratic_leq_prob_to_ip::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.LessThan{Float64}}, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.LessThan{Float64}}}

  • _quadratic_geq_prob_to_ip::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.GreaterThan{Float64}}}

  • _quadratic_eq_prob_to_ip::Dict{MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.EqualTo{Float64}}, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarQuadraticFunction{Float64}, MathOptInterface.EqualTo{Float64}}}

  • _objective::Union{Nothing, MathOptInterface.VariableIndex, MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.ScalarQuadraticFunction{Float64}}: Storage for the objective function

  • _nlp_data::Union{Nothing, MathOptInterface.NLPBlockData}: Storage for NLP constraints (set by MOI.set(m, ::NLPBlockData...) in moi_wrapper.jl)

  • _optimization_sense::MathOptInterface.OptimizationSense: Objective sense information (set by MOI.set(m, ::ObjectiveSense...))

source
EAGO.ParsedProblem — Type
mutable struct ParsedProblem

A structure used to store expressions and problem descriptions EAGO uses to formulate relaxed problems.

All field information available in extended help.

Extended Help

  • _problem_type::Union{Nothing, EAGO.DIFF_CVX, EAGO.LP, EAGO.MILP, EAGO.MINCVX, EAGO.MISOCP, EAGO.SOCP}: Problem classification (set in parse_classify_problem!)

  • _objective_saf::MathOptInterface.ScalarAffineFunction{Float64}: Stores the objective and is used for constructing linear affine cuts

  • _objective::Union{Nothing, MathOptInterface.VariableIndex, EAGO.AffineFunctionIneq, EAGO.BufferedQuadraticIneq, EAGO.BufferedNonlinearFunction}: Storage for the objective function

  • _optimization_sense::MathOptInterface.OptimizationSense: Objective sense information (set by MOI.set(m, ::ObjectiveSense...))

  • _saf_leq::Vector{EAGO.AffineFunctionIneq}

  • _saf_eq::Vector{EAGO.AffineFunctionEq}

  • _sqf_leq::Vector{EAGO.BufferedQuadraticIneq}

  • _sqf_eq::Vector{EAGO.BufferedQuadraticEq}

  • _conic_second_order::Vector{EAGO.BufferedSOC}

  • _nlp_data::Union{Nothing, MathOptInterface.NLPBlockData}

  • _nonlinear_constr::Vector{EAGO.BufferedNonlinearFunction}

  • _relaxed_evaluator::Evaluator

  • _variable_info::Vector{VariableInfo{Float64}}: Variable information (set in initial_parse!)

  • _variable_count::Int64: Count for the number of variables

source

Interval Optimizer Subroutines

EAGO.initial_parse! — Method
initial_parse!(m::Optimizer{R, S, T})

Translate the input problem to the working problem. Any checks or optional manipulation are left to the presolve stage.

source

Extending EAGO

Functionality has been included that allows for extensions to EAGO's Optimizer to be readily defined. This can be done in two ways first defining a new structure which is a subtype of ExtensionType and overloading methods associated with this new structure. An instance of this new structure is provided to the Optimizer using the ext_type keyword. This results in EAGO now dispatch to the new methods rather than the generally defined methods for the parent type. For a complete example, the reader is directed to the interval bounding example and the quasiconvex example. Alternatively, the user can overload the optimize_hook! for this subtype which will entirely circumvent the default global solution routine. Additional information can be stored in the ext field of the Optimizer. In order to allow for compatibility between packages the user is encouraged to append their extension name to the start of each variable name (e.g. newext_newdata).