EAGO's Branch and Bound Routine

This component is meant to provide a flexible framework for implementing spatial branch-and-bound based optimization routines in Julia. All components of the branch-and-bound routine can be customized by the individual user: lower bounding problem, upper bounding problem.

Branch and Bound Node Storage

EAGO.NodeBBType
NodeBB

Stores information associated with each node in Branch & Bound tree.

  • lower_variable_bounds::Vector{Float64}: Lower bounds of variable box.
  • upper_variable_bounds::Vector{Float64}: Upper bounds of variable box.
  • lower_bound::Float64: Lower bound of problem solution on nodeBB
  • upper_bound::Float64: Upper bound of problem solution on nodeBB
  • depth::Int64: Depth of node in B&B tree.
  • id::Int64: Unique id for each node.

Customizable subroutines

EAGO.add_cut!Method
add_cut!(t::ExtensionType, x::Optimizer)

Adds a cut for each constraint and the objective function to the subproblem.

EAGO.branch_node!Method
branch_node!(t::ExtensionType, x::Optimizer)

Creates two nodes from currentnode using information available the x and stores them to the stack. By default, relative width bisection is perfomed at a point `branchpntwhich is a convex combination (parameter: branch_cvx_factor) of the solution to the relaxation and the midpoint of the node. If this solution lies withinbranchoffset/widthof a bound then the branch point is moved to a distance ofbranchoffset/width` from the bound.

EAGO.convergence_checkMethod
convergence_check(t::ExtensionType, x::Optimizer)

Checks for convergence of algorithm with respect to absolute and/or relative tolerances.

EAGO.cut_conditionMethod
cut_condition(t::ExtensionType, x::Optimizer)

Checks if a cut should be added and computes a new reference point to add the cut at. If no cut should be added the constraints not modified in place are deleted from the relaxed optimizer and the solution is compared with the interval lower bound. The best lower bound is then used.

EAGO.fathom!Method
fathom!(t::ExtensionType, d::Optimizer)

Selects and deletes nodes from stack with lower bounds greater than global upper bound.

EAGO.lower_problem!Method
lower_problem!(t::ExtensionType, x::Optimizer)

Constructs and solves the relaxation using the default EAGO relaxation scheme and optimizer on node y.

EAGO.relax_objective!Method
relax_objective!(t::ExtensionType, x::Optimizer, x0::Vector{Float64})

A rountine that only relaxes the objective.

EAGO.relax_problem!Method
relax_problem!(t::ExtensionType, x::Optimizer, v::Vector{Float64}, q::Int64)

A rountine that updates the current node for the Evaluator and relaxes all nonlinear constraints and quadratic constraints.

EAGO.node_selection!Method
node_selection!(t::ExtensionType, x::Optimizer)

Selects node with the lowest lower bound in stack.

EAGO.optimize_hook!Method
optimize_hook!(t::ExtensionType, x::Optimizer)

Provides a hook for extensions to EAGO as opposed to standard global, local, or linear solvers.

EAGO.postprocess!Method
postprocess!(t::ExtensionType, x::Optimizer)

Default postprocess perfoms duality-based bound tightening on the y.

EAGO.preprocess!Method
preprocess!(t::ExtensionType, x::Optimizer)

Runs interval, linear, quadratic contractor methods followed by obbt and a constraint programming walk up to tolerances specified in EAGO.Optimizer object.

EAGO.repeat_checkMethod
repeat_check(t::ExtensionType, x::Optimizer)

Checks to see if current node should be reprocessed.

EAGO.single_storage!Method
single_storage!(t::ExtensionType, x::Optimizer)

Stores the current node to the stack after updating lower/upper bounds.

EAGO.termination_checkMethod
termination_check(t::ExtensionType, x::Optimizer)

Checks for termination of algorithm due to satisfying absolute or relative tolerance, infeasibility, or a specified limit, returns a boolean valued true if algorithm should continue.

EAGO.upper_problem!Method
upper_problem!(t::ExtensionType, x::Optimizer)

Default upper bounding problem which simply calls solve_local_nlp! to solve the nlp locally.

Internal Subroutines

EAGO.cut_updateMethod
cut_update(x::Optimizer)

Updates the internal storage in the optimizer after a valid feasible cut is added.

EAGO.default_nlp_heuresticMethod
default_nlp_heurestic(x::Optimizer, y::NodeBB)

Default check to see if the upper bounding problem should be run. By default, The upper bounding problem is run on every node up to depth upper_bounding_depth and is triggered with a probability of 0.5^(depth - upper_bounding_depth) afterwards.

EAGO.interval_boundFunction
interval_bound

Computes the natural interval extension of a MathOptInterface function s or ScalarQuadaraticFunction on a node y. Returns the lower bound if flag is true and the upper bound if flag is false.

EAGO.interval_lower_bound!Method
interval_lower_bound!(x::Optimizer, y::NodeBB)

A fallback lower bounding problem that consists of an natural interval extension calculation. This is called when the optimizer used to compute the lower bound does not return a termination and primal status code indicating that it successfully solved the relaxation to a globally optimal point.

EAGO.is_globally_optimalMethod
is_globally_optimal(t::MOI.TerminationStatusCode, r::MOI.ResultStatusCode)

Takes an MOI.TerminationStatusCode and a MOI.ResultStatusCode and returns the tuple (valid_result::Bool, feasible::Bool). The value valid_result is true if the pair of codes prove that either the subproblem solution was solved to global optimality or the subproblem solution is infeasible. The value of feasible is true if the problem is feasible and false if the problem is infeasible.

EAGO.is_feasible_solutionMethod
is_feasible_solution(t::MOI.TerminationStatusCode, r::MOI.ResultStatusCode)

Takes an MOI.TerminationStatusCode and a MOI.ResultStatusCode and returns true if this corresponds to a solution that is proven to be feasible. Returns false otherwise.

EAGO.log_iteration!Method
log_iteration!(x::Optimizer)

If 'loggingon' is true, the 'globallowerbound', 'globalupperbound', 'runtime', and 'nodecount' are stored every 'loginterval'. If 'logsubprobleminfo' then the lower bound, feasibility and run times of the subproblems are logged every 'log_interval'.

EAGO.same_boxMethod
same_box(x::NodeBB,y::NodeBB, atol::Float64)

Checks that node x and y have equal domains withing a tolerance of atol.

EAGO.solve_local_nlp!Method
solve_local_nlp!(x::Optimizer)

Constructs and solves the problem locally on on node y updated the upper solution informaton in the optimizer.

EAGO.set_dual!Method
set_dual!(x::Optimizer)

Retrieves the lower and upper duals for variable bounds from the relaxed_optimizer and sets the appropriate values in the _lower_lvd and _lower_uvd storage fields.

EAGO.update_relaxed_problem_box!Method
update_relaxed_problem_box!(x::Optimizer, y::NodeBB)

Updates the relaxed constraint by setting the constraint set of v == x*,xLi <= xi, andxi <= xUi` for each such constraint added to the relaxed optimizer.

Functions for generating console output

EAGO.print_iteration!Function
print_iteration!

Prints the iteration information based on verbosity. The header is displayed every header_interval, the iteration info is displayed every iteration_interval.

EAGO.print_node!Function
print_node!

Prints node information for the B&B problem. Node id, bound, and interval box.

EAGO.print_solution!Function
print_solution!

Prints solution information for the B&B problem. Displays first node found, solution value, solution, and time spent solving subproblems.