Branch-and-Bound tree functionality

Represents an optimization problem of the form:

min_x f(x)
s.t.  x ∈ X (given by the LMO)
      x_j ∈ Z ∀ j in integer_variables

Returns the indices of the discrete variables for the branching in BnBTree

Are indicator constraints present

Checks if a given vector is valid integral solution. Specifically for mixed problems.

Checks if x is valid for all linear and variable bound constraints

Returns the solution vector of the relaxed problem at the node

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

sort_solutions!(solutions::Vector{<:AbstractSolution})

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

AbtractFrankWolfeNode <: AbstractNode 
NodeInfo

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

This variant is more flexible than Bonobo.BnBNodeInfo.

FrankWolfeNode <: AbstractFrankWolfeNode

A node in the branch-and-bound tree storing information for a Frank-Wolfe subproblem.

std stores the id, lower, upper bound and Depth of the node. active_set store the active set structure. local_bounds instead of storing the complete LMO, it just stores the bounds specific to THIS node. All other integer bounds are stored in the root. 'level' stores the level in the tree 'fwdualgaplimit' set the tolerance for the dual gap in the FW algorithms 'precomputedset' stores specifically the extreme points computed in DICG for warm-start. 'parentlowerboundbase' contains lower bound value of the parent node. Needed for updating pseudocosts. 'branchedon' contains the index of the parent. Required for updating pseudocosts. 'branchedright' Boolean value specifying if node resulted from a left or right branch. Needed for updating pseudocosts. 'distancetoint' Stores information on the rounding amount at branching. Required for correct scaling of pseudocosts.

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

Computes the relaxation at that node

Create the information of the new branching nodes based on their parent and the index of the branching variable

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

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:

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

Frank-Wolfe Callback.

Is called in every Frank-Wolfe iteration. Node evaluation can be dynamically stopped here. Time limit is checked. If the vertex is providing a better incumbent, it is added as solution.

Branch-and-Bound Callback. Collects statistics and prints logs if verbose is turned on.

Output of Boscia: iter : current iteration of Boscia node id : current node id lower bound : treelb(tree) incumbent : tree.incumbent gap : tree.incumbent-treelb(tree) rel. gap : dualgap/tree.incumbent time : total time of Boscia time/nodes : average time per node FW time : time spent in FW LMO time : time used by LMO LMO calls : number of computeextreme_point calls in FW FW iterations : number of iterations in FW

Tightening of the bounds at node level. Children node inherit the updated bounds.

Use the gradient of the root node to tighten the global bounds.

Use strong convexity and/or sharpness to potentially remove one of the children nodes. If both sharpness and strong convexity parameters are provided, strong convexity is preferred.

Save the gradient of the root solution (i.e. the relaxed solution) and the corresponding lower and upper bounds.

Tighten the lower bound using strong convexity and/or sharpness of the objective.

Hybrid between partial strong branching and another strategy. perform_strong_branch(tree, node) -> Bool decides whether to perform strong branching or not.

Get branching variable using strong branching. Create all possible subproblems, solve them and pick the one with the most progress.

strongupto_depth performs strong branching on nodes up to a predetermined depth, and the falls back to another rule