idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
idol::Optimizers::BranchAndBound< NodeInfoT > Class Template Reference
Inheritance diagram for idol::Optimizers::BranchAndBound< NodeInfoT >:
Inheritance graph
Collaboration diagram for idol::Optimizers::BranchAndBound< NodeInfoT >:
Collaboration graph

Public Member Functions

 BranchAndBound (const Model &t_model, const OptimizerFactory &t_node_optimizer, const BranchingRuleFactory< NodeInfoT > &t_branching_rule_factory, const NodeSelectionRuleFactory< NodeInfoT > &t_node_selection_rule_factory, AbstractBranchAndBoundCallbackI< NodeInfoT > *t_callback, const Logs::BranchAndBound::Factory< NodeInfoT > &t_logger_factory)
 
std::string name () const override
 
void solve (TreeNode &t_node, unsigned int t_relaxation_id) const
 
virtual void set_subtree_depth (unsigned int t_depth)
 
unsigned int subtree_depth () const
 
virtual void add_callback (BranchAndBoundCallback< NodeInfoT > *t_cb)
 
void submit_heuristic_solution (NodeInfoT *t_info)
 
void submit_lower_bound (double t_lower_bound)
 
unsigned int n_created_nodes () const
 
unsigned int n_solved_nodes () const
 
unsigned int n_active_nodes () const
 
const Modelrelaxation () const
 
Modelrelaxation ()
 
double root_node_best_bound () const
 
double root_node_best_obj () const
 
BranchingRule< NodeInfoT > & branching_rule ()
 
const BranchingRule< NodeInfoT > & branching_rule () const
 
bool has_incumbent () const
 
const TreeNodeincumbent () const
 
double get_var_primal (const Var &t_var) const override
 
double get_var_reduced_cost (const Var &t_var) const override
 
double get_var_ray (const Var &t_var) const override
 
double get_ctr_dual (const Ctr &t_ctr) const override
 
double get_ctr_farkas (const Ctr &t_ctr) const override
 
unsigned int get_n_solutions () const override
 
unsigned int get_solution_index () const override
 
void set_solution_index (unsigned int t_index) override
 
void terminate () override
 
SolutionStatus get_status () const override
 
SolutionReason get_reason () const override
 
double get_best_obj () const override
 
double get_best_bound () const override
 
double get_relative_gap () const override
 
double get_absolute_gap () const override
 

Protected Member Functions

void build () override
 
void hook_before_optimize () override
 
void hook_optimize () override
 
void hook_after_optimize () override
 
void add (const Var &t_var) override
 
void add (const Ctr &t_ctr) override
 
void add (const QCtr &t_ctr) override
 
void remove (const Var &t_var) override
 
void remove (const Ctr &t_ctr) override
 
void remove (const QCtr &t_ctr) override
 
void update () override
 
void write (const std::string &t_name) override
 
void detect_integer_objective ()
 
void create_relaxations ()
 
Node< NodeInfoT > create_root_node ()
 
void explore (TreeNode &t_node, unsigned int t_relaxation_id, SetOfActiveNodes &t_active_nodes, unsigned int t_step)
 
void analyze (const TreeNode &t_node, unsigned int t_relaxation_id, bool *t_explore_children_flag, bool *t_reoptimize_flag)
 
Node< NodeInfoT > select_node_for_branching (SetOfActiveNodes &t_active_nodes)
 
std::vector< TreeNodecreate_child_nodes (const TreeNode &t_node)
 
void backtrack (SetOfActiveNodes &t_actives_nodes, SetOfActiveNodes &t_sub_active_nodes)
 
void set_as_incumbent (const TreeNode &t_node)
 
bool gap_is_closed () const
 
void prune_nodes_by_bound (SetOfActiveNodes &t_active_nodes)
 
void update_lower_bound (const SetOfActiveNodes &t_active_nodes)
 
bool is_valid (const TreeNode &t_node) const
 
