GitHub

The Bounded Linear Minimization Oracle (BLMO)

The Bounded Linear Minimization Oracle (BLMO) is an oracle solving the problem

\[\begin{aligned} v \in \arg\min & \; \langle x, d \rangle \\ \text{s.t} & \; x\in C \\ & \; x_I \in \mathbb{Z}^{|I|} \cap [l,u] %\text{ where } x \in X \subset \mathbb{R}, \, x_I \in \mathbb{Z}^{|I|} \end{aligned}\]

where the direction $d$ is usually the gradient evaluated at a certain point. The bounds are specified at the node level and correspond to bounds obtained by branching.

General BLMO Interface

In the following, the functions for the general BLMO interface are listed. Functions without signature needs to be implemented by a new BLMO type. Functions with signature are optional and are usually for statistics and additional safety checks.

Boscia.LMOStatus — Type

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

source
Boscia.build_LMO_correct — Method
build_LMO_correct(lmo::LinearMinimizationOracle, node_bounds)

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

source
Boscia.check_feasibility — Method
check_feasibility(lmo::LinearMinimizationOracle)

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

source
Boscia.find_best_solution — Method
find_best_solution(f::Function, lmo::LinearMinimizationOracle, vars, domain_oracle)

Find best solution from the solving process.

source
Boscia.free_model — Method
free_model(lmo::LinearMinimizationOracle)

Free model data from previous solve (if necessary).

source
Boscia.get_LMO_solve_data — Method
get_LMO_solve_data(lmo::LinearMinimizationOracle)

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

source
Boscia.get_tol — Method
get_tol(lmo::LinearMinimizationOracle)

Get solving tolerance for the LMO.

source
Boscia.get_variables_pointers — Method
get_variables_pointers(lmo::LinearMinimizationOracle, 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.

source
Boscia.is_indicator_feasible — Method
is_indicator_feasible(lmo::LinearMinimizationOracle, v; atol=1e-6, rtol=1e-6)

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

source
Boscia.is_linear_feasible — Function

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

source
Boscia.is_valid_split — Method
is_valid_split(tree::Bonobo.BnBTree, lmo::LinearMinimizationOracle, vidx::Int)

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

source

MathOptInterface (MOI) BLMO

With this BLMO type, any (MIP) solver that provides an interface to MathOptInterface and JuMP can be used in Boscia. Note that we only require the feasible region, i.e. no objective has to be set.

Boscia.MathOptBLMO — Method
MathOptBLMO(lmo::FrankWolfe.MathOptLMO)

Build an instance of MathOptBLMO from a FrankWolfe.MathOptLMO.

source
Base.convert — Method

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

source
Bonobo.get_branching_variable — Method
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.

source
Boscia.check_feasibility — Method
check_feasibility(blmo::MathOptBLMO)

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

source
Boscia.find_best_solution — Method
find_best_solution(f::Function, lmo::FrankWolfe.MathOptLMO, vars, domain_oracle)

Find best solution from the solving process.

source
Boscia.find_best_solution — Method
 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.

source
Boscia.free_model — Method
 free_model(blmo::MathOptBLMO)

Free model data from previous solve (if necessary).

source
Boscia.get_bound — Method
get_bound(blmo::MathOptBLMO, c_idx, sense::Symbol)

Read bound value for c_idx.

source
Boscia.get_int_var — Method
 get_int_var(blmo::MathOptBLMO, c_idx)

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

source
Boscia.get_list_of_variables — Method
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.

source
Boscia.get_variables_pointers — Method
get_variables_pointers(blmo, tree)

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

source
Boscia.is_bound_in — Method
is_bound_in(blmo::MathOptBLMO, c_idx, bounds)

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

source
Boscia.is_constraint_on_int_var — Method
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).

source
Boscia.is_indicator_feasible — Method
is_indicator_feasible(lmo::FrankWolfe.MathOptLMO, v; atol=1e-6, rtol=1e-6)

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

source
Boscia.is_valid_split — Method
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.

