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

#include <OS_lp.hpp>

Inheritance diagram for OS_lp:

Collaboration diagram for OS_lp:

Public Member Functions
virtual OsiSolverInterface *	initialize_solver_interface ()
	Pack algorithmic cuts. 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, bool in_strong_branching)
	Modify the parameters of the LP solver. More...

virtual void	display_lp_solution (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts, const bool final_lp_solution)
	Test feasibility of the LP solution. 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...

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	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...

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

virtual	~OS_lp ()
	Destructor. More...

Packing and unpacking methods
virtual void	unpack_module_data (BCP_buffer &buf)
	Unpack data sent from the tree manager. 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	modify_lp_parameters (OsiSolverInterface *lp, const int changeType, bool in_strong_branching)
	Modify parameters of the LP solver before optimization. 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...

virtual BCP_solution *	test_feasibility (const BCP_lp_result &lp_result, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
	Evaluate and return MIP feasibility of the current solution. 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	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)
	Generate cuts within the LP process. 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 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)
	This method provides an opportunity for the user to tighten the bounds of 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
OsiSolverInterface *	cg_lp

OS_prob *	os_prob
	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 OS_prob. More...

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

BCP_vec< BCP_var * >	algo_vars
	Hold pointers on generated variables. More...

bool	generated_vars

bool	generated_cuts

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

Detailed Description

Class for operations at the node level.

Definition at line 28 of file OS_lp.hpp.

Constructor & Destructor Documentation

OS_lp::OS_lp ( )

inline

Default constructor.

Definition at line 70 of file OS_lp.hpp.

virtual OS_lp::~OS_lp ( )

inlinevirtual

Destructor.

Definition at line 73 of file OS_lp.hpp.

Member Function Documentation

void OS_lp::unpack_module_data ( BCP_buffer & buf )

virtual

Unpack data sent from the tree manager.

we also have access to the osinstance object that was created in OS_tm the OS_tm tree manager sent us a pointer to this – the osinstance is actually a memeber of OS_prob – put in this class information we want access to

Reimplemented from BCP_lp_user.

Definition at line 34 of file OS_lp.cpp.

OsiSolverInterface * OS_lp::initialize_solver_interface ( )

virtual

Pack algorithmic cuts.

Unpack algorithmic cuts Pack user data Unpack user data Called only once at the beginning, from the root node

Reimplemented from BCP_lp_user.

Definition at line 55 of file OS_lp.cpp.

void OS_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.

Definition at line 63 of file OS_lp.cpp.

void OS_lp::modify_lp_parameters	(	OsiSolverInterface *	lp,
		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.

Definition at line 111 of file OS_lp.cpp.

void OS_lp::display_lp_solution	(	const BCP_lp_result &	lpres,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts,
		const bool	final_lp_solution
	)

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 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.

Definition at line 594 of file OS_lp.cpp.

BCP_solution * OS_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.

Definition at line 145 of file OS_lp.cpp.

void OS_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.

Definition at line 286 of file OS_lp.cpp.

BCP_branching_decision OS_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.

Definition at line 154 of file OS_lp.cpp.

void OS_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.

Definition at line 245 of file OS_lp.cpp.

void OS_lp::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
	)

virtual

Convert a set of variables into corresponding columns for the current LP relaxation.

Converting means to compute for each variable the coefficients corresponding to each cut and create BCP_col objects that can be added to the formulation.

See the documentation of cuts_to_rows() above for the use of this method (just reverse the role of cuts and variables.)

Parameters

cuts	the cuts currently in the relaxation (IN)
vars	the variables to be converted (IN/OUT)
cols	the colums the variables convert into (OUT)
lpres	solution to the current LP relaxation (IN)
origin	where the do the cuts come from (IN)
allow_multiple	whether multiple expansion, i.e., lifting, is allowed (IN)

Default: throw an exception (if this method is invoked then the user must have generated variables and BCP has no way to know how to convert them).

Reimplemented from BCP_lp_user.

Definition at line 311 of file OS_lp.cpp.

void OS_lp::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
	)

virtual

Process the result of an iteration.

This includes:

computing a true lower bound on the subproblem.
In case column generation is done the lower bound for the subproblem might not be the same as the objective value of the current LP relaxation. Here the user has an option to return a true lower bound.
test feasibility of the solution (or generate a heuristic solution)
generating cuts and/or variables

The reason for the existence of this method is that (especially when column generation is done) these tasks are so intertwined that it is much easier to execute them in one method instead of in several separate methods.

The default behavior is to do nothing and invoke the individual methods one-by-one.

Parameters

lp_result	the result of the most recent LP optimization (IN)
vars	variables currently in the formulation (IN)
cuts	variables currently in the formulation (IN)
old_lower_bound	the previously known best lower bound (IN)
new_cuts	the vector of generated cuts (OUT)
new_rows	the correspontding rows(OUT)
new_vars	the vector of generated variables (OUT)
new_cols	the correspontding columns(OUT)

Cgl cut addition scope

Reimplemented from BCP_lp_user.

Definition at line 339 of file OS_lp.cpp.

Member Data Documentation

OsiSolverInterface* OS_lp::cg_lp

private

Definition at line 30 of file OS_lp.hpp.

OS_prob* OS_lp::os_prob

private

Pointer on the description of the problem.

Definition at line 35 of file OS_lp.hpp.

MY_user_data* OS_lp::p_ud

private

Pointer on the description of the user data.

Definition at line 38 of file OS_lp.hpp.

int OS_lp::in_strong

private

in_strong = 1 if and only if in strong branching phase

Definition at line 41 of file OS_lp.hpp.

double OS_lp::EPS

private

Hold the value of EPSILON of class OS_prob.

Definition at line 44 of file OS_lp.hpp.

BCP_vec<BCP_cut*> OS_lp::algo_cuts

private

Hold pointers on generated algorithmic cuts.

Definition at line 47 of file OS_lp.hpp.

BCP_vec<BCP_var*> OS_lp::algo_vars

private

Hold pointers on generated variables.

Definition at line 50 of file OS_lp.hpp.

bool OS_lp::generated_vars

private

Definition at line 53 of file OS_lp.hpp.

bool OS_lp::generated_cuts

private

Definition at line 56 of file OS_lp.hpp.

std::vector<int> OS_lp::violated_cuts

private

Hold indices of violated indexed cuts.

Definition at line 59 of file OS_lp.hpp.

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

/tmp/OS-2.10.2/examples/branchCutPrice/include/OS_lp.hpp
/tmp/OS-2.10.2/examples/branchCutPrice/LP/OS_lp.cpp

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation