EAGO's Branch and Bound Routine

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.

convergence_check(t::ExtensionType, x::Optimizer)

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

EAGO.cut_conditionMethod.
cut_conditioncut_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.

lower_problem!(t::ExtensionType, x::Optimizer)

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

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

A rountine that only relaxes the objective.

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.

node_selection!(t::ExtensionType, x::Optimizer)

Selects node with the lowest lower bound in stack.

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.

single_storage!(t::ExtensionType, x::Optimizer)

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

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.

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.

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.

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.

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.

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.

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.

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.

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_results!Function.
print_results!

Prints the results of a single bounding problem.

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.