BranchAndBound

This class is an optimizer factory which creates a new branch-and-bound algorithm. It can be used to create customized branch-and-bound algorithms with a large degree of freedom.

See also

If you are not familiar with optimizers and optimizer factories, please refer to this page.

Example

Here, we create a simple branch-and-bound algorithm where branching is done on integer variables which are being relaxed. Each node is solved by the external solver GLPK. Nodes are selected according to the “best-bound” rule while variables are selected according to the “most-infeasible” branching rule.

The created algorithm also incorporates sub-tree exploration of maximum depth 2.

model.use(
    BranchAndBound()
        .with_node_optimizer( GLPK::ContinuousRelaxation() )
        .with_branching_rule( MostInfeasible() )
        .with_node_selection_rule( BestBound() )
        .with_subtree_depth(2)
);

template<class NodeT = idol::DefaultNodeInfo>
class BranchAndBound : public idol::OptimizerFactoryWithDefaultParameters<BranchAndBound<idol::DefaultNodeInfo>>

Template Parameters:

NodeT – the class used to store nodes information. It is strongly advised to inherit from NodeVarInfo in order to create your own node type.

Public Types

template<class ReturnT, class T>
using only_if_has_Strategy = typename std::pair<typename T::template Strategy<NodeT>, ReturnT>::second_type

This type is used to exploit SFINAE in order to identify classes having a sub-class named Strategy<NodeInfoT>. This is used to make calls like .with_node_selection_rule(DepthFirst()); which will actually call .with_node_selection_rule(DepthFirst::Strategy<NodeInfoT>()).

Public Functions

BranchAndBound() = default

Creates a new branch-and-bound algorithm.

Example:

model.use( BranchAndBound() );

BranchAndBound(const BranchAndBound &t_rhs)

Copy constructor

Parameters:

t_rhs – the object to copy

BranchAndBound<NodeT> &with_node_optimizer(const OptimizerFactory &t_node_optimizer)

Sets the optimizer for solving each of the branch-and-bound tree nodes

Example:

auto algorithm = BranchAndBound()
                     .with_node_optimizer(GLPK::ContinuousRelaxation());

Parameters:

t_node_optimizer – the optimizer factory the node problems

Returns:

the optimizer factory itself

void set_node_optimizer(const OptimizerFactory &t_node_optimizer)

BranchAndBound<NodeT> &operator+=(const OptimizerFactory &t_node_optimizer)

BranchAndBound<NodeT> &with_branching_rule(const BranchingRuleFactory<NodeT> &t_branching_rule)

Sets the branching rule used to create child nodes

Example:

auto algorithm = BranchAndBound<NodeVarInfo>()
                     .with_branching_rule(MostInfeasible::Strategy<NodeVarInfo>());

Parameters:

t_branching_rule – the branching rule

Returns:

the optimizer factory itself

template<class BranchingRuleFactoryT>
only_if_has_Strategy<BranchAndBound<NodeT>&, BranchingRuleFactoryT> with_branching_rule(const BranchingRuleFactoryT &t_branching_rule)

Sets the branching rule used to create child nodes.

Here, the function is called only when BranchingRuleFactoryT has a nested template class named Strategy<NodeInfoT>. In such a case, the branching rule is created by calling BranchingRuleFactoryT::Strategy<NodeInfoT>(t_branching_rule). This is used to avoid the user repeating the node type NodeInfoT being used.

Example:

auto algorithm = BranchAndBound<NodeVarInfo>()
                     .with_branching_rule(MostInfeasible());

Template Parameters:

BranchingRuleFactoryT – the class containing a nested template class named Strategy

Parameters:

t_branching_rule – the branching rule

Returns:

the optimizer factory itself

BranchAndBound<NodeT> &with_node_selection_rule(const NodeSelectionRuleFactory<NodeT> &t_node_selection)

Sets the node selection rule to explore the branch and bound tree.

auto algorithm = BranchAndBound<NodeVarInfo>()
                     .with_node_selection(BestBound::Strategy<NodeVarInfo>());

Parameters:

t_node_selection – the node selection rule

Returns:

the optimizer factory itself

template<class NodeSelectionRuleFactoryT>
only_if_has_Strategy<BranchAndBound<NodeT>&, NodeSelectionRuleFactoryT> with_node_selection_rule(const NodeSelectionRuleFactoryT &t_node_selection_rule)

Sets the node selection rule to explore the branch and bound tree.

Here, the function is called only when NodeSelectionRuleFactoryT has a nested template class named Strategy<NodeInfoT>. In such a case, the node selection rule is created by calling NodeSelectionRuleFactoryT::Strategy<NodeInfoT>(t_node_selection_rule). This is used to avoid the user repeating the node type NodeInfoT being used.

Example:

auto algorithm = BranchAndBound<NodeVarInfo>()
                     .with_node_selection_rule(BestBound());

Template Parameters:

NodeSelectionRuleFactoryT – the class containing a nested template class named Strategy

Parameters:

t_node_selection_rule – the node selection rule

Returns:

the optimizer factory itself

BranchAndBound(BranchAndBound&&) noexcept = default

BranchAndBound &operator=(const BranchAndBound&) = delete

BranchAndBound &operator=(BranchAndBound&&) noexcept = delete

virtual Optimizer *operator()(const Model &t_model) const override

Creates and returns a new optimizer to solve the model given as parameter.

Parameters:

t_model – The model which the optimizer will solve

Returns:

A new optimizer for the model

virtual OptimizerFactory *clone() const override

Creates and return a copy of the optimizer factory. This is used for polymorphism.

Returns:

A copied object of the current object (i.e., *this)

BranchAndBound<NodeT> &with_subtree_depth(unsigned int t_depth)

Sets the depth for sub-tree exploration.

When a node is selected for branching, each of its children is explored. This exploration takes the form of a sub-tree exploration. When this parameter is set to 0, only the root node of this sub-tree is solved. Thus every child node are solved and the branch-and-bound algorithm is continued.

For strictly greater values of this parameter, the sub-tree is explored with a maximum depth equal to the value of this parameter.

For example, with a value of 1, each child node is solved along with its child nodes.

Example:

auto algorithm = BranchAndBound()
                     .with_subtree_depth(1);

Parameters:

t_depth – the maximum sub-tree exploration depth

Returns:

the optimizer factory itself

BranchAndBound<NodeT> &with_logger(const Logs::BranchAndBound::Factory<NodeT> &t_log_factory)

BranchAndBound<NodeT> &with_scaling(bool t_value)

BranchAndBound<NodeT> &add_callback(const BranchAndBoundCallbackFactory<NodeT> &t_callback)

Adds a callback which will be called by the optimizer.

Note that this method can be called multiple times so that multiple callbacks can be added.

auto algorithm = BranchAndBound()
                     .with_callback(IntegerMaster.rst());

Parameters:

t_callback – the callback factory

Returns:

the optimizer factory itself

BranchAndBound<NodeT> &add_callback(const CallbackFactory &t_callback)

Adds a (solver independent) callback which will be called by the optimizer.

Note that this method can be called multiple times so that multiple callbacks can be added.

Here, the Callback is automatically converted into a BranchAndBoundCallback<NodeInfoT>.

auto algorithm = BranchAndBound()
                     .with_callback(UserCutCallback(separation_model, my_cut));

Parameters:

t_callback – the callback factory

Returns:

the optimizer factory itself

template<class NodeSelectionRuleFactoryT>
idol::BranchAndBound<NodeT>::template only_if_has_Strategy<idol::BranchAndBound<NodeT>&, NodeSelectionRuleFactoryT> with_node_selection_rule(const NodeSelectionRuleFactoryT &t_node_selection_rule)

template<class BranchingRuleFactoryT>
idol::BranchAndBound<NodeT>::template only_if_has_Strategy<idol::BranchAndBound<NodeT>&, BranchingRuleFactoryT> with_branching_rule(const BranchingRuleFactoryT &t_branching_rule)

BranchAndBound<idol::DefaultNodeInfo> &with_logs(bool t_value)

Sets the log_master level and color for the optimizer

Example:

auto algorithm = GLPK()
                     .with_logs(true);

Parameters:

• t_log_level – the log_master level

• t_log_color – the output color

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_time_limit(double t_time_limit)

Sets the time limit for the optimizer

Example:

auto algorithm = GLPK()
                     .with_time_limit(3600);

Parameters:

t_time_limit – the time limit (in seconds)

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_thread_limit(unsigned int t_max_n_threads)

Sets the maximum number of threads which the optimizer can use

Example:

auto algorithm = GLPK()
                     .with_thread_limit(5);

