idol::BranchAndBound< NodeT > Class Template Reference

#include <BranchAndBound.h>

Description

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

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.

Definition at line 29 of file BranchAndBound.h.

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

Public Methods
	BranchAndBound ()=default
	BranchAndBound (const BranchAndBound &t_rhs)
BranchAndBound< NodeT > &	with_node_optimizer (const OptimizerFactory &t_node_optimizer)
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)
template<class BranchingRuleFactoryT>
only_if_has_Strategy< BranchAndBound< NodeT > &, BranchingRuleFactoryT >	with_branching_rule (const BranchingRuleFactoryT &t_branching_rule)
BranchAndBound< NodeT > &	with_node_selection_rule (const NodeSelectionRuleFactory< NodeT > &t_node_selection)
template<class NodeSelectionRuleFactoryT>
only_if_has_Strategy< BranchAndBound< NodeT > &, NodeSelectionRuleFactoryT >	with_node_selection_rule (const NodeSelectionRuleFactoryT &t_node_selection_rule)
	BranchAndBound (BranchAndBound &&) noexcept=default
BranchAndBound &	operator= (const BranchAndBound &)=delete
BranchAndBound &	operator= (BranchAndBound &&) noexcept=delete
Optimizer *	operator() (const Model &t_model) const override
OptimizerFactory *	clone () const override
BranchAndBound< NodeT > &	with_subtree_depth (unsigned int t_depth)
BranchAndBound< NodeT > &	with_logger (const Logs::BranchAndBound::Factory< NodeT > &t_log_factory)
BranchAndBound< NodeT > &	add_callback (const BranchAndBoundCallbackFactory< NodeT > &t_callback)
BranchAndBound< NodeT > &	add_callback (const CallbackFactory &t_callback)
BranchAndBound< NodeT > &	with_root_node_info (const NodeT &t_root_node_info)
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)
BranchAndBound< idol::DefaultNodeInfo > &	with_time_limit (double t_time_limit)
BranchAndBound< idol::DefaultNodeInfo > &	with_thread_limit (unsigned int t_max_n_threads)
BranchAndBound< idol::DefaultNodeInfo > &	with_iteration_limit (unsigned int t_iteration_count_limit)
BranchAndBound< idol::DefaultNodeInfo > &	with_best_bound_stop (double t_best_bound_stop)
BranchAndBound< idol::DefaultNodeInfo > &	with_best_obj_stop (double t_user_best_obj)
BranchAndBound< idol::DefaultNodeInfo > &	with_relative_gap_tolerance (double t_relative_gap_tolerance)
BranchAndBound< idol::DefaultNodeInfo > &	with_absolute_gap_tolerance (double t_absolute_gap_tolerance)
BranchAndBound< idol::DefaultNodeInfo > &	with_presolve (bool t_value)
BranchAndBound< idol::DefaultNodeInfo > &	with_infeasible_or_unbounded_info (bool t_value)
BranchAndBound< idol::DefaultNodeInfo > &	conditional (bool t_conditional_value, const std::function< void(BranchAndBound< idol::DefaultNodeInfo > &)> &t_if)
template<class T>
T &	as ()
template<class T>
const T &	as () const
template<class T>
bool	is () const

Protected Methods
BranchAndBound< idol::DefaultNodeInfo > &	crtp ()
void	handle_default_parameters (Optimizer *t_optimizer) const

Member Typedef Documentation

only_if_has_Strategy

template<class NodeT = idol::DefaultNodeInfo>

template<class ReturnT, class T>

using idol::BranchAndBound< NodeT >::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>()).

Definition at line 47 of file BranchAndBound.h.

Constructor & Destructor Documentation

BranchAndBound() [1/2]

template<class NodeT = idol::DefaultNodeInfo>

idol::BranchAndBound< NodeT >::BranchAndBound ( )

default

Creates a new branch-and-bound algorithm.

Example:

model.use( BranchAndBound() );

BranchAndBound() [2/2]

template<class NodeT>

idol::BranchAndBound< NodeT >::BranchAndBound

(

const BranchAndBound< NodeT > &

t_rhs

)

Copy constructor

Parameters

t_rhs

the object to copy

Definition at line 324 of file BranchAndBound.h.

Methods Documentation

add_callback() [1/2]

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::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

Definition at line 253 of file BranchAndBound.h.

add_callback() [2/2]

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::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

Definition at line 236 of file BranchAndBound.h.

as() [1/2]

template<class T>

T & idol::OptimizerFactory::as ( )

inlineinherited

Definition at line 45 of file OptimizerFactory.h.

as() [2/2]

template<class T>

const T & idol::OptimizerFactory::as ( ) const

inlineinherited

Definition at line 53 of file OptimizerFactory.h.

clone()

template<class NodeT>

idol::OptimizerFactory * idol::BranchAndBound< NodeT >::clone ( ) const

