# Reference

`Bonobo.AbstractBranchStrategy`

— Type`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.

`Bonobo.AbstractNode`

— Type`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`

.

`Bonobo.AbstractSolution`

— Type`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.

`Bonobo.AbstractTraverseStrategy`

— Type`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.

`Bonobo.BestFirstSearch`

— Type`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.

`Bonobo.BnBNodeInfo`

— Type`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
```

`Bonobo.BnBTree`

— Type`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).
```

`Bonobo.DefaultNode`

— Type`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`

.

`Bonobo.DefaultSolution`

— Type`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.

`Bonobo.FIRST`

— Type`FIRST <: AbstractBranchStrategy`

The `FIRST`

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

`Bonobo.MOST_INFEASIBLE`

— Type`MOST_INFEASIBLE <: AbstractBranchStrategy`

The `MOST_INFEASIBLE`

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

`Bonobo.add_new_solution!`

— Method`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`

.

`Bonobo.add_node!`

— Method`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!`

.

`Bonobo.bound!`

— Method`bound!(tree::BnBTree, current_node_id::Int)`

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

`Bonobo.branch!`

— Method`branch!(tree, node)`

Get the branching variable with `get_branching_variable`

and then calls `get_branching_nodes_info`

and `add_node!`

.

`Bonobo.close_node!`

— Method`close_node!(tree::BnBTree, node::AbstractNode)`

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

`Bonobo.create_node`

— Method`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!`

.

`Bonobo.evaluate_node!`

— Function`evaluate_node!(tree, node)`

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

`Bonobo.get_branching_indices`

— Function`get_branching_indices(root)`

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

`Bonobo.get_branching_nodes_info`

— Function`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
```

`Bonobo.get_branching_variable`

— Method`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.

`Bonobo.get_branching_variable`

— Method`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.

`Bonobo.get_distance_to_feasible`

— Method`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

`Bonobo.get_next_node`

— Method`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`

.

`Bonobo.get_num_solutions`

— Method`get_num_solutions(tree::BnBTree)`

Return the number of solutions available.

`Bonobo.get_objective_value`

— Method`get_objective_value(tree::BnBTree; result=1)`

Return the objective value

`Bonobo.get_relaxed_values`

— Function`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.

`Bonobo.get_solution`

— Method`get_solution(tree::BnBTree; result=1)`

Return the solution values of the problem. See `get_objective_value`

to obtain the objective value instead.

`Bonobo.initialize`

— Method`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`

)

- needs to have
`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

`Bonobo.is_approx_feasible`

— Method`is_approx_feasible(tree::BnBTree, value)`

Return whether a given `value`

is approximately feasible based on the tolerances defined in the tree options.

`Bonobo.optimize!`

— Method`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:

- If the node is infeasible the kwarg
`node_infeasible`

is set to`true`

. - If the node has a higher lower bound than the incumbent the kwarg
`worse_than_incumbent`

is set to`true`

.

`Bonobo.set_node_bound!`

— Method`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.

`Bonobo.set_root!`

— Method`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
))
```

`Bonobo.sort_solutions!`

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

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

`Bonobo.terminated`

— Method`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.

`Bonobo.update_best_solution!`

— Method`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.