Parameters:

t_max_n_threads – the number of threads which can be used

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_iteration_limit(unsigned int t_iteration_count_limit)

Sets the maximum number of iterations which the optimizer go through

Example:

auto algorithm = GLPK()
                     .with_iteration_limit(200);

Parameters:

t_iteration_count_limit – the maximum number of iterations

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_best_bound_stop(double t_best_bound_stop)

Sets a threshold on the best bound for stopping the optimizer. When the optimizer have found a best bound which is greater than this threshold, the optimizer stops.

Example:

const double my_known_best_obj = 0.;
auto algorithm = GLPK()
                     .with_best_bound_stop(my_known_best_obj);

Parameters:

t_best_bound_stop – the threshold

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_best_obj_stop(double t_user_best_obj)

Sets a threshold on the best objective value for stopping the optimizer. When the optimizer have found a best objective value which is less than this threshold, the optimizer stops.

Example:

const double my_known_best_bound = 0;
auto algorithm = GLPK()
                     .with_best_obj_stop(my_known_best_bound);

Parameters:

t_user_best_obj – the threshold

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_relative_gap_tolerance(double t_relative_gap_tolerance)

Sets the relative gap tolerance for the optimizer. When the optimizer proves that the relative optimality gap is less than this threshold, the optimizer stops.

Example:

auto algorithm = GLPK()
                     .with_relative_gap_tolerance(.05); // sets a gap tolerance of 5%

Parameters:

t_relative_gap_tolerance – the relative gap tolerance

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_absolute_gap_tolerance(double t_absolute_gap_tolerance)

Sets the absolute gap tolerance for the optimizer. When the optimizer proves that the absolute optimality gap is less than this threshold, the optimizer stops.

Example:

auto algorithm = GLPK()
                     .with_absolute_gap_tolerance(1e-4);

Parameters:

t_absolute_gap_tolerance – the absolute gap tolerance

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_presolve(bool t_value)

Sets the get_param_presolve activation for the optimizer.

Example:

auto algorithm = GLPK()
                     .with_presolve(false); // turns off get_param_presolve phase

Parameters:

t_value – the activation level for the optimizer’s get_param_presolve (0 for disabling, 1 for enabling)

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &with_infeasible_or_unbounded_info(bool t_value)

Sets the behaviour of the optimizer when a model is shown to be infeasible or unbounded. When set to true, the optimizer is forced to prove feasibility or unboundedness by providing a certificate.

Example:

auto algorithm = GLPK()
                     .with_infeasible_or_unbounded_info(true);

Parameters:

t_value – the activation level

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &conditional(bool t_conditional_value, const std::function<void(BranchAndBound<idol::DefaultNodeInfo>&)> &t_if)

Executes the lambda function given as second parameter if and only if its first argument is true. This function can be used to build different optimizer factories depending on some external variable.

Example:

for (const bool use_presolve : {true, false}) {
     auto algorithm = GLPK()
                         .conditional(use_presolve, [](auto& x){ x.with_presolve(true); })
      model.use(algorithm);
      model.optimize();
}

Parameters:

• t_conditional_value – if true, the t_if lambda function is executed, if false, nothing happens.

• t_if – lambda function to execute in case t_conditional_value is true

Returns:

the optimizer factory itself

BranchAndBound<idol::DefaultNodeInfo> &conditional(bool t_conditional_value, const std::function<void(BranchAndBound<idol::DefaultNodeInfo>&)> &t_if, const std::function<void(BranchAndBound<idol::DefaultNodeInfo>&)> &t_else)

Executes the lambda function given as second parameter if and only if its first argument is true. This function can be used to build different optimizer factories depending on some external variable.

Example:

for (const bool use_presolve : {true, false}) {
     auto algorithm = GLPK()
                         .conditional(use_presolve,
                                         [](auto& x){ x.with_presolve(true); },
                                         [](auto& x){ x.with_presolve(false); })
      model.use(algorithm);
      model.optimize();
}

Parameters:

• t_conditional_value – if true, the t_if lambda function is executed, if false, the t_else lambda function is.

• t_if – lambda function to execute in case t_conditional_value is true

• t_else – lambda function to execute in case t_conditional_value is false

Returns:

the optimizer factory itself

template<class T>
inline T &as()

template<class T>
inline const T &as() const

template<class T>
inline bool is() const