idol
A C++ Framework for Optimization
Loading...
Searching...
No Matches
idol::Cuts::KnapsackCover< NodeInfoT >::Strategy Class Reference
Inheritance diagram for idol::Cuts::KnapsackCover< NodeInfoT >::Strategy:
Inheritance graph
Collaboration diagram for idol::Cuts::KnapsackCover< NodeInfoT >::Strategy:
Collaboration graph

Public Member Functions

 Strategy (bool t_use_lifting, bool t_apply_to_tree_nodes, unsigned int t_max_pass_root_node, double t_max_cuts_factor)
 

Protected Member Functions

void detect_knapsack_structure (const Ctr &t_ctr)
 
void add_knapsack_structure (const Row &t_row, CtrType t_type)
 
bool has_only_binary_variables (const Row &t_row)
 
bool has_only_single_signed_coefficients (const Row &t_row)
 
void separate_cut (const KnapsackStructure &t_knapsack_structure)
 
std::tuple< SetOfItems, SetOfItems, SetOfItems > fix_variables_equal_to_one_or_zero (const SetOfItems &t_set_of_items)
 
void set_current_values (const SetOfItems &t_set_of_items)
 
int sum_of_weights (const SetOfItems &t_set_of_items)
 
std::pair< SetOfItems, SetOfItems > compute_initial_cover (const SetOfItems &t_N_1, const SetOfItems &t_N_free, const SetOfItems &t_N_0, int t_capacity)
 
std::pair< SetOfItems, SetOfItems > solve_knapsack_approximately (const SetOfItems &t_set_of_items, int t_capacity)
 
std::pair< SetOfItems, SetOfItems > swap_items (const SetOfItems &t_a, const SetOfItems &t_b)
 
std::pair< SetOfItems, SetOfItems > compute_minimal_cover (const SetOfItems &t_initial_cover, int t_capacity)
 
std::pair< SetOfItems, SetOfItems > partition_minimal_cover (const SetOfItems &t_minimal_cover)
 
std::pair< SetOfItems, SetOfItems > partition_remaining_items (const SetOfItems &t_remaining_items)
 
void sort_by_non_decreasing_weights (const SetOfItems &t_set_of_items)
 
void sort_by_non_increasing_weights (const SetOfItems &t_set_of_items)
 
int sequential_up_and_down_lifting (const SetOfItems &t_C1, const SetOfItems &t_C2, const SetOfItems &t_F, const SetOfItems &t_R, int t_capacity)
 
double compute_cut_activity (const SetOfItems &t_set_of_items, int t_right_hand_side)
 
TempCtr create_cut (const SetOfItems &t_set_of_items, int t_right_hand_side)
 
void debug (const std::string &t_name, const SetOfItems &t_set_of_items, bool t_with_values=false, bool t_with_cut=false)
 
void initialize () override
 
void operator() (CallbackEvent t_event) override
 
void log_after_termination () override
 
void add_user_cut (const TempCtr &t_cut)
 
void add_lazy_cut (const TempCtr &t_cut)
 
void add_local_variable_branching (const Var &t_var, CtrType t_type, double t_rhs)
 
const Node< NodeInfoT > & node () const
 
const Modelrelaxation () const
 
const Modeloriginal_model () const
 
void submit_heuristic_solution (NodeInfoT *t_info)
 
void submit_bound (double t_bound)
 
const SideEffectRegistryside_effect_registry () const
 
const Timertime () const
 
double best_bound () const
 
double best_obj () const
 
void terminate ()
 

Detailed Description

template<class NodeInfoT = idol::DefaultNodeInfo>
class idol::Cuts::KnapsackCover< NodeInfoT >::Strategy

Definition at line 85 of file KnapsackCover.h.

Constructor & Destructor Documentation

◆ Strategy()

template<class NodeInfoT >
idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::Strategy ( bool  t_use_lifting,
bool  t_apply_to_tree_nodes,
unsigned int  t_max_pass_root_node,
double  t_max_cuts_factor 
)

Definition at line 179 of file KnapsackCover.h.

Member Function Documentation

◆ add_knapsack_structure()

template<class NodeInfoT = idol::DefaultNodeInfo>
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::add_knapsack_structure ( const Row &  t_row,
CtrType  t_type 
)
protected

Definition at line 292 of file KnapsackCover.h.

◆ add_lazy_cut()

template<class NodeInfoT >
void idol::BranchAndBoundCallback< NodeInfoT >::add_lazy_cut ( const TempCtr t_cut)
protectedinherited

Adds a lazy cut to the relaxation

