Reference

AbstractBranchStrategy

The abstract type for a branching strategy. If you implement a new branching strategy, this must be the supertype.

If you want to implement your own strategy, you must implement a new method for get_branching_variable which dispatches on the branch_strategy argument.

AbstractNode

The abstract type for a tree node. Your own type for Node given to initialize needs to subtype it. The default if you don't provide your own is DefaultNode.

AbstractSolution{Node<:AbstractNode, Value}

The abstract type for a Solution object. The default is DefaultSolution. It is parameterized by Node and Value where Value is the value which describes the full solution i.e the value for every variable.

AbstractTraverseStrategy

The abstract type for a traverse strategy. If you implement a new traverse strategy this must be the supertype.

If you want to implement your own strategy the get_next_node function needs a new method which dispatches on the traverse_strategy argument.

BestFirstSearch <: AbstractTraverseStrategy

The BestFirstSearch traverse strategy always picks the node with the lowest bound first. If there is a tie then the smallest node id is used as a tie breaker.

BnBNodeInfo

Holds the necessary information of every node. This needs to be added by every AbstractNode as std::BnBNodeInfo

id :: Int
lb :: Float64
ub :: Float64

BnBTree{Node<:AbstractNode,Root,Value,Solution<:AbstractSolution{Node,Value}}

Holds all the information of the branch and bound tree.

incumbent::Float64 - The best objective value found so far. Is stores as problem is a minimization problem
incumbent_solution::Solution - The currently best solution object
lb::Float64        - The highest current lower bound 
solutions::Vector{Solution} - A list of solutions
node_queue::PriorityQueue{Int,Tuple{Float64, Int}} - A priority queue with key being the node id and the priority consists of the node lower bound and the node id.
nodes::Dict{Int, Node}  - A dictionary of all nodes with key being the node id and value the actual node.
root::Root      - The root node see [`set_root!`](@ref)
branching_indices::Vector{Int} - The indices to be able to branch on used for [`get_branching_variable`](@ref)
num_nodes::Int  - The number of nodes created in total
sense::Symbol   - The objective sense: `:Max` or `:Min`.
options::Options  - All options for the branch and bound tree. See [`Options`](@ref).

DefaultNode <: AbstractNode

The default structure for saving node information. Currently this includes only the necessary std::BnBNodeInfo which needs to be part of every AbstractNode.

DefaultSolution{Node<:AbstractNode,Value} <: AbstractSolution{Node, Value}

The default struct to save a solution of the branch and bound run. It holds

objective :: Float64
solution  :: Value
node      :: Node

Both the Value and the Node type are determined by the initialize method.

solution holds the information to obtain the solution for example the values of all variables.

FIRST <: AbstractBranchStrategy

The FIRST strategy always picks the first variable which isn't fixed yet and can be branched on.

MOST_INFEASIBLE <: AbstractBranchStrategy

The MOST_INFEASIBLE strategy always picks the variable which is furthest away from being "fixed" and can be branched on.

add_new_solution!(tree::BnBTree{N,R,V,S}, node::AbstractNode) where {N,R,V,S<:DefaultSolution{N,V}}

Currently it changes the general solution itself by calling get_relaxed_values which needs to be implemented by you.

This function needs to be implemented by you if you have a different type of Solution object than DefaultSolution.

add_node!(tree::BnBTree{Node}, parent::Union{AbstractNode, Nothing}, node_info::NamedTuple)

Add a new node to the tree using the node_info. For information on that see set_root!.

bound!(tree::BnBTree, current_node_id::Int)

Close all nodes which have a lower bound higher or equal to the incumbent

branch!(tree, node)

Get the branching variable with get_branching_variable and then calls get_branching_nodes_info and add_node!.

close_node!(tree::BnBTree, node::AbstractNode)

Delete the node from the nodes dictionary and the priority queue.

create_node(Node, node_id::Int, parent::Union{AbstractNode, Nothing}, node_info::NamedTuple)

Creates a node of type Node with id node_id and the named tuple node_info. For information on that see set_root!.

evaluate_node!(tree, node)

Evaluate the current node and return the lower and upper bound of that node.

get_branching_indices(root)

Return a vector of variables to branch on from the current root object.

get_branching_nodes_info(tree::BnBTree, node::AbstractNode, vidx::Int)

Create the information for new branching nodes based on the variable index vidx. Return a list of those information as a NamedTuple vector.

Example

The following would add the necessary information about a new node and return it. The necessary information are the fields required by the AbstractNode. For this examle the required fields are the lower and upper bounds of the variables as well as the status of the node.

nodes_info = NamedTuple[]
push!(nodes_info, (
    lbs = lbs,
    ubs = ubs,
    status = MOI.OPTIMIZE_NOT_CALLED,
))
return nodes_info

get_branching_variable(tree::BnBTree, ::FIRST, node::AbstractNode)

Return the first possible branching variable which is a branching variable based on tree.branching_indices and is currently not valid based on is_approx_feasible. Return -1 if all integer constraints are respected.