void log_node_after_solve (const Node< NodeInfoT > &t_node)
 
void log_after_termination ()
 
SideEffectRegistry call_callbacks (CallbackEvent t_event, const TreeNode &t_node, unsigned int t_relaxation_id)
 
void update_obj_sense () override
 
void update_obj () override
 
void update_rhs () override
 
void update_obj_constant () override
 
void update_mat_coeff (const Ctr &t_ctr, const Var &t_var) override
 
void update_ctr_type (const Ctr &t_ctr) override
 
void update_ctr_rhs (const Ctr &t_ctr) override
 
void update_var_type (const Var &t_var) override
 
void update_var_lb (const Var &t_var) override
 
void update_var_ub (const Var &t_var) override
 
void update_var_obj (const Var &t_var) override
 
void set_status (SolutionStatus t_status) override
 
void set_reason (SolutionReason t_reason) override
 
void set_best_bound (double t_value) override
 
void set_best_obj (double t_value) override
 

Detailed Description

template<class NodeInfoT>
class idol::Optimizers::BranchAndBound< NodeInfoT >

Definition at line 30 of file Optimizers_BranchAndBound.h.

Constructor & Destructor Documentation

◆ BranchAndBound()

template<class NodeInfoT >
idol::Optimizers::BranchAndBound< NodeInfoT >::BranchAndBound ( const Model t_model,
const OptimizerFactory t_node_optimizer,
const BranchingRuleFactory< NodeInfoT > &  t_branching_rule_factory,
const NodeSelectionRuleFactory< NodeInfoT > &  t_node_selection_rule_factory,
AbstractBranchAndBoundCallbackI< NodeInfoT > *  t_callback,
const Logs::BranchAndBound< NodeInfoT >::Factory< NodeInfoT > &  t_logger_factory 
)
explicit

Definition at line 424 of file Optimizers_BranchAndBound.h.

Member Function Documentation

◆ add() [1/3]

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::add ( const Ctr t_ctr)
overrideprotected

Definition at line 877 of file Optimizers_BranchAndBound.h.

◆ add() [2/3]

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::add ( const QCtr t_ctr)
overrideprotected

Definition at line 174 of file Optimizers_BranchAndBound.h.

◆ add() [3/3]

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::add ( const Var t_var)
overrideprotected

Definition at line 884 of file Optimizers_BranchAndBound.h.

◆ add_callback()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::add_callback ( BranchAndBoundCallback< NodeInfoT > *  t_cb)
virtual

Definition at line 414 of file Optimizers_BranchAndBound.h.

◆ analyze()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::analyze ( const TreeNode t_node,
unsigned int  t_relaxation_id,
bool *  t_explore_children_flag,
bool *  t_reoptimize_flag 
)
protected

Definition at line 669 of file Optimizers_BranchAndBound.h.

◆ backtrack()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::backtrack ( BranchAndBound< NodeInfoT >::SetOfActiveNodes &  t_actives_nodes,
SetOfActiveNodes t_sub_active_nodes 
)
protected

Definition at line 848 of file Optimizers_BranchAndBound.h.

◆ branching_rule() [1/2]

template<class NodeInfoT >
BranchingRule< NodeInfoT > & idol::Optimizers::BranchAndBound< NodeInfoT >::branching_rule ( )
inline

Definition at line 139 of file Optimizers_BranchAndBound.h.

◆ branching_rule() [2/2]

template<class NodeInfoT >
const BranchingRule< NodeInfoT > & idol::Optimizers::BranchAndBound< NodeInfoT >::branching_rule ( ) const
inline

Definition at line 141 of file Optimizers_BranchAndBound.h.

◆ build()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::build ( )
overrideprotected

Definition at line 419 of file Optimizers_BranchAndBound.h.

◆ call_callbacks()