Parameters
t_cutthe cut to be added

Definition at line 286 of file BranchAndBoundCallback.h.

◆ add_local_variable_branching()

template<class NodeInfoT >
void idol::BranchAndBoundCallback< NodeInfoT >::add_local_variable_branching ( const Var t_var,
CtrType  t_type,
double  t_rhs 
)
protectedinherited

Definition at line 220 of file BranchAndBoundCallback.h.

◆ add_user_cut()

template<class NodeInfoT >
void idol::BranchAndBoundCallback< NodeInfoT >::add_user_cut ( const TempCtr t_cut)
protectedinherited

Adds a user cut to the relaxation

Parameters
t_cutthe cut to be added

Definition at line 292 of file BranchAndBoundCallback.h.

◆ best_bound()

template<class NodeInfoT >
double idol::BranchAndBoundCallback< NodeInfoT >::best_bound ( ) const
protectedinherited

Definition at line 232 of file BranchAndBoundCallback.h.

◆ best_obj()

template<class NodeInfoT >
double idol::BranchAndBoundCallback< NodeInfoT >::best_obj ( ) const
protectedinherited

Definition at line 226 of file BranchAndBoundCallback.h.

◆ compute_cut_activity()

template<class NodeInfoT >
double idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::compute_cut_activity ( const SetOfItems &  t_set_of_items,
int  t_right_hand_side 
)
protected

Definition at line 468 of file KnapsackCover.h.

◆ compute_initial_cover()

template<class NodeInfoT >
std::pair< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::compute_initial_cover ( const SetOfItems &  t_N_1,
const SetOfItems &  t_N_free,
const SetOfItems &  t_N_0,
int  t_capacity 
)
protected

Definition at line 753 of file KnapsackCover.h.

◆ compute_minimal_cover()

template<class NodeInfoT >
std::pair< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::compute_minimal_cover ( const SetOfItems &  t_initial_cover,
int  t_capacity 
)
protected

Definition at line 898 of file KnapsackCover.h.

◆ create_cut()

template<class NodeInfoT >
idol::TempCtr idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::create_cut ( const SetOfItems &  t_set_of_items,
int  t_right_hand_side 
)
protected

Definition at line 450 of file KnapsackCover.h.

◆ debug()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::debug ( const std::string &  t_name,
const SetOfItems &  t_set_of_items,
bool  t_with_values = false,
bool  t_with_cut = false 
)
protected

Definition at line 191 of file KnapsackCover.h.

◆ detect_knapsack_structure()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::detect_knapsack_structure ( const Ctr t_ctr)
protected

Definition at line 264 of file KnapsackCover.h.

◆ fix_variables_equal_to_one_or_zero()

template<class NodeInfoT >
std::tuple< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::fix_variables_equal_to_one_or_zero ( const SetOfItems &  t_set_of_items)
protected

Definition at line 705 of file KnapsackCover.h.

◆ has_only_binary_variables()

template<class NodeInfoT = idol::DefaultNodeInfo>
bool idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::has_only_binary_variables ( const Row &  t_row)
protected

Definition at line 312 of file KnapsackCover.h.

◆ has_only_single_signed_coefficients()

template<class NodeInfoT = idol::DefaultNodeInfo>
bool idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::has_only_single_signed_coefficients ( const Row &  t_row)
protected

Definition at line 328 of file KnapsackCover.h.

◆ initialize()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::initialize ( )
overrideprotectedvirtual

This method is called at the very beginning of the Branch-and-Bound algorithm

Reimplemented from idol::BranchAndBoundCallback< NodeInfoT >.

Definition at line 245 of file KnapsackCover.h.

◆ log_after_termination()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::log_after_termination ( )
overrideprotectedvirtual

Reimplemented from idol::BranchAndBoundCallback< NodeInfoT >.

Definition at line 171 of file KnapsackCover.h.

◆ node()

template<class NodeInfoT >
const idol::Node< NodeInfoT > & idol::BranchAndBoundCallback< NodeInfoT >::node ( ) const
protectedinherited

Returns the node which is currently explored

Returns
the node which is currently explored

Definition at line 280 of file BranchAndBoundCallback.h.

◆ operator()()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::operator() ( CallbackEvent  t_event)
overrideprotectedvirtual

This method is left for the user to write and consists in the main execution block of the callback.

Parameters
t_eventThe event triggering the callback

Implements idol::BranchAndBoundCallback< NodeInfoT >.

Definition at line 351 of file KnapsackCover.h.

◆ original_model()

template<class NodeInfoT >
const idol::Model & idol::BranchAndBoundCallback< NodeInfoT >::original_model ( ) const
protectedinherited

