GitHub

Domain Reduction

Duality-Based Bound Tightening

Variable bound tightening based on the duality multipliers are supported.

EAGO.variable_dbbt! — Function
variable_dbbt!(
    n::NodeBB,
    mult_lo::Vector{Float64},
    mult_hi::Vector{Float64},
    LBD::Float64,
    UBD::Float64,
    nx::Int64
)

Tighten the bounds of the _current_node using the current global upper bound and the duality information obtained from the relaxation.

source

Special Forms

Bound tightening for linear forms, univariate quadratic forms, and bivariate quadratic forms are also supported.

EAGO.fbbt! — Function
fbbt!(m::GlobalOptimizer, f::T)

Performs feasibility-based bound tightening on a back-end constraint and returns true if it is feasible or false if it is infeasible.

Options for T (all are subtypes of AbstractEAGOConstraint):

  • AffineFunctionIneq
  • AffineFunctionEq
source

Constraint Propagation

EAGO contains a constraint propagation architecture that supported forward and reverse evaluation of set-valued functions on the directed acyclic graph. The interval contractor and reverse McCormick relaxation-based contractors are currently available.

EAGO.set_constraint_propagation_fbbt! — Function
set_constraint_propagation_fbbt!(
    m::GlobalOptimizer{R, S, Q<:ExtensionType}
) -> Bool

Performs bound tightening based on forward/reverse interval and/or McCormick passes. This routine resets the current node with new interval bounds.

source

Optimization-Based Bound Tightening

EAGO makes use of an optimization-based bound tightening scheme using filtering and greedy ordering as detailed in [1].

EAGO.obbt! — Function
obbt!(m::GlobalOptimizer{R, S, Q<:ExtensionType}) -> Bool

Performs OBBT with filtering and greedy ordering as detailed in: Gleixner, A.M., Berthold, T., Müller, B. et al. J Glob Optim (2017) 67: 731. https://doi.org/10.1007/s10898-016-0450-4

source
EAGO.trivial_filtering! — Method
trivial_filtering!(
    m::GlobalOptimizer{R, S, Q<:ExtensionType},
    n::NodeBB
)

Excludes OBBT on variable indices that are tight for the solution of the relaxation.

source
EAGO.aggressive_filtering! — Method
aggressive_filtering!(
    m::GlobalOptimizer{R, S, Q<:ExtensionType},
    n::NodeBB
) -> Bool

Excludes OBBT on variable indices after a search in a filtering direction.

source
EAGO.bool_indx_diff! — Method
bool_indx_diff!(
    z::Vector{Bool},
    x::Vector{Bool},
    y::Vector{Bool}
) -> Vector{Bool}

Utility function used to set vector of booleans z to x & ~y. Avoids the generation of conversion of the BitArray created by broadcasting logical operators.

source

References

  1. Gleixner, A.M., Berthold, T., Müller, B. et al. J Glob Optim (2017) 67: 731. https://doi.org/10.1007/s10898-016-0450-4