get_branching_variable(tree::BnBTree, ::MOST_INFEASIBLE, node::AbstractNode)

Return the branching variable which is furthest away from being feasible based on get_distance_to_feasible or -1 if all integer constraints are respected.

get_distance_to_feasible(tree::BnBTree, value)

Return the distance of feasibility for the given value.

• if value::Number this returns the distance to the nearest discrete value

get_next_node(tree::BnBTree, ::BestFirstSearch)

Get the next node of the tree which shall be evaluted next by evaluate_node!. If you want to implement your own traversing strategy check out AbstractTraverseStrategy.

get_num_solutions(tree::BnBTree)

Return the number of solutions available.

get_objective_value(tree::BnBTree; result=1)

Return the objective value

get_relaxed_values(tree::BnBTree, node::AbstractNode)

Get the values of the current node. This is always called only after evaluate_node! is called. It is used to store a Solution object. Return the type of Value given to the initialize method.

get_solution(tree::BnBTree; result=1)

Return the solution values of the problem. See get_objective_value to obtain the objective value instead.

initialize(; kwargs...)

Initialize the branch and bound framework with the the following arguments. Later it can be dispatched on BnBTree{Node, Root, Solution} for various methods.

Keyword arguments

• traverse_strategy [BestFirstSearch] currently the only supported traverse strategy is BestFirstSearch. Should be an AbstractTraverseStrategy
• branch_strategy [FIRST] currently the only supported branching strategies are FIRST and MOST_INFEASIBLE. Should be an AbstractBranchStrategy
• atol [1e-6] the absolute tolerance to check whether a value is discrete
• rtol [1e-6] the relative tolerance to check whether a value is discrete
• Node DefaultNode can be special structure which is used to store all information about a node.
  • needs to have AbstractNode as the super type
  • needs to have std :: BnBNodeInfo as a field (see BnBNodeInfo)
• Solution DefaultSolution stores the node and several other information about a solution
• root [nothing] the information about the root problem. The type can be used for dispatching on types
• sense [:Min] can be :Min or :Max depending on the objective sense
• Value [Vector{Float64}] the type of a solution

Return a BnBTree object which is the input for optimize!.

is_approx_feasible(tree::BnBTree, value)

Return whether a given value is approximately feasible based on the tolerances defined in the tree options.

optimize!(tree::BnBTree; callback=(args...; kwargs...)->())

Optimize the problem using a branch and bound approach.

The steps, repeated until terminated is true, are the following:

# 1. get the next open node depending on the traverse strategy
node = get_next_node(tree, tree.options.traverse_strategy)
# 2. evaluate the current node and return the lower and upper bound
# if the problem is infeasible both values should be set to NaN
lb, ub = evaluate_node!(tree, node)
# 3. update the upper and lower bound of the node struct
set_node_bound!(tree.sense, node, lb, ub)

# 4. update the best solution
updated = update_best_solution!(tree, node)
updated && bound!(tree, node.id)

# 5. remove the current node
close_node!(tree, node)
# 6. compute the node children and adds them to the tree
# internally calls get_branching_variable and branch_on_variable!
branch!(tree, node)

A callback function can be provided which will be called whenever a node is closed. It always has the arguments tree and node and is called after the node is closed. Additionally the callback function must accept additional keyword arguments (kwargs) which are set in the following ways:

1. If the node is infeasible the kwarg node_infeasible is set to true.
2. If the node has a higher lower bound than the incumbent the kwarg worse_than_incumbent is set to true.

set_node_bound!(objective_sense::Symbol, node::AbstractNode, lb, ub)

Set the bounds of the node object to the lower and upper bound given. Internally everything is stored as a minimization problem. Therefore the objective_sense :Min/:Max is needed.

set_root!(tree::BnBTree, node_info::NamedTuple)

Set the root node information based on the node_info which needs to include the same fields as the Node struct given to the initialize method. (Besides the std field which is set by Bonobo automatically)

Example

If your node structure is the following:

mutable struct MIPNode <: AbstractNode
    std :: BnBNodeInfo
    lbs :: Vector{Float64}
    ubs :: Vector{Float64}
    status :: MOI.TerminationStatusCode
end

then you can call the function with this syntax:

Bonobo.set_root!(tree, (
    lbs = fill(-Inf, length(x)),
    ubs = fill(Inf, length(x)),
    status = MOI.OPTIMIZE_NOT_CALLED
))

sort_solutions!(solutions::Vector{<:AbstractSolution}, sense::Symbol)

Sort the solutions vector by objective value such that the best solution is at index 1.

terminated(tree::BnBTree)

Return true when the branch-and-bound loop in optimize! should be terminated. Default behavior is to terminate the loop only when no nodes exist in the priority queue or when the relative or absolute duality gap are below the tolerances fixed in the options.

update_best_solution!(tree::BnBTree, node::AbstractNode)

Update the best solution when we found a better incumbent. Calls [add_new_solution!] if this is the case, returns whether a solution was added.