Reference

Bonobo.AbstractBranchStrategyType
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.

source
Bonobo.AbstractSolutionType
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.

source
Bonobo.AbstractTraverseStrategyType
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.

source
Bonobo.BestFirstSearchType
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.

source
Bonobo.BnBNodeInfoType
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
source
Bonobo.BnBTreeType
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).
source
Bonobo.DefaultNodeType
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.

source
Bonobo.DefaultSolutionType
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.

source
Bonobo.FIRSTType
FIRST <: AbstractBranchStrategy

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

source
Bonobo.MOST_INFEASIBLEType
MOST_INFEASIBLE <: AbstractBranchStrategy

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

source
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.

source
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!.

source
Bonobo.bound!Method
bound!(tree::BnBTree, current_node_id::Int)

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

source
Bonobo.close_node!Method
close_node!(tree::BnBTree, node::AbstractNode)

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

source
Bonobo.create_nodeMethod
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!.

source
Bonobo.evaluate_node!Function
evaluate_node!(tree, node)

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

source
Bonobo.get_branching_nodes_infoFunction
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
source
Bonobo.get_branching_variableMethod
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.

source
Bonobo.get_distance_to_feasibleMethod
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
source
Bonobo.get_relaxed_valuesFunction
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.

source
Bonobo.initializeMethod
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!.

source
Bonobo.is_approx_feasibleMethod
is_approx_feasible(tree::BnBTree, value)

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

source
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:

  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.
source
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.

source
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
))
source
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.

source
Bonobo.terminatedMethod
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.

source
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.

source