Algorithm Interface

postsolve(tree, result, time_ref, verbose, max_iteration_post)

Runs the post solve to optimize for the continuous variables if present. Is called if use_post_solve is enabled in the solve function. Prints solution statistics if verbose is set to true.

solve(f, g, blmo::BoundedLinearMinimizationOracle; ...)

Requires

• f oracle of the objective function.
• g oracle of the gradient of the objective
• blmo encodes the feasible region and can handle additional bound constraints. This can either be a MIP solver instance (e.g., SCIP) or be a custom type (see polytope_blmos.jl). Has to be of type BoundedLinearMinimizationOracle (see blmo_interface.jl).

Returns

• x the best solution found.
• tlmo the BLMO wrapped in a TimeTrackingLMO instance.
• result a dictionary containg the statistics like number of nodes, total solving etc. It also contains information for plotting progress plots like the lower and upper bound progress.

Optional settings

• settings_bnb dictionary of settings for the branch-and-bound algorithm. Created via settings_bnb().
• settings_frank_wolfe dictionary of settings for the Frank-Wolfe algorithm. Created via settings_frank_wolfe().
• settings_tolerances dictionary of settings for the tolerances. Created via settings_tolerances().
• settings_postprocessing dictionary of settings for the postprocessing. Created via settings_postprocessing().
• settings_heuristic dictionary of settings for the heuristics. Created via settings_heuristic().
• settings_tightening dictionary of settings for the tightening. Created via settings_tightening().
• settings_domain dictionary of settings for the domain. Created via settings_domain().

Create default settings depending on the mode.

Only requires the mode, if no mode is provided, the default mode is used. Returns a NamedTuple of dictionaries for the different group of settings.

settings_bnb(mode::Mode;...)

Set the settings for the branch-and-bound algorithm.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of settings for the branch-and-bound algorithm.

Available settings:

• traverse_strategy encodes how to choose the next node for evaluation. By default the node with the best lower bound is picked.
• branching_strategy fixes the branching strategy. By default, weuse MOST_INFEASIBLE, i.e. we branch on the entry which is the farthest away from being an integer.
• verbose if true, logs and solution statistics are printed. Per default, this is false.
• node_limit maximum number of nodes to be evaluated. In DEFAULT mode, there is no limit. In HEURISTIC mode, the default is set to 1000.
• 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. In DEFAULT mode, there is no time limit. In HEURISTIC mode, the default is set to 300 seconds (5 minutes).
• print_iter encodes after how many processed nodes the current node and solution status is printed. The logs are always printed if a new integral solution has been found. Per default, print_iter is set to 100`.
• bnb_callback optional callback function that is called after every node evaluation. It will be called before the Boscia internal callback handling the printing of the logs. It receives the tree, the node and the following keyword arguments: worse_than_incumbent=false, node_infeasible=false, lb_update=false.
• branch_callback an optional callback called before branching. Receives the tree, the node and the branching variable index as input. If it returns false, no branching is performed and the node is pruned.
• no_pruning if true, no pruning of nodes is performed. Per default, nodes are pruned if they have a lower bound which is worse than the best known solution. Per default, this is true for the HEURISTIC mode and false for the OPTIMAL mode.
• ignore_lower_bound if true, the lower bound obtain by Frank-Wolfe is ignored and in the logs, only Inf will be printed. Per default, this is true for the HEURISTIC mode and false for the OPTIMAL mode.
• start_solution an initial solution can be provided if known. It will be used as the initial incumbent.
• 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 BLMO is expensive. In case of a cheap BLMO, performance might improve by disabling this option. Per default, this is true.

settings_domain(mode::Mode;...)

To set settings for a non-trivial domain, i.e. if not all points of the feasible region are domain feasible.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of settings for the domain.

Available settings:

• domain_oracle given a point x: returns true if x is in the domain of f, else false. Per default, it always returns true. In case of the non-trivial domain oracle, the initial point has to be domain feasible for f and can be set via the active_set. Additionally, the user has to provide a functiondomain_point`, see below. Also, depending on the line search method, you might have to provide the domain oracle to it, too. The default line search Secant, for example, requires the domain oracle.
• find_domain_point given the current node bounds return a domain feasible point respecting the bounds. If no such point can be found, return nothing. Only necessary for a non-trivial domain oracle.
• active_set can be used to specify a starting point. By default, the direction (1,..,n) where n is the size of the problem is used to find a start vertex. This has to be of the type FrankWolfe.ActiveSet. Beware that the active set may only contain actual vertices of the feasible region.

settings_frank_wolfe(mode::Mode;...)

Options for the Frank-Wolfe algorithm used as node solver.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of settings for the Frank-Wolfe algorithm.

Available settings:

