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 30 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
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 > &	add_presolver (const Presolvers::AbstractPresolver &t_presolver)
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_presolve (bool t_value)
BranchAndBound< idol::DefaultNodeInfo > &	with_infeasible_or_unbounded_info (bool t_value)
BranchAndBound< idol::DefaultNodeInfo > &	with_tol_mip_relative_gap (double t_tol_mip_relative_gap)
BranchAndBound< idol::DefaultNodeInfo > &	with_tol_mip_absolute_gap (double t_tol_mip_absolute_gap)
BranchAndBound< idol::DefaultNodeInfo > &	with_tol_integer (double t_tol_integer)
BranchAndBound< idol::DefaultNodeInfo > &	with_tol_feasibility (double t_tol_feasibility)
BranchAndBound< idol::DefaultNodeInfo > &	with_tol_optimality (double t_tol_optimality)
BranchAndBound< idol::DefaultNodeInfo > &	conditional (bool t_conditional_value, const std::function< void(BranchAndBound< idol::DefaultNodeInfo > &)> &t_if)
virtual Optimizer *	operator() (const Model &t_model) const
template<class T>
T &	as ()
template<class T>
const T &	as () const
template<class T>
bool	is () const

Protected Methods
Optimizer *	create (const Model &t_model) const override
BranchAndBound< idol::DefaultNodeInfo > &	crtp ()

Protected Attributes
std::optional< bool >	m_logs
std::optional< double >	m_time_limit
std::optional< unsigned int >	m_thread_limit
std::optional< unsigned int >	m_iteration_count_limit
std::optional< double >	m_best_bound_stop
std::optional< double >	m_best_obj_stop
std::optional< bool >	m_presolve
std::optional< bool >	m_infeasible_or_unbounded_info
std::optional< double >	m_tol_mip_relative_gap
std::optional< double >	m_tol_mip_absolute_gap
std::optional< double >	m_tol_integer
std::optional< double >	m_tol_feasibility
std::optional< double >	m_tol_optimality

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 51 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 334 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 263 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 240 of file BranchAndBound.h.

add_presolver()

template<class NodeT>

idol::BranchAndBound< NodeT > & idol::BranchAndBound< NodeT >::add_presolver

(

const Presolvers::AbstractPresolver &

t_presolver

)

Definition at line 245 of file BranchAndBound.h.

as() [1/2]

template<class T>

T & idol::OptimizerFactory::as ( )

inlineinherited

Definition at line 46 of file OptimizerFactory.h.

as() [2/2]

template<class T>

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

inlineinherited

Definition at line 54 of file OptimizerFactory.h.

clone()

template<class NodeT>

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

nodiscardoverridevirtual

Implements idol::OptimizerFactory.

Definition at line 401 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

Definition at line 88 of file OptimizerFactory.h.

create()

template<class NodeT>

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

nodiscardoverrideprotectedvirtual

Implements idol::OptimizerFactory.

Definition at line 355 of file BranchAndBound.h.

crtp()

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

inlineprotectedinherited

Definition at line 70 of file OptimizerFactory.h.

is()

template<class T>

bool idol::OptimizerFactory::is ( ) const

inlinenodiscardinherited

Definition at line 62 of file OptimizerFactory.h.

operator+=()

template<class NodeT>

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

(

const OptimizerFactory &

t_node_optimizer

)

Definition at line 234 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 216 of file BranchAndBound.h.

with_best_bound_stop()

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

inherited

Definition at line 77 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

Definition at line 78 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 310 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 305 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

Definition at line 80 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

Definition at line 76 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 222 of file BranchAndBound.h.

with_logs()

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

inherited

Definition at line 73 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 322 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 291 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 285 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

Definition at line 79 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 251 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 271 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

Definition at line 75 of file OptimizerFactory.h.

with_time_limit()

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

inherited

Definition at line 74 of file OptimizerFactory.h.

with_tol_feasibility()

BranchAndBound< idol::DefaultNodeInfo > & idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::with_tol_feasibility ( double t_tol_feasibility )

inherited

Definition at line 85 of file OptimizerFactory.h.

with_tol_integer()

BranchAndBound< idol::DefaultNodeInfo > & idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::with_tol_integer ( double t_tol_integer )

inherited

Definition at line 84 of file OptimizerFactory.h.

with_tol_mip_absolute_gap()

BranchAndBound< idol::DefaultNodeInfo > & idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::with_tol_mip_absolute_gap ( double t_tol_mip_absolute_gap )

inherited

Definition at line 83 of file OptimizerFactory.h.

with_tol_mip_relative_gap()

BranchAndBound< idol::DefaultNodeInfo > & idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::with_tol_mip_relative_gap ( double t_tol_mip_relative_gap )

inherited

Definition at line 82 of file OptimizerFactory.h.

with_tol_optimality()

BranchAndBound< idol::DefaultNodeInfo > & idol::OptimizerFactoryWithDefaultParameters< BranchAndBound< idol::DefaultNodeInfo > >::with_tol_optimality ( double t_tol_optimality )

inherited

Definition at line 86 of file OptimizerFactory.h.

Member Data Documentation

m_best_bound_stop

std::optional<double> idol::OptimizerFactory::m_best_bound_stop

protectedinherited

Definition at line 27 of file OptimizerFactory.h.

m_best_obj_stop

std::optional<double> idol::OptimizerFactory::m_best_obj_stop

protectedinherited

Definition at line 28 of file OptimizerFactory.h.

m_infeasible_or_unbounded_info

std::optional<bool> idol::OptimizerFactory::m_infeasible_or_unbounded_info

protectedinherited

Definition at line 30 of file OptimizerFactory.h.

m_iteration_count_limit

std::optional<unsigned int> idol::OptimizerFactory::m_iteration_count_limit

protectedinherited

Definition at line 26 of file OptimizerFactory.h.

m_logs

std::optional<bool> idol::OptimizerFactory::m_logs

protectedinherited

Definition at line 23 of file OptimizerFactory.h.

m_presolve

std::optional<bool> idol::OptimizerFactory::m_presolve

protectedinherited

Definition at line 29 of file OptimizerFactory.h.

m_thread_limit

std::optional<unsigned int> idol::OptimizerFactory::m_thread_limit

protectedinherited

Definition at line 25 of file OptimizerFactory.h.

m_time_limit

std::optional<double> idol::OptimizerFactory::m_time_limit

protectedinherited

Definition at line 24 of file OptimizerFactory.h.

m_tol_feasibility

std::optional<double> idol::OptimizerFactory::m_tol_feasibility

protectedinherited

Definition at line 35 of file OptimizerFactory.h.

m_tol_integer

std::optional<double> idol::OptimizerFactory::m_tol_integer

protectedinherited

Definition at line 34 of file OptimizerFactory.h.

m_tol_mip_absolute_gap

std::optional<double> idol::OptimizerFactory::m_tol_mip_absolute_gap

protectedinherited

Definition at line 33 of file OptimizerFactory.h.

m_tol_mip_relative_gap

std::optional<double> idol::OptimizerFactory::m_tol_mip_relative_gap

protectedinherited

Definition at line 32 of file OptimizerFactory.h.

m_tol_optimality

std::optional<double> idol::OptimizerFactory::m_tol_optimality

protectedinherited

Definition at line 36 of file OptimizerFactory.h.