idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
idol::BranchAndBound< NodeT > Class Template Reference

#include <BranchAndBound.h>

Inheritance diagram for idol::BranchAndBound< NodeT >:
Inheritance graph
Collaboration diagram for idol::BranchAndBound< NodeT >:
Collaboration graph

Public Types

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

Public Member Functions

 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
 
BranchAndBoundoperator= (const BranchAndBound &)=delete
 
BranchAndBoundoperator= (BranchAndBound &&) noexcept=delete
 
Optimizeroperator() (const Model &t_model) const override
 
OptimizerFactoryclone () 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)
 
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)
 
CRTP & with_time_limit (double t_time_limit)
 
CRTP & with_thread_limit (unsigned int t_max_n_threads)
 
CRTP & with_iteration_limit (unsigned int t_iteration_count_limit)
 
CRTP & with_best_bound_stop (double t_best_bound_stop)
 
CRTP & with_best_obj_stop (double t_user_best_obj)
 
CRTP & with_relative_gap_tolerance (double t_relative_gap_tolerance)
 
CRTP & with_absolute_gap_tolerance (double t_absolute_gap_tolerance)
 
CRTP & with_presolve (bool t_value)
 
CRTP & with_infeasible_or_unbounded_info (bool t_value)
 
CRTP & conditional (bool t_conditional_value, const std::function< void(CRTP &)> &t_if)
 
CRTP & conditional (bool t_conditional_value, const std::function< void(CRTP &)> &t_if, const std::function< void(CRTP &)> &t_else)
 
template<class T >
T & as ()
 
template<class T >
const T & as () const
 
template<class T >
bool is () const
 

Protected Member Functions

CRTP & crtp ()
 
const CRTP & crtp () const
 
void handle_default_parameters (Optimizer *t_optimizer) const
 

Detailed Description

template<class NodeT = idol::DefaultNodeInfo>
class idol::BranchAndBound< NodeT >
Template Parameters
NodeTthe 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.

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 46 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()=default

◆ BranchAndBound() [2/2]

template<class NodeT >
idol::BranchAndBound< NodeT >::BranchAndBound ( const BranchAndBound< NodeT > &  t_rhs)

Copy constructor

Parameters
t_rhsthe object to copy

Definition at line 310 of file BranchAndBound.h.

Member Function 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_callbackthe callback factory
Returns
the optimizer factory itself

Definition at line 239 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_callbackthe callback factory
Returns
the optimizer factory itself

Definition at line 234 of file BranchAndBound.h.

◆ as() [1/2]

template<class T >
T & idol::OptimizerFactory::as ( )
inlineinherited

Definition at line 44 of file OptimizerFactory.h.

◆ as() [2/2]

template<class T >
const T & idol::OptimizerFactory::as ( ) const
inlineinherited

Definition at line 52 of file OptimizerFactory.h.

◆ clone()

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

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 366 of file BranchAndBound.h.

◆ conditional() [1/2]

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::conditional ( bool  t_conditional_value,
const std::function< void(CRTP &)> &  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();
}
CRTP & conditional(bool t_conditional_value, const std::function< void(CRTP &)> &t_if)
Parameters
t_conditional_valueif true, the t_if lambda function is executed, if false, nothing happens.
t_iflambda function to execute in case t_conditional_value is true
Returns
the optimizer factory itself

Definition at line 273 of file OptimizerFactory.h.

◆ conditional() [2/2]

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::conditional ( bool  t_conditional_value,
const std::function< void(CRTP &)> &  t_if,
const std::function< void(CRTP &)> &  t_else 
)
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); },
[](auto& x){ x.with_presolve(false); })
model.use(algorithm);
model.optimize();
}
Parameters
t_conditional_valueif true, the t_if lambda function is executed, if false, the t_else lambda function is.
t_iflambda function to execute in case t_conditional_value is true
t_elselambda function to execute in case t_conditional_value is false
Returns
the optimizer factory itself

Definition at line 266 of file OptimizerFactory.h.

◆ crtp() [1/2]

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::crtp ( )
inlineprotectedinherited

Definition at line 78 of file OptimizerFactory.h.

◆ crtp() [2/2]

template<class CRTP >
const CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::crtp ( ) const
inlineprotectedinherited

Definition at line 79 of file OptimizerFactory.h.

◆ handle_default_parameters()

template<class CRTP >
void idol::OptimizerFactoryWithDefaultParameters< CRTP >::handle_default_parameters ( Optimizer t_optimizer) const
protectedinherited