Returns the original model from which the branch-and-bound algorithm started (i.e., the original non-relaxed model)

Returns
the original model

Definition at line 268 of file BranchAndBoundCallback.h.

◆ partition_minimal_cover()

template<class NodeInfoT >
std::pair< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::partition_minimal_cover ( const SetOfItems &  t_minimal_cover)
protected

Definition at line 776 of file KnapsackCover.h.

◆ partition_remaining_items()

template<class NodeInfoT >
std::pair< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::partition_remaining_items ( const SetOfItems &  t_remaining_items)
protected

Definition at line 803 of file KnapsackCover.h.

◆ relaxation()

template<class NodeInfoT >
const idol::Model & idol::BranchAndBoundCallback< NodeInfoT >::relaxation ( ) const
protectedinherited

Returns the current node's model being solved

Returns
the current node's model being solved

Definition at line 274 of file BranchAndBoundCallback.h.

◆ separate_cut()

template<class NodeInfoT = idol::DefaultNodeInfo>
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::separate_cut ( const KnapsackStructure &  t_knapsack_structure)
protected

Definition at line 381 of file KnapsackCover.h.

◆ sequential_up_and_down_lifting()

template<class NodeInfoT >
int idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::sequential_up_and_down_lifting ( const SetOfItems &  t_C1,
const SetOfItems &  t_C2,
const SetOfItems &  t_F,
const SetOfItems &  t_R,
int  t_capacity 
)
protected

Definition at line 486 of file KnapsackCover.h.

◆ set_current_values()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::set_current_values ( const SetOfItems &  t_set_of_items)
protected

Definition at line 689 of file KnapsackCover.h.

◆ side_effect_registry()

template<class NodeInfoT >
const idol::SideEffectRegistry & idol::BranchAndBoundCallback< NodeInfoT >::side_effect_registry ( ) const
protectedinherited

Returns the side effect registry

Returns
the side effect registry

Definition at line 244 of file BranchAndBoundCallback.h.

◆ solve_knapsack_approximately()

template<class NodeInfoT >
std::pair< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::solve_knapsack_approximately ( const SetOfItems &  t_set_of_items,
int  t_capacity 
)
protected

Definition at line 830 of file KnapsackCover.h.

◆ sort_by_non_decreasing_weights()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::sort_by_non_decreasing_weights ( const SetOfItems &  t_set_of_items)
protected

Definition at line 680 of file KnapsackCover.h.

◆ sort_by_non_increasing_weights()

template<class NodeInfoT >
void idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::sort_by_non_increasing_weights ( const SetOfItems &  t_set_of_items)
protected

Definition at line 671 of file KnapsackCover.h.

◆ submit_bound()

template<class NodeInfoT >
void idol::BranchAndBoundCallback< NodeInfoT >::submit_bound ( double  t_bound)
protectedinherited

Submits a new proven bound.

The given bound is set as best bound if and only if it improves the current best bound.

Parameters
t_bounda proven bound

Definition at line 256 of file BranchAndBoundCallback.h.

◆ submit_heuristic_solution()

template<class NodeInfoT >
void idol::BranchAndBoundCallback< NodeInfoT >::submit_heuristic_solution ( NodeInfoT *  t_info)
protectedinherited

Submits a new solution to the branch-and-bound tree algorithm.

The solution is checked for validity according to the branch-and-bound tree branching rule and is set as incumbent if and only if it is valid and improves the current best objective.

Parameters
t_infoa node information storing the solution

Definition at line 262 of file BranchAndBoundCallback.h.

◆ sum_of_weights()

template<class NodeInfoT >
int idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::sum_of_weights ( const SetOfItems &  t_set_of_items)
protected

Definition at line 737 of file KnapsackCover.h.

◆ swap_items()

template<class NodeInfoT >
std::pair< typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems, typename idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::SetOfItems > idol::Cuts::KnapsackCover< NodeInfoT >::Strategy::swap_items ( const SetOfItems &  t_a,
const SetOfItems &  t_b 
)
protected

Definition at line 877 of file KnapsackCover.h.

◆ terminate()

template<class NodeInfoT >
void idol::BranchAndBoundCallback< NodeInfoT >::terminate ( )
protectedinherited

Definition at line 238 of file BranchAndBoundCallback.h.

◆ time()

template<class NodeInfoT >
const idol::Timer & idol::BranchAndBoundCallback< NodeInfoT >::time ( ) const
protectedinherited

Definition at line 250 of file BranchAndBoundCallback.h.