AbtractFrankWolfeNode <: Bonobo.AbstractNode

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.

Enum encoding the status of the Bounded Linear Minimization Oracle.

Blended Pairwise Conditional Gradient

Blended Conditional Gradient

BLMO

Supertype for the Bounded Linear Minimization Oracles

CubeSimpleBLMO{T}(lower_bounds, upper_bounds)

Hypercube with lower and upper bounds implementing the SimpleBoundableLMO interface.

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

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

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

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.

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

BoundedLinearMinimizationOracle for solvers supporting MathOptInterface.

Build MathOptBLMO from FrankWolfe.MathOptLMO.

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.

ProbablitySimplexSimpleBLMO(N)

Scaled Probability Simplex: ∑ x = N.

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.

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

Enum for the solving stage

TimeTrackingLMO  <: FW.LMO

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

UnitSimplexSimpleBLMO(N)

Scaled Unit Simplex: ∑ x ≤ N.

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.

Convert object of Type MathOptLMO into MathOptBLMO and viceversa.

Computes the relaxation at that node

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

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

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

Behavior for strong branching.

Returns the solution vector of the relaxed problem at the node

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.

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

Add bound constraint.

Add bound constraint.

Add a new solution found from the heuristic to the tree.

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

If the entry is positve, choose the lower bound. Else, choose the upper bound.

Assign the largest possible values to the entries corresponding to the smallest entries of d.

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

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)

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

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

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

Read global bounds from the problem.

Read global bounds from the problem

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

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

Check feasibility and boundedness

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

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

Delete bounds.

Delete bounds.

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

Add explicit bounds for binary variables.

Find best solution from the solving process.

Find best solution from the solving process.

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.

Flip coin.

follow-the-gradient

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

Free model data from previous solve (if necessary).

Free model data from previous solve (if necessary).

Get solve time, number of nodes and number of iterations, if applicable.

Get solve time, number of nodes and number of simplex iterations.

Get list of binary and integer variables, respectively.

Read bound value for c_idx.

Read bound value for c_idx.

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

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

Get list of integer variables.

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

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.

Get the list of lower bounds.

Get the list of lower bounds.

Get solving tolerance for the BLMO.

Get solving tolerance for the BLMO.

Get the list of upper bounds.

Get the list of upper bounds.

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.

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

Is used in find_best_solution.

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

Has variable a binary constraint?

Has variable an integer constraint?

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

Does the variable have an integer constraint?

Are indicator constraints present?

Are indicator constraints present?

Are indicator constraints present

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

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

Check if the subject of the bound cidx is an integer variable (recorded in intvars).

Check if the subject of the bound cidx is an integer variable (recorded in intvars).

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

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

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

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

Is a given point v linear feasible for the model?

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

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.

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

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

Check wether a split is valid.

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

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.

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.

Use strong convexity to potentially remove one of the children nodes

Compute relative gap consistently everywhere

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

Simple rounding heuristic.

Hyperplane-aware rounding for the probability simplex.

Hyperplane-aware rounding for the unit simplex.

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

Choose which heuristics to run by rolling a dice.

Change the value of the bound c_idx.

Change the value of the bound c_idx.

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.

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

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.

Split an active set between left and right children.

Split a discarded vertices set between left and right children.

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

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

Tighten the lower bound using strong convexity of the objective.

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

compute_extreme_point

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