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.NodeBB
— TypeNodeBB
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 nodeBBupper_bound::Float64
: Upper bound of problem solution on nodeBBdepth::Int64
: Depth of node in B&B tree.id::Int64
: Unique id for each node.
Customizable subroutines
EAGO.add_cut!
— Methodadd_cut!(t::ExtensionType, x::Optimizer)
Adds a cut for each constraint and the objective function to the subproblem.
EAGO.branch_node!
— Methodbranch_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 within
branchoffset/widthof a bound then the branch point is moved to a distance of
branchoffset/width` from the bound.
EAGO.convergence_check
— Methodconvergence_check(t::ExtensionType, x::Optimizer)
Checks for convergence of algorithm with respect to absolute and/or relative tolerances.
EAGO.cut_condition
— Methodcut_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!
— Methodfathom!(t::ExtensionType, d::Optimizer)
Selects and deletes nodes from stack with lower bounds greater than global upper bound.
EAGO.lower_problem!
— Methodlower_problem!(t::ExtensionType, x::Optimizer)
Constructs and solves the relaxation using the default EAGO relaxation scheme and optimizer on node y
.
EAGO.relax_objective!
— Methodrelax_objective!(t::ExtensionType, x::Optimizer, x0::Vector{Float64})
A rountine that only relaxes the objective.
EAGO.relax_problem!
— Methodrelax_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!
— Methodnode_selection!(t::ExtensionType, x::Optimizer)
Selects node with the lowest lower bound in stack.
EAGO.optimize_hook!
— Methodoptimize_hook!(t::ExtensionType, x::Optimizer)
Provides a hook for extensions to EAGO as opposed to standard global, local, or linear solvers.
EAGO.postprocess!
— Methodpostprocess!(t::ExtensionType, x::Optimizer)
Default postprocess perfoms duality-based bound tightening on the y
.
EAGO.preprocess!
— Methodpreprocess!(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_check
— Methodrepeat_check(t::ExtensionType, x::Optimizer)
Checks to see if current node should be reprocessed.
EAGO.single_storage!
— Methodsingle_storage!(t::ExtensionType, x::Optimizer)
Stores the current node to the stack after updating lower/upper bounds.
EAGO.termination_check
— Methodtermination_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!
— Methodupper_problem!(t::ExtensionType, x::Optimizer)
Default upper bounding problem which simply calls solve_local_nlp!
to solve the nlp locally.
Internal Subroutines
EAGO.cut_update
— Methodcut_update(x::Optimizer)
Updates the internal storage in the optimizer after a valid feasible cut is added.
EAGO.default_nlp_heurestic
— Methoddefault_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_bound
— Functioninterval_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!
— Methodinterval_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_optimal
— Methodis_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_solution
— Methodis_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!
— Methodlog_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_box
— Methodsame_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!
— Methodsolve_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!
— Methodset_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!
— Methodupdate_relaxed_problem_box!(x::Optimizer, y::NodeBB)
Updates the relaxed constraint by setting the constraint set of v == x*
,
xLi <= xi, and
xi <= xUi` for each such constraint added to the relaxed optimizer.
Functions for generating console output
EAGO.print_iteration!
— Functionprint_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!
— Functionprint_node!
Prints node information for the B&B problem. Node id, bound, and interval box.
EAGO.print_results!
— Functionprint_results!
Prints the results of a single bounding problem.
EAGO.print_solution!
— Functionprint_solution!
Prints solution information for the B&B problem. Displays first node found, solution value, solution, and time spent solving subproblems.