Definition at line 398 of file OptimizerFactory.h.

◆ is()

template<class T >
bool idol::OptimizerFactory::is ( ) const
inlineinherited

Definition at line 60 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_modelThe model which the optimizer will solve
Returns
A new optimizer for the model

Implements idol::OptimizerFactory.

Definition at line 326 of file BranchAndBound.h.

◆ operator+=()

template<class NodeT >
idol::BranchAndBound< NodeT > & idol::BranchAndBound< NodeT >::operator+= ( const OptimizerFactory t_node_optimizer)

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

◆ with_absolute_gap_tolerance()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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()
CRTP & with_absolute_gap_tolerance(double t_absolute_gap_tolerance)
Parameters
t_absolute_gap_tolerancethe absolute gap tolerance
Returns
the optimizer factory itself

Definition at line 302 of file OptimizerFactory.h.

◆ with_best_bound_stop()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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);
CRTP & with_best_bound_stop(double t_best_bound_stop)
Parameters
t_best_bound_stopthe threshold
Returns
the optimizer factory itself

Definition at line 338 of file OptimizerFactory.h.

◆ with_best_obj_stop()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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);
CRTP & with_best_obj_stop(double t_user_best_obj)
Parameters
t_user_best_objthe threshold
Returns
the optimizer factory itself

Definition at line 326 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>()
BranchAndBound< NodeT > & with_branching_rule(const BranchingRuleFactory< NodeT > &t_branching_rule)
Parameters
t_branching_rulethe branching rule
Returns
the optimizer factory itself

Definition at line 286 of file BranchAndBound.h.

◆ with_branching_rule() [2/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:

Template Parameters
BranchingRuleFactoryTthe class containing a nested template class named Strategy
Parameters
t_branching_rulethe branching rule
Returns
the optimizer factory itself

◆ with_branching_rule() [3/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 281 of file BranchAndBound.h.

◆ with_infeasible_or_unbounded_info()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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()
Parameters
t_valuethe activation level
Returns
the optimizer factory itself

Definition at line 278 of file OptimizerFactory.h.

◆ with_iteration_limit()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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()
CRTP & with_iteration_limit(unsigned int t_iteration_count_limit)
Parameters
t_iteration_count_limitthe maximum number of iterations
Returns
the optimizer factory itself

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

◆ with_logs()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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_levelthe log_master level
t_log_colorthe output color
Returns
the optimizer factory itself

Definition at line 386 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_optimizerthe optimizer factory the node problems
Returns
the optimizer factory itself

Definition at line 298 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.

Parameters
t_node_selectionthe node selection rule
Returns
the optimizer factory itself

Definition at line 267 of file BranchAndBound.h.

◆ with_node_selection_rule() [2/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>()
BranchAndBound< NodeT > & with_node_selection_rule(const NodeSelectionRuleFactory< NodeT > &t_node_selection)
Template Parameters
NodeSelectionRuleFactoryTthe class containing a nested template class named Strategy
Parameters
t_node_selection_rulethe node selection rule
Returns
the optimizer factory itself

◆ with_node_selection_rule() [3/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 261 of file BranchAndBound.h.

◆ with_presolve()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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_valuethe activation level for the optimizer's get_param_presolve (0 for disabling, 1 for enabling)
Returns
the optimizer factory itself

Definition at line 290 of file OptimizerFactory.h.

◆ with_relative_gap_tolerance()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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%
CRTP & with_relative_gap_tolerance(double t_relative_gap_tolerance)
Parameters
t_relative_gap_tolerancethe relative gap tolerance
Returns
the optimizer factory itself

Definition at line 314 of file OptimizerFactory.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_depththe maximum sub-tree exploration depth
Returns
the optimizer factory itself

Definition at line 247 of file BranchAndBound.h.

◆ with_thread_limit()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::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()
CRTP & with_thread_limit(unsigned int t_max_n_threads)
Parameters
t_max_n_threadsthe number of threads which can be used
Returns
the optimizer factory itself

Definition at line 362 of file OptimizerFactory.h.

◆ with_time_limit()

template<class CRTP >
CRTP & idol::OptimizerFactoryWithDefaultParameters< CRTP >::with_time_limit ( double  t_time_limit)
inherited

Sets the time limit for the optimizer

Example:

auto algorithm = GLPK()
Parameters
t_time_limitthe time limit (in seconds)
Returns
the optimizer factory itself

Definition at line 374 of file OptimizerFactory.h.