Class for operations at the node level. More...

#include <BB_lp.hpp>

Inheritance diagram for BB_lp:

Collaboration diagram for BB_lp:

Public Member Functions
virtual void	unpack_module_data (BCP_buffer &buf)
	Unpack data sent from the tree manager. More...

virtual OsiSolverInterface *	initialize_solver_interface ()
	Called only once at the beginning, from the root node. More...

virtual void	initialize_new_search_tree_node (const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const BCP_vec< BCP_obj_status > &var_status, const BCP_vec< BCP_obj_status > &cut_status, BCP_vec< int > &var_changed_pos, BCP_vec< double > &var_new_bd, BCP_vec< int > &cut_changed_pos, BCP_vec< double > &cut_new_bd)
	Initialize data members at the start of processing a new subproblem. More...

virtual void	modify_lp_parameters (OsiSolverInterface *lp, const int changeType, bool in_strong_branching)
	Modify the parameters of the LP solver. More...

virtual BCP_solution *	test_feasibility (const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
	Test feasibility of the LP solution. More...

virtual void	logical_fixing (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const BCP_vec< BCP_obj_status > &var_status, const BCP_vec< BCP_obj_status > &cut_status, const int var_bound_changes_since_logical_fixing, BCP_vec< int > &changed_pos, BCP_vec< double > &new_bd)
	Perform fixing of variables. More...

virtual void	generate_cuts_in_lp (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_cut * > &new_cuts, BCP_vec< BCP_row * > &new_rows)
	Cut generation. More...

virtual BCP_solution *	generate_heuristic_solution (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
	Simple rounding heuristic. More...

virtual void	cuts_to_rows (const BCP_vec< BCP_var * > &vars, BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_row * > &rows, const BCP_lp_result &lpres, BCP_object_origin origin, bool allow_multiple)
	Describes how to get a row of the matrix from the representation of the cut. More...

virtual BCP_branching_decision	select_branching_candidates (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const BCP_lp_var_pool &local_var_pool, const BCP_lp_cut_pool &local_cut_pool, BCP_vec< BCP_lp_branching_object * > &cands, bool force_branch=false)
	Called at the end of each iteration. More...

virtual void	set_user_data_for_children (BCP_presolved_lp_brobj *best, const int selected)
	Set up the user data for the children according to the chosen branching object. More...

Constructors and destructors
	BB_lp ()
	Default constructor. More...

virtual	~BB_lp ()
	Destructor. More...

Public Member Functions inherited from BCP_lp_user
void	setOsiBabSolver (OsiBabSolver *ptr)

OsiBabSolver *	getOsiBabSolver ()

void	print (const bool ifprint, const char *format,...) const
	A method to print a message with the process id. More...

int	process_id () const
	What is the process id of the current process. More...

int	parent () const
	the process id of the parent More...

void	send_message (const int target, const BCP_buffer &buf, BCP_message_tag tag=BCP_Msg_User)
	Send a message to a particular process. More...

void	receive_message (const int sender, BCP_buffer &buf, BCP_message_tag tag=BCP_Msg_User)
	Wait for a message and receive it. More...

void	broadcast_message (const BCP_process_t proc_type, const BCP_buffer &buf)
	Broadcast the message to all processes of the given type. More...

virtual void	process_message (BCP_buffer &buf)
	Process a message that has been sent by another process' user part to this process' user part. More...

virtual void	initialize_int_and_sos_list (std::vector< OsiObject * > &intAndSosObjects)
	Create the list of objects that can be used for branching (simple integer vars and SOS sets). More...

virtual void	load_problem (OsiSolverInterface &osi, BCP_problem_core *core, BCP_var_set &vars, BCP_cut_set &cuts)
	Load the problem specified by core, vars, and cuts into the solver interface. More...

virtual void	process_lp_result (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const double old_lower_bound, double &true_lower_bound, BCP_solution &sol, BCP_vec< BCP_cut > &new_cuts, BCP_vec< BCP_row * > &new_rows, BCP_vec< BCP_var * > &new_vars, BCP_vec< BCP_col * > &new_cols)
	Process the result of an iteration. More...

virtual double	compute_lower_bound (const double old_lower_bound, const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
	Compute a true lower bound for the subproblem. More...

virtual void	restore_feasibility (const BCP_lp_result &lpres, const std::vector< double * > dual_rays, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_var * > &vars_to_add, BCP_vec< BCP_col * > &cols_to_add)
	Restoring feasibility. More...

virtual void	select_vars_to_delete (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool before_fathom, BCP_vec< int > &deletable)

virtual void	select_cuts_to_delete (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool before_fathom, BCP_vec< int > &deletable)

void	reduced_cost_fixing (const double dj, const double x, const double gap, BCP_vec< BCP_var * > &vars, int &newly_changed)
	Reduced cost fixing. More...

virtual BCP_branching_object_relation	compare_branching_candidates (BCP_presolved_lp_brobj new_solved, BCP_presolved_lp_brobj old_solved)
	Decide which branching object is preferred for branching. More...

virtual void	set_actions_for_children (BCP_presolved_lp_brobj *best)
	Decide what to do with the children of the selected branching object. More...

virtual void	set_user_data_for_children (BCP_presolved_lp_brobj *best)
	Deprecated version of the previos method (it does not pass the index of the selected branching candidate). More...

void	setLpProblemPointer (BCP_lp_prob *ptr)
	Set the pointer. More...

BCP_lp_prob *	getLpProblemPointer ()
	Get the pointer. More...

double	upper_bound () const
	Return what is the best known upper bound (might be BCP_DBL_MAX) More...

bool	over_ub (double lb) const
	Return true / false depending on whether the lb argument is over the current upper bound or not. More...

int	current_phase () const
	Return the phase the algorithm is in. More...

int	current_level () const
	Return the level of the search tree node being processed. More...

int	current_index () const
	Return the internal index of the search tree node being processed. More...

int	current_iteration () const
	Return the iteration count within the search tree node being processed. More...

double	start_time () const
	Return when the LP process started. More...

BCP_user_data *	get_user_data ()
	Return a pointer to the BCP_user_data structure the user (may have) stored in this node. More...

char	get_param (const BCP_lp_par::chr_params key) const

int	get_param (const BCP_lp_par::int_params key) const

double	get_param (const BCP_lp_par::dbl_params key) const

const BCP_string &	get_param (const BCP_lp_par::str_params key) const

void	set_param (const BCP_lp_par::chr_params key, const bool val)

void	set_param (const BCP_lp_par::chr_params key, const char val)

void	set_param (const BCP_lp_par::int_params key, const int val)

void	set_param (const BCP_lp_par::dbl_params key, const double val)

void	set_param (const BCP_lp_par::str_params key, const char *val)

void	send_feasible_solution (const BCP_solution *sol)

	BCP_lp_user ()
	Being virtual, the destructor invokes the destructor for the real type of the object being deleted. More...

virtual	~BCP_lp_user ()
	Being virtual, the destructor invokes the destructor for the real type of the object being deleted. More...

void	select_nonzeros (const double first, const double last, const double etol, BCP_vec< int > &nonzeros) const
	Select all nonzero entries. More...

void	select_zeros (const double first, const double last, const double etol, BCP_vec< int > &zeros) const
	Select all zero entries. More...

void	select_positives (const double first, const double last, const double etol, BCP_vec< int > &positives) const
	Select all positive entries. More...

void	select_fractions (const double first, const double last, const double etol, BCP_vec< int > &fractions) const
	Select all fractional entries. More...

BCP_solution_generic *	test_binary (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
	Test whether all variables are 0/1. More...

BCP_solution_generic *	test_integral (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
	Test whether all variables are integer. More...

BCP_solution_generic *	test_full (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
	Test whether the variables specified as integers are really integer. More...

virtual void	pack_feasible_solution (BCP_buffer &buf, const BCP_solution *sol)
	Pack a MIP feasible solution into a buffer. More...

virtual void	pack_primal_solution (BCP_buffer &buf, const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
	Pack the information necessary for cut generation into the buffer. More...

virtual void	pack_dual_solution (BCP_buffer &buf, const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
	Pack the information necessary for variable generation into the buffer. More...

virtual void	display_lp_solution (const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool final_lp_solution)
	Display the result of most recent LP optimization. More...

virtual void	vars_to_cols (const BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_var * > &vars, BCP_vec< BCP_col * > &cols, const BCP_lp_result &lpres, BCP_object_origin origin, bool allow_multiple)
	Convert a set of variables into corresponding columns for the current LP relaxation. More...

virtual void	generate_vars_in_lp (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool before_fathom, BCP_vec< BCP_var * > &new_vars, BCP_vec< BCP_col * > &new_cols)
	Generate variables within the LP process. More...

virtual BCP_object_compare_result	compare_cuts (const BCP_cut c0, const BCP_cut c1)
	Compare two generated cuts. More...

virtual BCP_object_compare_result	compare_vars (const BCP_var v0, const BCP_var v1)
	Compare two generated variables. More...

virtual int	try_to_branch (OsiBranchingInformation &branchInfo, OsiSolverInterface solver, OsiChooseVariable choose, OsiBranchingObject *&branchObject, bool allowVarFix)
	Select the "close-to-half" variables for strong branching. More...

void	branch_close_to_half (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const int to_be_selected, const double etol, BCP_vec< BCP_lp_branching_object * > &candidates)
	Select the "close-to-half" variables for strong branching. More...

void	branch_close_to_one (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const int to_be_selected, const double etol, BCP_vec< BCP_lp_branching_object * > &candidates)
	Select the "close-to-one" variables for strong branching. More...

void	append_branching_vars (const double x, const BCP_vec< BCP_var > &vars, const BCP_vec< int > &select_pos, BCP_vec< BCP_lp_branching_object * > &candidates)
	This helper method creates branching variable candidates and appends them to `cans`. More...

virtual void	purge_slack_pool (const BCP_vec< BCP_cut * > &slack_pool, BCP_vec< int > &to_be_purged)
	Selectively purge the list of slack cuts. More...

Public Member Functions inherited from BCP_user_class
virtual	~BCP_user_class ()

Private Attributes
BB_prob *	p_desc
	Pointer on the description of the problem. More...

MY_user_data *	p_ud
	Pointer on the description of the user data. More...

int	in_strong
	in_strong = 1 if and only if in strong branching phase More...

double	EPS
	Hold the value of EPSILON of class BB_prob. More...

BCP_vec< BCP_cut * >	algo_cuts
	Hold pointers on generated algorithmic cuts. More...

std::vector< int >	violated_cuts
	Hold indices of violated indexed cuts. More...

Detailed Description

Class for operations at the node level.

Definition at line 23 of file BB_lp.hpp.

Constructor & Destructor Documentation

BB_lp::BB_lp ( )

inline

Default constructor.

Definition at line 48 of file BB_lp.hpp.

virtual BB_lp::~BB_lp ( )

inlinevirtual

Destructor.

Definition at line 51 of file BB_lp.hpp.

Member Function Documentation

virtual void BB_lp::unpack_module_data ( BCP_buffer & buf )

virtual

Unpack data sent from the tree manager.

Reimplemented from BCP_lp_user.

virtual OsiSolverInterface* BB_lp::initialize_solver_interface ( )

virtual

Called only once at the beginning, from the root node.

Reimplemented from BCP_lp_user.

virtual void BB_lp::initialize_new_search_tree_node	(	const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts,
		const BCP_vec< BCP_obj_status > &	var_status,
		const BCP_vec< BCP_obj_status > &	cut_status,
		BCP_vec< int > &	var_changed_pos,
		BCP_vec< double > &	var_new_bd,
		BCP_vec< int > &	cut_changed_pos,
		BCP_vec< double > &	cut_new_bd
	)

virtual

Initialize data members at the start of processing a new subproblem.

Reimplemented from BCP_lp_user.

virtual void BB_lp::modify_lp_parameters	(	OsiSolverInterface *	lp,
		const int	changeType,
		bool	in_strong_branching
	)

virtual

Modify the parameters of the LP solver.

Called at the beginning of the optimization of a node when the node LP is not yet solved.

Reimplemented from BCP_lp_user.

virtual BCP_solution* BB_lp::test_feasibility	(	const BCP_lp_result &	lp_result,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts
	)

virtual

Test feasibility of the LP solution.

Called after each node LP has been solved. Called even if the node LP was infeasible Called also during strong branching

Reimplemented from BCP_lp_user.

virtual void BB_lp::logical_fixing	(	const BCP_lp_result &	lpres,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts,
		const BCP_vec< BCP_obj_status > &	var_status,
		const BCP_vec< BCP_obj_status > &	cut_status,
		const int	var_bound_changes_since_logical_fixing,
		BCP_vec< int > &	changed_pos,
		BCP_vec< double > &	new_bd
	)

virtual

Perform fixing of variables.

Called at each iteration, after test_feasibility, if the node is not fathomable

Reimplemented from BCP_lp_user.

virtual void BB_lp::generate_cuts_in_lp	(	const BCP_lp_result &	lpres,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts,
		BCP_vec< BCP_cut * > &	new_cuts,
		BCP_vec< BCP_row * > &	new_rows
	)

virtual

Cut generation.

Send to BCP the cuts generated in test_feasibility. Use this function to generate standard cuts (Knapsack covers, Lift-and-Project, odd holes, ...).

Reimplemented from BCP_lp_user.

virtual BCP_solution* BB_lp::generate_heuristic_solution	(	const BCP_lp_result &	lpres,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts
	)

virtual

Simple rounding heuristic.

Reimplemented from BCP_lp_user.

virtual void BB_lp::cuts_to_rows	(	const BCP_vec< BCP_var * > &	vars,
		BCP_vec< BCP_cut * > &	cuts,
		BCP_vec< BCP_row * > &	rows,
		const BCP_lp_result &	lpres,
		BCP_object_origin	origin,
		bool	allow_multiple
	)

virtual

Describes how to get a row of the matrix from the representation of the cut.

Required method when indexed or algorithmic cuts are used.

Reimplemented from BCP_lp_user.

virtual BCP_branching_decision BB_lp::select_branching_candidates	(	const BCP_lp_result &	lpres,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts,
		const BCP_lp_var_pool &	local_var_pool,
		const BCP_lp_cut_pool &	local_cut_pool,
		BCP_vec< BCP_lp_branching_object * > &	cands,
		bool	force_branch = `false`
	)

virtual

Called at the end of each iteration.

Possible return values are: BCP_DoNotBranch_Fathomed : The node should be fathomed without branching; BCP_DoNotBranch : BCP should continue to work on this node; BCP_DoBranch : Branching must be done. In this case the method returns the branching object candidates in one of the arguments.

Reimplemented from BCP_lp_user.

virtual void BB_lp::set_user_data_for_children	(	BCP_presolved_lp_brobj *	best,
		const int	selected
	)

virtual

Set up the user data for the children according to the chosen branching object.

Reimplemented from BCP_lp_user.

Member Data Documentation

BB_prob* BB_lp::p_desc

private

Pointer on the description of the problem.

Definition at line 26 of file BB_lp.hpp.

MY_user_data* BB_lp::p_ud

private

Pointer on the description of the user data.

Definition at line 29 of file BB_lp.hpp.

int BB_lp::in_strong

private

in_strong = 1 if and only if in strong branching phase

Definition at line 32 of file BB_lp.hpp.

double BB_lp::EPS

private

Hold the value of EPSILON of class BB_prob.

Definition at line 35 of file BB_lp.hpp.

BCP_vec<BCP_cut*> BB_lp::algo_cuts

private

Hold pointers on generated algorithmic cuts.

Definition at line 38 of file BB_lp.hpp.

std::vector<int> BB_lp::violated_cuts

private

Hold indices of violated indexed cuts.

Definition at line 41 of file BB_lp.hpp.

The documentation for this class was generated from the following file:

/tmp/Bcp-1.4.4/Bcp/examples/BAC/include/BB_lp.hpp

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation