The Bounded Linear Minimization Oracle (BLMO)

Enum encoding the status of the Bounded Linear Minimization Oracle. Currently available: OPTIMAL, INFEASIBLE and UNBOUNDED.

Supertype for the Bounded Linear Minimization Oracles (BLMO).

Add bound constraint.

build_LMO_correct(blmo::BoundedLinearMinimizationOracle, node_bounds)

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

Read global bounds from the problem.

check_feasibility(blmo::BoundedLinearMinimizationOracle)

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

check_infeasible_vertex(blmo::BoundedLinearMinimizationOracle, tree)

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

Delete bounds.

find_best_solution(f::Function, blmo::BoundedLinearMinimizationOracle, vars, domain_oracle)

Find best solution from the solving process.

free_model(blmo::BoundedLinearMinimizationOracle)

Free model data from previous solve (if necessary).

get_BLMO_solve_data(blmo::BoundedLinearMinimizationOracle)

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

Read bound value for c_idx.

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 the list of lower bounds.

get_tol(blmo::BoundedLinearMinimizationOracle)

Get solving tolerance for the BLMO.

Get the list of upper bounds.

get_variables_pointers(blmo::BoundedLinearMinimizationOracle, tree)

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.

Has variable an integer constraint?

indicator_present(blmo::BoundedLinearMinimizationOracle)

Are indicator constraints present?

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

is_indicator_feasible(blmo::BoundedLinearMinimizationOracle, v; atol=1e-6, rtol=1e-6)

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

Is a given point a on the minimal face containing the given x?

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

is_valid_split(tree::Bonobo.BnBTree, blmo::BoundedLinearMinimizationOracle, vidx::Int)

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

Change the value of the bound c_idx.

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

Implement FrankWolfe.compute_inface_extreme_point

Given a direction d and feasible point x solves the problem min_a d^T a where a has to be an integer feasible point and on the minimal face containing x

Implement FrankWolfe.dicg_maximum_step

Given a direction d and feasible point x solves the problem argmax_γ (x - γ * d) ∈ P where P is feasible set

Implement FrankWolfe.is_decomposition_invariant_oracle

Check if necessary DICG-specific orcales are implemented.

MathOptBLMO(lmo::FrankWolfe.MathOptLMO)

Build an instance of MathOptBLMO from a FrankWolfe.MathOptLMO.

Convert object of Type FrankWolfe.MathOptLMO into Boscia.MathOptBLMO and viceversa.

Bonobo.get_branching_variable(tree::Bonobo.BnBTree, branching::PartialStrongBranching{MathOptBLMO{OT}}, node::Bonobo.AbstractNode,) where {OT<:MOI.AbstractOptimizer}

Behavior for strong branching. Note that in constrast to the ManagedBLMO type, we filter out the integer and binary constraints as solving general MIP in strong branching would be very expensive.

add_bound_constraint!(blmo::MathOptBLMO, key, value, sense::Symbol)

Add bound constraint.

build_LMO_correct(blmo, node_bounds)

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

build_global_bounds(blmo::MathOptBLMO, integer_variables)

Read global bounds from the problem

check_feasibility(blmo::MathOptBLMO)

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

 check_infeasible_vertex(blmo::MathOptBLMO, tree)

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

delete_bounds!(blmo::MathOptBLMO, cons_delete)

Delete bounds.

explicit_bounds_binary_var(blmo::MathOptBLMO, global_bounds::IntegerBounds)

Add explicit bounds for binary variables.

find_best_solution(f::Function, blmo::MathOptBLMO, vars, domain_oracle)

Find best solution from the solving process.

 function find_best_solution(f::Function, o::MOI.AbstractOptimizer, vars::Vector{MOI.VariableIndex}, domain_oracle,)

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.

 free_model(blmo::MathOptBLMO)

Free model data from previous solve (if necessary).

get_BLMO_solve_data(blmo::MathOptBLMO)

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

get_binary_variables(blmo::MathOptBLMO)

Get list of binary variables.

get_bound(blmo::MathOptBLMO, c_idx, sense::Symbol)

Read bound value for c_idx.

 get_int_var(blmo::MathOptBLMO, c_idx)

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

 get_integer_variables(blmo::MathOptBLMO)

Get list of integer variables.

get_list_of_variables(blmo::MathOptBLMO)

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_lower_bound_list(blmo::MathOptBLMO)

Get the list of lower bounds.

 get_tol(blmo::MathOptBLMO)

Get solving tolerance for the BLMO.

get_upper_bound_list(blmo::MathOptBLMO)

Get the list of upper bounds.

 get_variables_pointers(blmo::MathOptBLMO, tree)

List of all variable pointers. Depends on how you save your variables internally. Is used in find_best_solution.

has_binary_constraint(blmo::MathOptBLMO, idx::Int)

Has variable a binary constraint?

has_integer_constraint(blmo::MathOptBLMO, idx::Int)

Does the variable have an integer constraint?

indicator_present(blmo::MathOptBLMO)

Are indicator constraints present?

is_bound_in(blmo::MathOptBLMO, c_idx, bounds)

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

is_constraint_on_int_var(blmo::MathOptBLMO, c_idx, int_vars)

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

is_indicator_feasible(blmo::MathOptBLMO, v; atol=1e-6, rtol=1e-6)

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

is_linear_feasible(blmo::MathOptBLMO, v::AbstractVector)

Is a given point v linear feasible for the model?

is_valid_split(tree::Bonobo.BnBTree, blmo::MathOptBLMO, vidx::Int)

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

set_bound!(blmo::MathOptBLMO, c_idx, value, sense::Symbol)

Change the value of the bound c_idx.

The solve function receiving a FrankWolfe.MathOptLMO. Converts the lmo into an instance of Boscia.MathOptBLMO and calls the main solve function.

compute_extreme_point(blmo::MathOptBLMO, d; kwargs...)

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

ManagedBoundedLMO{SBLMO<:SimpleBoundableLMO} <: BoundedLinearMinimizationOracle

A Bounded Linear Minimization Oracle that manages the bounds.

• simple_lmo an LMO of type Simple Boundable LMO.
• 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 Inf.
• n total number of variables.
• int_vars list of indices of the integer variables.
• solving_time the time to evaluate compute_extreme_point.

SimpleBoundableLinearMinimizationOracle

A "simple" BLMO that computes the extreme point given a linear objective and the node specific bounds on the integer variables. Can be stateless since all of the bound management is done by the ManagedBoundedLMO.

bounded_compute_extreme_point

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

is_simple_linear_feasible

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.

CubeSimpleBLMO{T}(lower_bounds, upper_bounds)

Hypercube with lower and upper bounds implementing the SimpleBoundableLMO interface.

ProbablitySimplexSimpleBLMO(N)

The scaled probability simplex with ∑ x = N.

UnitSimplexSimpleBLMO(N)

The scaled unit simplex with ∑ x ≤ N.

 bounded_compute_extreme_point(sblmo::CubeSimpleBLMO, d, lb, ub, int_vars; kwargs...)

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

bounded_compute_extreme_point(sblmo::ProbabilitySimplexSimpleBLMO, d, lb, ub, int_vars; kwargs...)

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

bounded_compute_extreme_point(sblmo::UnitSimplexSimpleBLMO, d, lb, ub, int_vars; kwargs...)

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

If the entry in x is at the boundary, choose the corresponding bound. Otherwise, if the entry in direction is positve, choose the lower bound. Else, choose the upper bound.

Fix the corresponding entries to the boudary based on the given x. Assign the largest possible values to the unfixed entries corresponding to the smallest entries of d.

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

Compute the maximum step size for each entry and return the minium of all the possible step sizes.

Compute the maximum step size for each entry and return the minium of all the possible step sizes.

Compute the maximum step size for each entry and the sum of entries should satisfy inequality constraint. Return the minium of all the possible step sizes.

 rounding_hyperplane_heuristic(tree::Bonobo.BnBTree, tlmo::TimeTrackingLMO{ManagedBoundedLMO{ProbabilitySimplexSimpleBLMO}}, x)

Hyperplane-aware rounding for the probability simplex.

rounding_hyperplane_heuristic(tree::Bonobo.BnBTree, tlmo::TimeTrackingLMO{ManagedBoundedLMO{UnitSimplexSimpleBLMO}}, x)

Hyperplane-aware rounding for the unit simplex.

TimeTrackingLMO{BLMO<:BoundedLinearMinimizationOracle} <: FrankWolfe.LinearMinimizationOracle

A wrapper for the BLMO tracking the solving time, number of calls etc. Is created in Boscia itself.

TimeTrackingLMO(blmo::BoundedLinearMinimizationOracle, int_vars)

Constructor with just the blmo.

TimeTrackingLMO(blmo::BoundedLinearMinimizationOracle)

Constructor with just the blmo.

reset!(tlmo::TimeTrackingLMO)

If we want to reset the info between nodes in the Branch-and-Bound tree.

FrankWolfe.compute_extreme_point(tlmo::TimeTrackingLMO, d; kwargs...)

Compute the extreme point and collect statistics.

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)

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.