• variant the Frank-Wolfe variant to be used to solve the node problem. Options currently available are AwayFrankWolfe, BlendedConditionalGradient, BlendedPairwiseConditionalGradient, DecompositionInvariantConditionalGradient and StandardFrankWolfe. Per default, this is set to BlendedPairwiseConditionalGradient.
• line_search specifies the line search method used in the FrankWolfe variant. Default is the FrankWolfe.Secant line search. For other available types, check the FrankWolfe.jl package.
• max_fw_iter maximum number of iterations in a Frank-Wolfe run. Per default, this is set to 10000.
• fw_timeout time limit for the Frank-Wolfe runs. Per default, there is no time limit. It is preferred to set the iteration limit but this can be used as a fallback and/or if the BLMO call is time consuming.
• min_fw_iterations the minimum number of Frank-Wolfe iterations performed in the node evaluation. Per default, this is set to 5.
• fw_verbose if true, the Frank-Wolfe logs are printed at each node. Mostly meant for debugging. Per default, this is false.
• lazy flag specifies whether the lazification of the Frank-Wolfe variant should be used. Per default true. Note that it has no effect on standard Frank-Wolfe.
• lazy_tolerance decides how much progress is deemed enough to not have to call the LMO. Only used if the lazy flag is activated. Per default, this is set to 2.

settings_heuristic(mode::Mode;...)

Set the settings for the heuristics.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of settings for the heuristics.

Available settings:

• custom_heuristics list of custom heuristics from the user. Heuristics can be created via the Boscia.Heuristic constructor. It requires a function, a probability and an identifier (symbol). Note that the heuristics defined in Boscia themselves don't have to be added here and can be set via the probability parameters below.
• post_heuristics_callback callback function called whenever a new solution is found and added to the tree.
• prob_rounding the probability for calling the simple rounding heuristic. Since the feasibility has to be checked, it might be expensive to do this for every node. Per default, this is activated for every node.
• follow_gradient_prob the probability for calling the follow-the-gradient heuristic. Per default, this is 0.0.
• follow_gradient_steps the number of steps for the follow-the-gradient heuristic. Per default, this is 10.
• rounding_lmo_01_prob the probability for calling the rounding-LMO-01 heuristic. Per default, this is 0.0.
• probability_rounding_prob the probability for calling the probability-rounding heuristic. Per default, this is 0.0.
• hyperplane_aware_rounding_prob the probability for calling the hyperplane-aware-rounding heuristic. Per default, this is 0.0.
• add_all_solutions if true, all solutions found by the heuristics, Frank-Wolfe or the BLMO are added to the tree. Per default, this is true for the HEURISTIC mode and false for the OPTIMAL mode.

settings_postprocessing(mode::Mode;...)

Set the settings for the postprocessing.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of settings for the postprocessing.

Available settings:

• use_postsolve if true, 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. Per default, this is true.
• max_iteration_post maximum number of iterations in the Frank-Wolfe run during postsolve. Per default, this is set to 10000.

settings_tightening(mode::Mode;...)

Set the tightening parameters.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of settings for the tightening.

Available settings:

• dual_tightening flag to decide whether to use dual tightening techniques at node level. Note that this only porvides valid tightenings if your function is convex! Per default, this is true.
• global_dual_tightening flag to decide whether to generate dual tightenings from new solutions that are gloablly valid. Per default, this is true.
• strong_convexity strong convexity parameter of the objective f, used for tightening the dual bound at every node. Per default, this is set to 0.0.
• sharpness_constant - the constant M > 0 for (θ, M)-sharpness. f is (θ, M)-sharpness: f satisfies min_{x^* ∈ X^*} || x - x^* || ≤ M (f(x) - f^(x^*))^θ where X^* is the set of minimizer of f. Note that tightenings using sharpness are only valid if the problem has a unique minimizer, i.e. f is stricly convex! Per default, this is set to 0.0.
• sharpness_exponent - the exponent θ ∈ [0, 1/2] for (θ, M)-sharpness. Per default, this is set to Inf.
• propagate_bounds optional function that allows the user to propagate and tighten bounds depending on the node. Receives the tree and the node as input.

settings_tolerances(mode::Mode;...)

Set the tolerances for the Frank-Wolfe algorithm. These are tolerances both for the Branch-and-Bound tree as well as for the Frank-Wolfe variant used as node solver.

Requires:

• mode the mode of the algorithm. See the Boscia.Mode enum for the available modes. If no mode is provided, the default mode is used.

Returns:

• Dict of tolerances for the Frank-Wolfe algorithm.

Available settings:

• fw_epsilon the solving precision of Frank-Wolfe at the root node.
• dual_gap absolute dual gap. If the difference between the incumbent and the lower bound reaches this value, the algorithm stops. Per default, this is set to 1e-6.
• rel_dual_gap relative dual gap. If the difference between the incumbent and the lower bound reaches this value, the algorithm stops. Per default, this is set to 1e-2.
• 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. Per default, this is set to 0.8.
• min_number_lower if not Inf, evaluation of a node is stopped if at least min_number_lower open nodes have a better lower bound. Per default, this is set to Inf.
• min_node_fw_epsilon smallest fw epsilon tolerance, see also dual_gap_decay_factor. Per default, this is set to 1e-6.