Boscia.AwayFrankWolfeType
Away-Frank-Wolfe

In every iteration, it computes the worst performing vertex, called away vertex, in the active set with regard to the gradient. If enough local progress can be made, weight is shifted from the away vertex to all other vertices.

In case lazification is activated, the FW vertex is only computed if not enough local progress can be guaranteed.

Boscia.BLMOStatusType

Enum encoding the status of the Bounded Linear Minimization Oracle.

Boscia.BPCGType
Blended Pairwise Conditional Gradient
Boscia.CubeSimpleBLMOType
CubeSimpleBLMO{T}(lower_bounds, upper_bounds)

Hypercube with lower and upper bounds implementing the SimpleBoundableLMO interface.

Boscia.FrankWolfeNodeType
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 'fwdualgap_limit' set the tolerance for the dual gap in the FW algorithms

Boscia.FrankWolfeVariantType

Frank-Wolfe variant used to compute the problems at node level. A FrankWolfeVariant must implement

solve_frank_wolfe(fw::FrankWolfeVariant, f, grad!, lmo, active_set, line_search, epsilon, max_iteration,
    added_dropped_vertices, use_extra_vertex_storage, callback, lazy, timeout, verbose, workspace))

It may also implement build_frank_wolfe_workspace(x) which creates a workspace structure that is passed as last argument to solve_frank_wolfe.

Boscia.HybridStrongBranchingType

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

Boscia.IntegerBoundsType
IntegerBounds

Keeps track of the bounds of the integer (binary) variables.

lower_bounds dictionary of Float64, index is the key. upper_bounds dictionary of Float64, index is the key.

Boscia.ManagedBoundedLMOType
ManagedBoundedLinearMinimizationOracle

A Bounded Linear Minimization Oracle that manages the bounds.

simplelmo - An LMO of type Simple Boundable LMO (see above). lowerbounds - List of lower bounds for the integer variables recorded in intvars. If there is no specific lower bound, set corresponding entry to -Inf. upperbounds - List of upper bounds for the integer variables recorded in intvars. If there is no specific upper bound, set corresponding entry to Inf. n - Total number of variables. intvars - List of indices of the integer variables. solvingtime - The time evaluate `computeextreme_point`.

Boscia.MathOptBLMOType
BoundedLinearMinimizationOracle for solvers supporting MathOptInterface.
Boscia.SimpleBoundableLMOType
SimpleBoundableLinearMinimizationOracle

A simple LMO that computes the extreme point given the node specific bounds on the integer variables. Can be stateless since all of the bound management is done by the ManagedBoundedLMO.

Boscia.SimpleOptimizationProblemType

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
Boscia.TimeTrackingLMOType
TimeTrackingLMO  <: FW.LMO

An LMO wrapping another one tracking the time, number of nodes and number of calls.

Boscia.VanillaFrankWolfeType
Vanilla-Frank-Wolfe

The standard variant of Frank-Wolfe. In each iteration, the vertex v minimizing ∇f * (x-v) is computed.

Lazification cannot be used in this setting.

Base.convertMethod

Convert object of Type MathOptLMO into MathOptBLMO and viceversa.

Bonobo.get_branching_variableMethod

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

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

Checks if the branch and bound can be stopped. By default (in Bonobo) stops then the priority queue is empty.

Boscia.bounded_compute_extreme_pointFunction

Computes the extreme point given an direction d, the current lower and upper bounds on the integer variables, and the set of integer variables.

Boscia.bounded_compute_extreme_pointMethod

For all positive entries of d, assign the corresponding lower bound. For non-positive entries, assign largest possible value in increasing order.

Boscia.build_LMOMethod

Build node LMO from global LMO

Four action can be taken: KEEP - constraint is as saved in the global bounds CHANGE - lower/upper bound is changed to the node specific one DELETE - custom bound from the previous node that is invalid at current node and has to be deleted ADD - bound has to be added for this node because it does not exist in the global bounds (e.g. variable bound is a half open interval globally)

Boscia.build_bnb_callbackMethod

Output of Boscia

iter :          current iteration of Boscia
node id :       current node id
lower bound :   tree_lb(tree)
incumbent :     tree.incumbent
gap :           tree.incumbent-tree_lb(tree)
rel. gap :      dual_gap/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 compute_extreme_point calls in FW
FW iterations : number of iterations in FW
Boscia.dual_tighteningMethod

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

Boscia.find_best_solutionMethod

Finds the best solution in the Optimizer's solution storage, based on the objective function f. Returns the solution vector and the corresponding best value.

Boscia.get_int_varFunction

Get the index of the integer variable the bound is working on.

Boscia.get_int_varMethod

Get the index of the integer variable the bound is working on.

Boscia.get_list_of_variablesFunction

Get list of variables indices. If the problem has n variables, they are expected to contiguous and ordered from 1 to n.

Boscia.get_list_of_variablesMethod

Get list of variables indices and the total number of variables. If the problem has n variables, they are expected to contiguous and ordered from 1 to n.

Boscia.get_variables_pointersMethod

List of all variable pointers. Depends on how you save your variables internally. In the easy case, this is simply collect(1:N).

Is used in find_best_solution.

Boscia.get_variables_pointersMethod

List of all variable pointers. Depends on how you save your variables internally.

Is used in find_best_solution.

Boscia.is_bound_inFunction

To check if there is bound for the variable in the global or node bounds.

Boscia.is_bound_inMethod

To check if there is bound for the variable in the global or node bounds.

