`Boscia.AbstractFrankWolfeNode`

— Type`AbtractFrankWolfeNode <: Bonobo.AbstractNode`

`Boscia.AwayFrankWolfe`

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

— TypeEnum encoding the status of the Bounded Linear Minimization Oracle.

`Boscia.BPCG`

— Type`Blended Pairwise Conditional Gradient`

`Boscia.Blended`

— Type`Blended Conditional Gradient`

`Boscia.BoundedLinearMinimizationOracle`

— Type`BLMO`

Supertype for the Bounded Linear Minimization Oracles

`Boscia.CubeSimpleBLMO`

— Type`CubeSimpleBLMO{T}(lower_bounds, upper_bounds)`

Hypercube with lower and upper bounds implementing the `SimpleBoundableLMO`

interface.

`Boscia.FrankWolfeNode`

— Type`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 'fw*dual*gap_limit' set the tolerance for the dual gap in the FW algorithms

`Boscia.FrankWolfeVariant`

— TypeFrank-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.Heuristic`

— Type`Boscia Heuristic`

Interface for heuristics in Boscia. `h`

is the heuristic function receiving as input the tree, the bounded LMO and a point x (the current node solution). It returns the heuristic solution (can be nothing, we check for that) and whether feasibility still has to be check. `prob`

is the probability with which it will be called.

`Boscia.HybridStrongBranching`

— TypeHybrid between partial strong branching and another strategy. `perform_strong_branch(tree, node) -> Bool`

decides whether to perform strong branching or not.

`Boscia.IntegerBounds`

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

— Type`ManagedBoundedLinearMinimizationOracle`

A Bounded Linear Minimization Oracle that manages the bounds.

simple*lmo - An LMO of type Simple Boundable LMO (see above). lower*bounds - List of lower bounds for the integer variables recorded in int*vars. If there is no specific lower bound, set corresponding entry to -Inf. upper*bounds - List of upper bounds for the integer variables recorded in int

*vars. If there is no specific upper bound, set corresponding entry to*vars - List of indices of the integer variables. solving

`Inf`

. n - Total number of variables. int*time - The time evaluate `compute*extreme_point`.

`Boscia.MathOptBLMO`

— Type`BoundedLinearMinimizationOracle for solvers supporting MathOptInterface.`

`Boscia.MathOptBLMO`

— MethodBuild MathOptBLMO from FrankWolfe.MathOptLMO.

`Boscia.NodeInfo`

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

`Boscia.ProbabilitySimplexSimpleBLMO`

— Type`ProbablitySimplexSimpleBLMO(N)`

Scaled Probability Simplex: ∑ x = N.

`Boscia.SimpleBoundableLMO`

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

— TypeRepresents 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.Solve_Stage`

— TypeEnum for the solving stage

`Boscia.TimeTrackingLMO`

— Type`TimeTrackingLMO <: FW.LMO`

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

`Boscia.UnitSimplexSimpleBLMO`

— Type`UnitSimplexSimpleBLMO(N)`

Scaled Unit Simplex: ∑ x ≤ N.

`Boscia.VanillaFrankWolfe`

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

— MethodConvert object of Type MathOptLMO into MathOptBLMO and viceversa.

`Bonobo.evaluate_node!`

— MethodComputes the relaxation at that node

`Bonobo.get_branching_indices`

— MethodReturns the indices of the discrete variables for the branching in `Bonobo.BnBTree`

`Bonobo.get_branching_nodes_info`

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

`Bonobo.get_branching_variable`

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

`Bonobo.get_branching_variable`

— MethodBehavior for strong branching.

`Bonobo.get_relaxed_values`

— MethodReturns the solution vector of the relaxed problem at the node

`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.terminated`

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

`Boscia.add_bound_constraint!`

— FunctionAdd bound constraint.

`Boscia.add_bound_constraint!`

— MethodAdd bound constraint.

`Boscia.add_heuristic_solution`

— MethodAdd a new solution found from the heuristic to the tree.

`Boscia.bounded_compute_extreme_point`

— FunctionComputes 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_point`

— MethodIf the entry is positve, choose the lower bound. Else, choose the upper bound.

`Boscia.bounded_compute_extreme_point`

— MethodAssign the largest possible values to the entries corresponding to the smallest entries of d.

`Boscia.bounded_compute_extreme_point`

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

`Boscia.build_LMO`

— MethodBuild 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_LMO_correct`

— MethodCheck if the bounds were set correctly in build_LMO. Safety check only.

`Boscia.build_LMO_correct`

— MethodCheck if the bounds were set correctly in build_LMO. Safety check only.

`Boscia.build_bnb_callback`

— MethodOutput 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.build_global_bounds`