template<class NodeInfoT >
idol::SideEffectRegistry idol::Optimizers::BranchAndBound< NodeInfoT >::call_callbacks ( CallbackEvent  t_event,
const TreeNode t_node,
unsigned int  t_relaxation_id 
)
protected

Definition at line 404 of file Optimizers_BranchAndBound.h.

◆ create_child_nodes()

template<class NodeInfoT >
std::vector< idol::Node< NodeInfoT > > idol::Optimizers::BranchAndBound< NodeInfoT >::create_child_nodes ( const TreeNode t_node)
protected

Definition at line 825 of file Optimizers_BranchAndBound.h.

◆ create_relaxations()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::create_relaxations ( )
protected

Definition at line 442 of file Optimizers_BranchAndBound.h.

◆ create_root_node()

template<class NodeInfoT >
idol::Node< NodeInfoT > idol::Optimizers::BranchAndBound< NodeInfoT >::create_root_node ( )
protected

Definition at line 462 of file Optimizers_BranchAndBound.h.

◆ detect_integer_objective()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::detect_integer_objective ( )
protected

Definition at line 195 of file Optimizers_BranchAndBound.h.

◆ explore()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::explore ( TreeNode t_node,
unsigned int  t_relaxation_id,
SetOfActiveNodes t_active_nodes,
unsigned int  t_step 
)
protected

Definition at line 552 of file Optimizers_BranchAndBound.h.

◆ gap_is_closed()

template<class NodeInfoT >
bool idol::Optimizers::BranchAndBound< NodeInfoT >::gap_is_closed ( ) const
protected

Definition at line 842 of file Optimizers_BranchAndBound.h.

◆ get_ctr_dual()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::get_ctr_dual ( const Ctr t_ctr) const
override

Definition at line 343 of file Optimizers_BranchAndBound.h.

◆ get_ctr_farkas()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::get_ctr_farkas ( const Ctr t_ctr) const
override

Definition at line 335 of file Optimizers_BranchAndBound.h.

◆ get_n_solutions()

template<class NodeInfoT >
unsigned int idol::Optimizers::BranchAndBound< NodeInfoT >::get_n_solutions ( ) const
override

Definition at line 255 of file Optimizers_BranchAndBound.h.

◆ get_solution_index()

template<class NodeInfoT >
unsigned int idol::Optimizers::BranchAndBound< NodeInfoT >::get_solution_index ( ) const
override

Definition at line 250 of file Optimizers_BranchAndBound.h.

◆ get_var_primal()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::get_var_primal ( const Var t_var) const
override

Definition at line 359 of file Optimizers_BranchAndBound.h.

◆ get_var_ray()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::get_var_ray ( const Var t_var) const
override

Definition at line 351 of file Optimizers_BranchAndBound.h.

◆ get_var_reduced_cost()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::get_var_reduced_cost ( const Var t_var) const
override

Definition at line 215 of file Optimizers_BranchAndBound.h.

◆ has_incumbent()

template<class NodeInfoT >
bool idol::Optimizers::BranchAndBound< NodeInfoT >::has_incumbent ( ) const
inline

Definition at line 143 of file Optimizers_BranchAndBound.h.

◆ hook_after_optimize()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::hook_after_optimize ( )
overrideprotected

Definition at line 543 of file Optimizers_BranchAndBound.h.

◆ hook_before_optimize()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::hook_before_optimize ( )
overrideprotected

Definition at line 473 of file Optimizers_BranchAndBound.h.

◆ hook_optimize()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::hook_optimize ( )
overrideprotected

Definition at line 500 of file Optimizers_BranchAndBound.h.

◆ incumbent()

template<class NodeInfoT >
const TreeNode & idol::Optimizers::BranchAndBound< NodeInfoT >::incumbent ( ) const
inline

Definition at line 145 of file Optimizers_BranchAndBound.h.

◆ is_valid()

template<class NodeInfoT >
bool idol::Optimizers::BranchAndBound< NodeInfoT >::is_valid ( const TreeNode t_node) const
protected

