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

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.

AbtractFrankWolfeNode <: Bonobo.AbstractNode

FrankWolfeNode <: AbstractFrankWolfeNode

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

std stores the id, lower and upper bound 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.

NodeInfo

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

This variant is more flexibel than Bonobo.BnBNodeInfo.

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

Returns the solution vector of the relaxed problem at the node

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