EAGO Optimizer

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


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


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



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).


Storage for Input Parameters

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)


Internal Storage Structures

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.

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 EAGO Optimizer in the ext_type field.


Internal Problem Representations

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

  • _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...))

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 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


Interval Optimizer Subroutines


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


Extending EAGO

Functionality has been included that allows for extension's to EAGO's optimizer to readily be defined. This can be done in two ways first defining a new structure which is a subtype of EAGO.ExtensionType and overloading methods associated with this new structure. An instance of this new structure is provided to the EAGO.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 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 EAGO. 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).