Definition at line 181 of file Optimizers_BranchAndBound.h.

◆ log_after_termination()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::log_after_termination ( )
protected

Definition at line 223 of file Optimizers_BranchAndBound.h.

◆ log_node_after_solve()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::log_node_after_solve ( const Node< NodeInfoT > &  t_node)
protected

Definition at line 238 of file Optimizers_BranchAndBound.h.

◆ n_active_nodes()

template<class NodeInfoT >
unsigned int idol::Optimizers::BranchAndBound< NodeInfoT >::n_active_nodes ( ) const
inline

Definition at line 129 of file Optimizers_BranchAndBound.h.

◆ n_created_nodes()

template<class NodeInfoT >
unsigned int idol::Optimizers::BranchAndBound< NodeInfoT >::n_created_nodes ( ) const
inline

Definition at line 125 of file Optimizers_BranchAndBound.h.

◆ n_solved_nodes()

template<class NodeInfoT >
unsigned int idol::Optimizers::BranchAndBound< NodeInfoT >::n_solved_nodes ( ) const
inline

Definition at line 127 of file Optimizers_BranchAndBound.h.

◆ name()

template<class NodeInfoT >
std::string idol::Optimizers::BranchAndBound< NodeInfoT >::name ( ) const
inlineoverride

Definition at line 111 of file Optimizers_BranchAndBound.h.

◆ prune_nodes_by_bound()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::prune_nodes_by_bound ( BranchAndBound< NodeInfoT >::SetOfActiveNodes &  t_active_nodes)
protected

Definition at line 786 of file Optimizers_BranchAndBound.h.

◆ relaxation() [1/2]

template<class NodeInfoT >
Model & idol::Optimizers::BranchAndBound< NodeInfoT >::relaxation ( )
inline

Definition at line 133 of file Optimizers_BranchAndBound.h.

◆ relaxation() [2/2]

template<class NodeInfoT >
const Model & idol::Optimizers::BranchAndBound< NodeInfoT >::relaxation ( ) const
inline

Definition at line 131 of file Optimizers_BranchAndBound.h.

◆ remove() [1/3]

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::remove ( const Ctr t_ctr)
overrideprotected

Definition at line 863 of file Optimizers_BranchAndBound.h.

◆ remove() [2/3]

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::remove ( const QCtr t_ctr)
overrideprotected

Definition at line 167 of file Optimizers_BranchAndBound.h.

◆ remove() [3/3]

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::remove ( const Var t_var)
overrideprotected

Definition at line 870 of file Optimizers_BranchAndBound.h.

◆ root_node_best_bound()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::root_node_best_bound ( ) const
inline

Definition at line 135 of file Optimizers_BranchAndBound.h.

◆ root_node_best_obj()

template<class NodeInfoT >
double idol::Optimizers::BranchAndBound< NodeInfoT >::root_node_best_obj ( ) const
inline

Definition at line 137 of file Optimizers_BranchAndBound.h.

◆ select_node_for_branching()

template<class NodeInfoT >
idol::Node< NodeInfoT > idol::Optimizers::BranchAndBound< NodeInfoT >::select_node_for_branching ( BranchAndBound< NodeInfoT >::SetOfActiveNodes &  t_active_nodes)
protected

Definition at line 812 of file Optimizers_BranchAndBound.h.

◆ set_as_incumbent()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::set_as_incumbent ( const TreeNode t_node)
protected

Definition at line 764 of file Optimizers_BranchAndBound.h.

◆ set_best_bound()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::set_best_bound ( double  t_value)
overrideprotectedvirtual

Reimplemented from idol::Algorithm.

Definition at line 897 of file Optimizers_BranchAndBound.h.

◆ set_best_obj()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::set_best_obj ( double  t_value)
overrideprotectedvirtual

Reimplemented from idol::Algorithm.

Definition at line 891 of file Optimizers_BranchAndBound.h.

