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.

Doxygen¶

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> &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)¶

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &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

CRTP &conditional(bool t_conditional_value, const std::function<void(CRTP&)> &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

CRTP &conditional(bool t_conditional_value, const std::function<void(CRTP&)> &t_if, const std::function<void(CRTP&)> &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¶