source
Boscia.set_bound! — Method
set_bound!(blmo::MathOptBLMO, c_idx, value, sense::Symbol)

Change the value of the bound c_idx.

source
Boscia.solve — Method

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

source

Managed BLMO

Sometimes the linear problem over the feasible region can be computed via a combinatorial algorithm that is more efficient than formulating the problem as a MIP. If one does not want to implement the BLMO interface from scratch which requires multiple methods to be provided, we provide the ManagedBLMO. It handles the bound management, so that the user has to implement only a few methods.

Boscia.ManagedLMO — Type
ManagedLMO{LMO<:FrankWolfe.LinearMinimizationOracle} <: FrankWolfe.LinearMinimizationOracle

A Linear Minimization Oracle wrapper that manages the bounds.

  • lmo a FrankWolfe.LinearMinimizationOracle.
  • 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.
source
Boscia.SimpleBoundableLMO — Type
SimpleBoundableLinearMinimizationOracle

A "simple" LMO 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.

WILL BE DEPRECATED!

source
Boscia.bounded_compute_extreme_point — Function
bounded_compute_extreme_point(lmo::LinearMinimizationOracle, d, lb, ub, int_vars; kwargs...)

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.

source
Boscia.is_simple_linear_feasible — Function
is_simple_linear_feasible(lmo::LinearMinimizationOracle, v::AbstractVector)

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.

source

Polytopes

Here are some preimplemented polytopes. We have the hypercube, the unit simplex and the probability simplex.

Boscia.CubeLMO — Type
CubeSimpleLMO{T}(lower_bounds, upper_bounds, int_vars)

Hypercube with lower and upper bounds implementing the SimpleBoundableLMO interface.

source
Boscia.ReverseKnapsackLMO — Type
ReverseKnapsackLMO(N, upper_bounds)

BLMO denotes the reverse Knapsack constraint: ∑ x ≥ N. We assume x ≥ 0. Explicit upper bounds are needed, otherwise the feasible region is unbounded.

source
Boscia.bounded_compute_extreme_point — Method
 bounded_compute_extreme_point(sblmo::CubeSimpleLMO, d, lb, ub, int_vars; kwargs...)

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

source
Boscia.bounded_compute_extreme_point — Method
bounded_compute_extreme_point(lmo::ProbabilitySimplexLMO, d, lb, ub, int_vars; kwargs...)

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

source
Boscia.bounded_compute_extreme_point — Method
bounded_compute_extreme_point(lmo::UnitSimplexSimpleLMO, 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.

source
Boscia.bounded_compute_inface_extreme_point — Method

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.

source
Boscia.bounded_dicg_maximum_step — Method

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.

source
Boscia.rounding_hyperplane_heuristic — Method
 rounding_hyperplane_heuristic(tree::Bonobo.BnBTree, tlmo::TimeTrackingLMO{ManagedBoundedLMO{ProbabilitySimplexLMO}}, x)

Hyperplane-aware rounding for the probability simplex.

source
Boscia.rounding_hyperplane_heuristic — Method
rounding_hyperplane_heuristic(tree::Bonobo.BnBTree, tlmo::TimeTrackingLMO{ManagedBoundedLMO{UnitSimplexLMO}}, x)

Hyperplane-aware rounding for the unit simplex.

source

Time Tracking BLMO Wrapper

This wrapper keeps track of the statistics like solving time of the BLMO, the number of calls etc.

Boscia.TimeTrackingLMO — Type
TimeTrackingLMO{LMO<:LinearMinimizationOracle} <: FrankWolfe.LinearMinimizationOracle

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

source
Boscia.reset! — Method
reset!(tlmo::TimeTrackingLMO)

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

source

Build LMO

Given the global bounds on the integer variables and the bounds at the node level, this builds the BLMO instance for the specific node. This way, the BLMO can be stored in the tree as opposed to every node having a copy of it.

Boscia.build_LMO — Method

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

Integer Bounds

The data structure that records the bounds on the integer/binary variables.

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