◆ set_reason()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::set_reason ( idol::SolutionReason  t_reason)
overrideprotectedvirtual

Reimplemented from idol::Algorithm.

Definition at line 903 of file Optimizers_BranchAndBound.h.

◆ set_solution_index()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::set_solution_index ( unsigned int  t_index)
override

Definition at line 243 of file Optimizers_BranchAndBound.h.

◆ set_status()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::set_status ( idol::SolutionStatus  t_status)
overrideprotectedvirtual

Reimplemented from idol::Algorithm.

Definition at line 909 of file Optimizers_BranchAndBound.h.

◆ set_subtree_depth()

template<class NodeInfoT >
virtual void idol::Optimizers::BranchAndBound< NodeInfoT >::set_subtree_depth ( unsigned int  t_depth)
inlinevirtual

Definition at line 115 of file Optimizers_BranchAndBound.h.

◆ solve()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::solve ( TreeNode t_node,
unsigned int  t_relaxation_id 
) const

Definition at line 639 of file Optimizers_BranchAndBound.h.

◆ submit_heuristic_solution()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::submit_heuristic_solution ( NodeInfoT *  t_info)

Definition at line 383 of file Optimizers_BranchAndBound.h.

◆ submit_lower_bound()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::submit_lower_bound ( double  t_lower_bound)

Definition at line 369 of file Optimizers_BranchAndBound.h.

◆ subtree_depth()

template<class NodeInfoT >
unsigned int idol::Optimizers::BranchAndBound< NodeInfoT >::subtree_depth ( ) const
inline

Definition at line 117 of file Optimizers_BranchAndBound.h.

◆ terminate()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::terminate ( )
override

Definition at line 189 of file Optimizers_BranchAndBound.h.

◆ update()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update ( )
overrideprotected

Definition at line 856 of file Optimizers_BranchAndBound.h.

◆ update_ctr_rhs()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_ctr_rhs ( const Ctr t_ctr)
overrideprotected

Definition at line 295 of file Optimizers_BranchAndBound.h.

◆ update_ctr_type()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_ctr_type ( const Ctr t_ctr)
overrideprotected

Definition at line 288 of file Optimizers_BranchAndBound.h.

◆ update_lower_bound()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_lower_bound ( const SetOfActiveNodes t_active_nodes)
protected

Definition at line 772 of file Optimizers_BranchAndBound.h.

◆ update_mat_coeff()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_mat_coeff ( const Ctr t_ctr,
const Var t_var 
)
overrideprotected

Definition at line 281 of file Optimizers_BranchAndBound.h.

◆ update_obj()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_obj ( )
overrideprotected

Definition at line 260 of file Optimizers_BranchAndBound.h.

◆ update_obj_constant()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_obj_constant ( )
overrideprotected

Definition at line 274 of file Optimizers_BranchAndBound.h.

◆ update_obj_sense()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_obj_sense ( )
overrideprotected

Definition at line 330 of file Optimizers_BranchAndBound.h.

◆ update_rhs()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_rhs ( )
overrideprotected

Definition at line 267 of file Optimizers_BranchAndBound.h.

◆ update_var_lb()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_var_lb ( const Var t_var)
overrideprotected

Definition at line 309 of file Optimizers_BranchAndBound.h.

◆ update_var_obj()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_var_obj ( const Var t_var)
overrideprotected

Definition at line 323 of file Optimizers_BranchAndBound.h.

◆ update_var_type()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_var_type ( const Var t_var)
overrideprotected

Definition at line 302 of file Optimizers_BranchAndBound.h.

◆ update_var_ub()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::update_var_ub ( const Var t_var)
overrideprotected

Definition at line 316 of file Optimizers_BranchAndBound.h.

◆ write()

template<class NodeInfoT >
void idol::Optimizers::BranchAndBound< NodeInfoT >::write ( const std::string &  t_name)
overrideprotected

Definition at line 820 of file Optimizers_BranchAndBound.h.