nodiscardoverridevirtual

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)

Implements idol::OptimizerFactory.

Definition at line 385 of file BranchAndBound.h.

conditional()

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

inherited

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

Definition at line 239 of file OptimizerFactory.h.

crtp()

BranchAndBound< idol::DefaultNodeInfo > & idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::crtp ( )

inlineprotectedinherited

Definition at line 79 of file OptimizerFactory.h.

handle_default_parameters()

void idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::handle_default_parameters ( Optimizer * t_optimizer ) const

protectedinherited

Definition at line 82 of file OptimizerFactory.h.

is()

template<class T>

bool idol::OptimizerFactory::is ( ) const

inlinenodiscardinherited

Definition at line 61 of file OptimizerFactory.h.

operator()()

template<class NodeT>

idol::Optimizer * idol::BranchAndBound< NodeT >::operator() ( const Model & t_model ) const

overridevirtual

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

Implements idol::OptimizerFactory.

Definition at line 341 of file BranchAndBound.h.

operator+=()

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::BranchAndBound< NodeT >::operator+=

(

const OptimizerFactory &

t_node_optimizer

)

Definition at line 230 of file BranchAndBound.h.

set_node_optimizer()

template<class NodeT>

void idol::BranchAndBound< NodeT >::set_node_optimizer

(

const OptimizerFactory &

t_node_optimizer

)

Definition at line 212 of file BranchAndBound.h.

with_absolute_gap_tolerance()

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

inherited

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

Definition at line 193 of file OptimizerFactory.h.

with_best_bound_stop()

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

inherited

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

Definition at line 150 of file OptimizerFactory.h.

with_best_obj_stop()

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

inherited

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

Definition at line 165 of file OptimizerFactory.h.

with_branching_rule() [1/3]

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::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

Definition at line 300 of file BranchAndBound.h.

with_branching_rule() [2/3]

template<class NodeT = idol::DefaultNodeInfo>

template<class BranchingRuleFactoryT>

idol::BranchAndBound< NodeT >::template only_if_has_Strategy< idol::BranchAndBound< NodeT > &, BranchingRuleFactoryT > idol::BranchAndBound< NodeT >::with_branching_rule

(

const BranchingRuleFactoryT &

t_branching_rule

)

Definition at line 295 of file BranchAndBound.h.

with_branching_rule() [3/3]

template<class NodeT = idol::DefaultNodeInfo>

template<class BranchingRuleFactoryT>

only_if_has_Strategy< BranchAndBound< NodeT > &, BranchingRuleFactoryT > idol::BranchAndBound< NodeT >::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

with_infeasible_or_unbounded_info()

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

inherited

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

Definition at line 220 of file OptimizerFactory.h.

with_iteration_limit()

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

inherited

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

Definition at line 135 of file OptimizerFactory.h.

with_logger()

template<class NodeT = idol::DefaultNodeInfo>

idol::BranchAndBound< NodeT > & idol::BranchAndBound< NodeT >::with_logger

(

const Logs::BranchAndBound< NodeT >::Factory< NodeT > &

t_log_factory

)

Definition at line 218 of file BranchAndBound.h.

with_logs()

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

inherited

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

Definition at line 96 of file OptimizerFactory.h.

with_node_optimizer()

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::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

Definition at line 312 of file BranchAndBound.h.

with_node_selection_rule() [1/3]

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::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

Definition at line 281 of file BranchAndBound.h.

with_node_selection_rule() [2/3]

template<class NodeT = idol::DefaultNodeInfo>

template<class NodeSelectionRuleFactoryT>

idol::BranchAndBound< NodeT >::template only_if_has_Strategy< idol::BranchAndBound< NodeT > &, NodeSelectionRuleFactoryT > idol::BranchAndBound< NodeT >::with_node_selection_rule

(

const NodeSelectionRuleFactoryT &

t_node_selection_rule

)

Definition at line 275 of file BranchAndBound.h.

with_node_selection_rule() [3/3]

template<class NodeT = idol::DefaultNodeInfo>

template<class NodeSelectionRuleFactoryT>

only_if_has_Strategy< BranchAndBound< NodeT > &, NodeSelectionRuleFactoryT > idol::BranchAndBound< NodeT >::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

with_presolve()

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

inherited

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

Definition at line 206 of file OptimizerFactory.h.

with_relative_gap_tolerance()

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

inherited

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

Definition at line 179 of file OptimizerFactory.h.

with_root_node_info()

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::BranchAndBound< NodeT >::with_root_node_info

(

const NodeT &

t_root_node_info

)

Definition at line 241 of file BranchAndBound.h.

with_subtree_depth()

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::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

Definition at line 261 of file BranchAndBound.h.

with_thread_limit()

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

inherited

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

Definition at line 122 of file OptimizerFactory.h.

with_time_limit()

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

inherited

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

Definition at line 109 of file OptimizerFactory.h.