Description

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

Definition at line 85 of file KnapsackCover.h.

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

Protected Methods
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 Model &	relaxation () const
const Model &	original_model () const
void	submit_heuristic_solution (NodeInfoT *t_info)
void	submit_bound (double t_bound)
const SideEffectRegistry &	side_effect_registry () const
const Timer &	time () const
double	best_bound () const
double	best_obj () const
void	terminate ()

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.

Methods 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_cut the 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_cut the cut to be added

Definition at line 292 of file BranchAndBoundCallback.h.

◆ best_bound()

template<class NodeInfoT>

double idol::BranchAndBoundCallback< NodeInfoT >::best_bound ( ) const

nodiscardprotectedinherited

Definition at line 232 of file BranchAndBoundCallback.h.

◆ best_obj()

template<class NodeInfoT>

double idol::BranchAndBoundCallback< NodeInfoT >::best_obj ( ) const

nodiscardprotectedinherited

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

nodiscardprotectedinherited

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_event The 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

nodiscardprotectedinherited

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

nodiscardprotectedinherited

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

nodiscardprotectedinherited

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_bound a 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_info a 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

nodiscardprotectedinherited

Definition at line 250 of file BranchAndBoundCallback.h.

Description

Public Methods

Protected Methods

Constructor & Destructor Documentation

◆ Strategy()

Methods Documentation

◆ add_knapsack_structure()

◆ add_lazy_cut()

◆ add_local_variable_branching()

◆ add_user_cut()

◆ best_bound()

◆ best_obj()

◆ compute_cut_activity()

◆ compute_initial_cover()

◆ compute_minimal_cover()

◆ create_cut()

◆ debug()

◆ detect_knapsack_structure()

◆ fix_variables_equal_to_one_or_zero()

◆ has_only_binary_variables()

◆ has_only_single_signed_coefficients()

◆ initialize()

◆ log_after_termination()

◆ node()

◆ operator()()

◆ original_model()

◆ partition_minimal_cover()

◆ partition_remaining_items()

◆ relaxation()

◆ separate_cut()

◆ sequential_up_and_down_lifting()

◆ set_current_values()

◆ side_effect_registry()

◆ solve_knapsack_approximately()

◆ sort_by_non_decreasing_weights()

◆ sort_by_non_increasing_weights()

◆ submit_bound()

◆ submit_heuristic_solution()

◆ sum_of_weights()

◆ swap_items()

◆ terminate()

◆ time()