— FunctionRead global bounds from the problem.

`Boscia.build_global_bounds`

— MethodRead global bounds from the problem

`Boscia.check_feasibility`

— MethodCheck if problem is bounded and feasible, i.e. no contradicting constraints.

`Boscia.check_feasibility`

— MethodCheck if problem is bounded and feasible, i.e. no contradicting constraints.

`Boscia.check_feasibility`

— MethodCheck feasibility and boundedness

`Boscia.check_infeasible_vertex`

— MethodDeal with infeasible vertex if necessary, e.g. check what caused it etc.

`Boscia.check_infeasible_vertex`

— MethodDeal with infeasible vertex if necessary, e.g. check what caused it etc.

`Boscia.delete_bounds!`

— FunctionDelete bounds.

`Boscia.delete_bounds!`

— MethodDelete bounds.

`Boscia.dual_tightening`

— MethodTightening of the bounds at node level. Children node inherit the updated bounds.

`Boscia.explicit_bounds_binary_var`

— MethodAdd explicit bounds for binary variables.

`Boscia.find_best_solution`

— MethodFind best solution from the solving process.

`Boscia.find_best_solution`

— MethodFind best solution from the solving process.

`Boscia.find_best_solution`

— MethodFinds 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.flip_coin`

— FunctionFlip coin.

`Boscia.follow_gradient_heuristic`

— Method`follow-the-gradient`

Follow the gradient for a fixed number of steps and collect solutions on the way

`Boscia.free_model`

— MethodFree model data from previous solve (if necessary).

`Boscia.free_model`

— MethodFree model data from previous solve (if necessary).

`Boscia.get_BLMO_solve_data`

— MethodGet solve time, number of nodes and number of iterations, if applicable.

`Boscia.get_BLMO_solve_data`

— MethodGet solve time, number of nodes and number of simplex iterations.

`Boscia.get_binary_variables`

— MethodGet list of binary and integer variables, respectively.

`Boscia.get_bound`

— FunctionRead bound value for c_idx.

`Boscia.get_bound`

— MethodRead bound value for c_idx.

`Boscia.get_int_var`

— FunctionGet the index of the integer variable the bound is working on.

`Boscia.get_int_var`

— MethodGet the index of the integer variable the bound is working on.

`Boscia.get_integer_variables`

— FunctionGet list of integer variables.

`Boscia.get_list_of_variables`

— FunctionGet 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_variables`

— MethodGet 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_lower_bound_list`

— FunctionGet the list of lower bounds.

`Boscia.get_lower_bound_list`

— MethodGet the list of lower bounds.

`Boscia.get_tol`

— MethodGet solving tolerance for the BLMO.

`Boscia.get_tol`

— MethodGet solving tolerance for the BLMO.

`Boscia.get_upper_bound_list`

— FunctionGet the list of upper bounds.

`Boscia.get_upper_bound_list`

— MethodGet the list of upper bounds.

`Boscia.get_variables_pointers`

— MethodList 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_pointers`

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

Is used in `find_best_solution`

.

`Boscia.global_tightening`

— MethodUse the gradient of the root node to tighten the global bounds.

`Boscia.has_binary_constraint`

— MethodHas variable a binary constraint?

`Boscia.has_integer_constraint`

— FunctionHas variable an integer constraint?

`Boscia.has_integer_constraint`

— MethodCheck if at a given index we have an integer constraint respectivily.

`Boscia.has_integer_constraint`

— MethodDoes the variable have an integer constraint?

`Boscia.indicator_present`

— MethodAre indicator constraints present?

`Boscia.indicator_present`

— MethodAre indicator constraints present?

`Boscia.indicator_present`

— MethodAre indicator constraints present

`Boscia.is_bound_in`

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

`Boscia.is_bound_in`

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

`Boscia.is_constraint_on_int_var`

— FunctionCheck if the subject of the bound c*idx is an integer variable (recorded in int*vars).

`Boscia.is_constraint_on_int_var`

— MethodCheck if the subject of the bound c*idx is an integer variable (recorded in int*vars).

`Boscia.is_indicator_feasible`

— MethodIs a given point v indicator feasible, i.e. meets the indicator constraints? If applicable.

`Boscia.is_indicator_feasible`

— MethodIs a given point v indicator feasible, i.e. meets the indicator constraints? If applicable.

`Boscia.is_integer_feasible`

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

`Boscia.is_linear_feasible`

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

`Boscia.is_linear_feasible`