Boscia.is_linear_feasibleFunction

Is a given point v linear feasible for the model? That means does v satisfy all bounds and other linear constraints?

Boscia.is_simple_linear_feasibleFunction

Checks whether a given point v is satisfying the constraints on the problem. Note that the bounds on the integer variables are being checked by the ManagedBoundedLMO and do not have to be check here.

Boscia.is_valid_splitMethod

Check whether a split is valid, i.e. the upper and lower on variable vidx are not the same.

Boscia.is_valid_splitMethod

Check whether a split is valid, i.e. the upper and lower on variable vidx are not the same.

Boscia.min_via_enumFunction

Naive optimization by enumeration. Default uses binary values. Otherwise, third argument should be a vector of n sets of possible values for the variables.

Boscia.postsolveMethod
postsolve(tree, result, time_ref, verbose)

Runs the post solve both for a cleaner solutiona and to optimize for the continuous variables if present. Prints solution statistics if verbose is true.

Boscia.probability_roundingMethod

Probability rounding for 0/1 problems. It decides based on the fractional value whether to ceil or floor the variable value. Afterward, one call to Frank-Wolfe is performed to optimize the continuous variables.

Boscia.restart_active_setMethod

Call this if the active set is empty after splitting. Remark: This should not happen when using a MIP solver for the nodes!

Boscia.solveMethod
solve

f - objective function oracle. g - oracle for the gradient of the objective. blmo - a MIP solver instance (e.g., SCIP) encoding the feasible region. Has to be of type BoundedLinearMinimizationOracle (see lmo_wrapper.jl). traversestrategy - encodes how to choose the next node for evaluation. By default the node with the best lower bound is picked. branchingstrategy - by default we branch on the entry which is the farthest away from being an integer. variant - variant of FrankWolfe to be used to solve the node problem. Options: FW – Vanilla FrankWolfe AFW – Away FrankWolfe BPCG – Blended Pairwise Conditional Gradient linesearch - specifies the Line Search method used in the FrankWolfe variant. Default is the Adaptive Line Search. For other types, check the FrankWolfe.jl package. activeset - can be used to specify a starting point, e.g. if the feasible region is not completely contained in the domain of the objective. By default, the direction (1,..,n) where n is the size of the problem is used to find a start vertex. Beware that the active set may only contain actual vertices of the feasible region. lazy - specifies whether the lazification shoud be used. Per default true. Beware that it has no effect with Vanilla Frank-Wolfe. lazytolerance - decides how much progress is deemed enough to not have to call the LMO. fwepsilon - the tolerance for FrankWolfe in the root node. verbose - if true, a log and solution statistics are printed. dualgap - if this absolute dual gap is reached, the algorithm stops. reldualgap - if this relative dual gap is reached, the algorithm stops. timelimit - algorithm will stop if the time limit is reached. Depending on the problem it is possible that no feasible solution has been found yet. printiter - encodes after how many proccessed nodes the current node and solution status is printed. Will always print if a new integral solution has been found. dualgapdecayfactor - the FrankWolfe tolerance at a given level i in the tree is given by fwepsilon * dualgapdecayfactor^i until we reach the minnodefwepsilon. maxfwiter - maximum number of iterations in a FrankWolfe run. minnumberlower - If not Inf, evaluation of a node is stopped if at least minnumberlower nodes have a better lower bound. minnodefwepsilon - smallest fw epsilon possible, see dualgapdecayfactor. usepostsolve - Runs the specified Frank-Wolfe variant on the problem with the integral variables fixed to the solution, i.e. it only optimizes over the continuous variables. This might improve the solution if one has many continuous variables. minfwiterations - the minimum number of FrankWolfe iterations in the node evaluation. maxiterationpost - maximum number of iterations in a FrankWolfe run during postsolve dualtightening - whether to use dual tightening techniques (make sure your function is convex!) globaldualtightening - dual tightening maintained globally valid (when new solutions are found) bnbcallback - an optional callback called at every node of the tree, for example for heuristics strongconvexity - strong convexity of the function, used for tighter dual bound at every node domainoracle - For a point x: returns true if x is in the domain of f, else false. Per default is true. In case of the non trivial domain oracle, the starting point has to be feasible for f. Also, depending on the Line Search method, you might have to provide the domain oracle to it, too. startsolution - initial solution to start with an incumbent fwverbose - if true, FrankWolfe logs are printed useshadowset - The shadow set is the set of discarded vertices which is inherited by the children nodes. It is used to avoid recomputing of vertices in case the LMO is expensive. In case of a cheap LMO, performance might improve by disabling this option. customheuristics - List of custom heuristic from the user. probrounding - The probability for calling the rounding heuristics. Since the feasibility has to be checked, it might expensive to do this for every node.

Boscia.solveMethod

Solve function in case of MathOptLMO. Converts the lmo into a MathOptBLMO and calls the solve function below.

Boscia.solve_frank_wolfeFunction
solve_frank_wolfe(fw::FrankWolfeVariant, f, grad!, lmo, active_set, line_search, epsilon, max_iteration,
added_dropped_vertices, use_extra_vertex_storage, callback, lazy, timeout, verbose, workspace)

Returns the optimal solution x to the node problem, its primal and dual gap and the active set.

Boscia.strong_up_to_depthFunction

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

FrankWolfe.compute_extreme_pointFunction

Implement FrankWolfe.compute_extreme_point

Given a direction d solves the problem min_x d^T x where x has to be an integer feasible point