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

• 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.
• variant the Frank-Wolfe variant to be used to solve the node problem. Options currently available are AwayFrankWolfe, Blended, BPCG and VanillaFrankWolfe.
• line_search specifies the line search method used in the FrankWolfe variant. Default is the Adaptive line search. For other available types, check the FrankWolfe.jl package.
• 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.
• lazy flag specifies whether the lazification of the Frank-Wolfe variant should be used. Per default true. Note that it has no effect on Vanilla 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.
• fw_epsilon the solving precision of Frank-Wolfe at the root node.
• verbose if true, logs and solution statistics are printed.
• dual_gap absolute dual gap. If reached, the algorithm stops.
• rel_dual_gap relative dual gap. If 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. On default, there is no time limit.
• 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.
• 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 Frank-Wolfe run.
• 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.
• min_node_fw_epsilon smallest fw epsilon tolerance, see also dual_gap_decay_factor.
• 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.
• min_fw_iterations the minimum number of Frank-Wolfe iterations performed in the node evaluation.
• max_iteration_post maximum number of iterations in the Frank-Wolfe run during postsolve.
• 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!
• global_dual_tightening flag to decide whether to generate dual tightenings from new solutions that are gloablly valid.
• bnb_callback an optional callback called after every node evaluation.
• 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.
• strong_convexity strong convexity parameter of the objective f, used for tightening the dual bound at every node.
• 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!
• sharpness_exponent - the exponent θ ∈ [0, 1/2] for (θ, M)-sharpness.
• 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 starting point has to be domain feasible for f. Additionally, the user has to provide a function domain_point, see below. Also, depending on the line search method, you might have to provide the domain oracle to it, too.
• 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.
• start_solution an initial solution can be provided if known. It will be used as the initial incumbent.
• fw_verbose if true, the Frank-Wolfe logs are printed at each node. Mostly meant for debugging.
• 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.
• custom_heuristics list of custom heuristics from the user.
• 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.
• 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 iterations in the Frank-Wolfe call for polishing new solutions.
• use_strong_lazy specifies strong lazification in DICG. Otherwise, weak version is used.
• use_DICG_warm_start if true, enables DICG-specific warm-start strategy.
• use_strong_warm_start if true, performs additional in-face check for vertices.
• build_dicg_start_point default generates a random feasible vertex.