— MethodIs a given point v linear feasible for the model?

`Boscia.is_linear_feasible`

— MethodChecks if x is valid for all linear and variable bound constraints

`Boscia.is_simple_linear_feasible`

— FunctionChecks 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_split`

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

`Boscia.is_valid_split`

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

`Boscia.is_valid_split`

— MethodCheck wether a split is valid.

`Boscia.min_via_enum`

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

`Boscia.postsolve`

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

— MethodProbability 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.prune_children`

— MethodUse strong convexity to potentially remove one of the children nodes

`Boscia.relative_gap`

— MethodCompute relative gap consistently everywhere

`Boscia.restart_active_set`

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

`Boscia.rounding_heuristic`

— MethodSimple rounding heuristic.

`Boscia.rounding_hyperplane_heuristic`

— MethodHyperplane-aware rounding for the probability simplex.

`Boscia.rounding_hyperplane_heuristic`

— MethodHyperplane-aware rounding for the unit simplex.

`Boscia.rounding_lmo_01_heuristic`

— MethodAdvanced lmo-aware rounding for binary vars. Rounding respecting the hidden feasible region structure.

`Boscia.run_heuristics`

— MethodChoose which heuristics to run by rolling a dice.

`Boscia.set_bound!`

— FunctionChange the value of the bound c_idx.

`Boscia.set_bound!`

— MethodChange the value of the bound c_idx.

`Boscia.solve`

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

). traverse*strategy - encodes how to choose the next node for evaluation. By default the node with the best lower bound is picked. branching*strategy - 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 line*search - specifies the Line Search method used in the FrankWolfe variant. Default is the Adaptive Line Search. For other types, check the FrankWolfe.jl package. active*set - 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. lazy*tolerance - decides how much progress is deemed enough to not have to call the LMO. fw*epsilon - the tolerance for FrankWolfe in the root node. verbose - if true, a log and solution statistics are printed. dual*gap - if this absolute dual gap is reached, the algorithm stops. rel*dual*gap - if this relative dual gap is reached, the algorithm stops. time*limit - algorithm will stop if the time limit is reached. Depending on the problem it is possible that no feasible solution has been found yet. print*iter - 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. dual*gap*decay*factor - the FrankWolfe tolerance at a given level i in the tree is given by fw*epsilon * dual*gap*decay*factor^i until we reach the min*node*fw*epsilon. max*fw*iter - maximum number of iterations in a FrankWolfe run. min*number*lower - If not Inf, evaluation of a node is stopped if at least min*number*lower nodes have a better lower bound. min*node*fw*epsilon - smallest fw epsilon possible, see dual*gap*decay*factor. use*postsolve - 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. min*fw*iterations - the minimum number of FrankWolfe iterations in the node evaluation. max*iteration*post - maximum number of iterations in a FrankWolfe run during postsolve dual*tightening - whether to use dual tightening techniques (make sure your function is convex!) global*dual*tightening - dual tightening maintained globally valid (when new solutions are found) bnb*callback - an optional callback called at every node of the tree, for example for heuristics strong*convexity - strong convexity of the function, used for tighter dual bound at every node domain*oracle - 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. start*solution - initial solution to start with an incumbent fw*verbose - if true, FrankWolfe logs are printed use*shadow*set - 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. custom*heuristics - List of custom heuristic from the user. prob*rounding - The probability for calling the rounding heuristics. Since the feasibility has to be checked, it might expensive to do this for every node. clean*solutions - Flag deciding whether new solutions should be polished. They will be rounded and then a quick Frank-Wolfe run will be started. max*clean_iter - Maximum number of iteration in the Frank-Wolfe call for polishing new solutions.

Returns

- x - the solution.
- tlmo - the blmo wrapped in a TimeTrackingLMO instance.
- result - dictionary containg the statistics and information for plotting progress plots.

`Boscia.solve`

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

`Boscia.solve_frank_wolfe`

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

— MethodSplit an active set between left and right children.

`Boscia.split_vertices_set!`

— MethodSplit a discarded vertices set between left and right children.

`Boscia.store_data_global_tightening`

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

`Boscia.strong_up_to_depth`

— Functionstrong*up*to_depth performs strong branching on nodes up to a predetermined depth, and the falls back to another rule

`Boscia.tightening_strong_convexity`

— MethodTighten the lower bound using strong convexity of the objective.

`FrankWolfe.compute_extreme_point`

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

`FrankWolfe.compute_extreme_point`

— Method`compute_extreme_point`

Is implemented in the FrankWolfe package in file "moi_oracle.jl".