MCF2_lp Class Reference

#include <MCF2_lp.hpp>

Inheritance diagram for MCF2_lp:

Collaboration diagram for MCF2_lp:

Public Member Functions
	MCF2_lp ()
virtual	~MCF2_lp ()
virtual void	unpack_module_data (BCP_buffer &buf)
	Unpack the initial information sent to the LP process by the Tree Manager.
virtual void	pack_var_algo (const BCP_var_algo *var, BCP_buffer &buf)
	Pack an algorithmic variable.
virtual BCP_var_algo *	unpack_var_algo (BCP_buffer &buf)
	Unpack an algorithmic variable.
virtual OsiSolverInterface *	initialize_solver_interface ()
	Create LP solver environment.
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)
	Initializing a new search tree node.
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.
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.
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.
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.
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)
	Decide whether to branch or not and select a set of branching candidates if branching is decided upon.
Private Attributes
OsiSolverInterface *	cg_lp
BCP_parameter_set< MCF2_par >	par
MCF2_data	data
std::vector < MCF2_branch_decision > *	branch_history
std::map< int, double > *	flows
BCP_vec< BCP_var * >	gen_vars
bool	generated_vars

Detailed Description

Definition at line 12 of file MCF2_lp.hpp.

Constructor & Destructor Documentation

MCF2_lp::MCF2_lp ( ) [inline]

Definition at line 25 of file MCF2_lp.hpp.

virtual MCF2_lp::~MCF2_lp ( ) [inline, virtual]

Definition at line 26 of file MCF2_lp.hpp.

Member Function Documentation

virtual void MCF2_lp::unpack_module_data ( BCP_buffer & buf ) [virtual]

Unpack the initial information sent to the LP process by the Tree Manager.

This information was packed by the method BCP_tm_user::pack_module_data() invoked with BCP_ProcessType_LP as the third (target process type) argument.

Default: empty method.

Reimplemented from BCP_lp_user.

virtual void MCF2_lp::pack_var_algo	(	const BCP_var_algo *	var,
		BCP_buffer &	buf
	)			`[inline, virtual]`

Pack an algorithmic variable.

Reimplemented from BCP_lp_user.

Definition at line 34 of file MCF2_lp.hpp.

virtual BCP_var_algo* MCF2_lp::unpack_var_algo ( BCP_buffer & buf ) [inline, virtual]

Unpack an algorithmic variable.

Reimplemented from BCP_lp_user.

Definition at line 37 of file MCF2_lp.hpp.

virtual OsiSolverInterface* MCF2_lp::initialize_solver_interface ( ) [virtual]

Create LP solver environment.

Create the LP solver class that will be used for solving the LP relaxations. The default implementation picks up which COIN_USE_XXX is defined and initializes an lp solver of that type. This is probably OK for most users. The only reason to override this method is to be able to choose at runtime which lp solver to instantiate (maybe even different solvers on different processors). In this case she should probably also override the pack_warmstart() and unpack_warmstart() methods in this class and in the BCP_tm_user class.

Reimplemented from BCP_lp_user.

virtual void MCF2_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]`

Initializing a new search tree node.

This method serves as hook for the user to do some preprocessing on a search tree node before the node is processed. Also, logical fixing results can be returned in the last four parameters. This might be very useful if the branching implies significant tightening.
Default: empty method.

Parameters:

	vars	(IN) The variables in the current formulation
	cuts	(IN) The cuts in the current formulation
	var_status	(IN) The stati of the variables
	cut_status	(IN) The stati of the cuts
	var_changed_pos	(OUT) The positions of the variables whose bounds should be tightened
	var_new_bd	(OUT) The new lb/ub of those variables
	cut_changed_pos	(OUT) The positions of the cuts whose bounds should be tightened
	cut_new_bd	(OUT) The new lb/ub of those cuts

Reimplemented from BCP_lp_user.

virtual BCP_solution* MCF2_lp::test_feasibility	(	const BCP_lp_result &	lp_result,
		const BCP_vec< BCP_var * > &	vars,
		const BCP_vec< BCP_cut * > &	cuts
	)			`[virtual]`

Evaluate and return MIP feasibility of the current solution.

If the solution is MIP feasible, return a solution object otherwise return a NULL pointer. The useris also welcome to heuristically generate a solution and return a pointer to that solution (although the user will have another chance (after cuts and variables are generated) to return/create heuristically generated solutions. (After all, it's quite possible that solutions are generated during cut/variable generation.)

Default: test feasibility based on the FeeasibilityTest parameter in BCP_lp_par which defults to BCP_FullTest_Feasible.

Parameters:

	lp_result	the result of the most recent LP optimization
	vars	variables currently in the formulation
	cuts	variables currently in the formulation

Reimplemented from BCP_lp_user.

virtual double MCF2_lp::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
	)			`[virtual]`

Compute a true lower bound for 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.
The default implementation returns the objective value of the current LP relaxation if no column generation is done, otherwise returns the current (somehow previously computed) true lower bound.

Reimplemented from BCP_lp_user.

virtual void MCF2_lp::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
	)			`[virtual]`

Generate variables within the LP process.

Sometimes too much information would need to be transmitted for variable generation or the variable generation is so fast that transmitting the info would take longer than generating the variables. In such cases it might be better to generate the variables locally. This routine provides the opportunity.

Default: empty method.

Parameters:

	lpres	solution to the current LP relaxation (IN)
	vars	the variabless currently in the relaxation (IN)
	cuts	the cuts currently in the relaxation (IN)
	before_fathom	if true then BCP is about to fathom the node, so spend some extra effort generating variables if you want to avoid that...
	new_vars	the vector of generated variables (OUT)
	new_cols	the correspontding columns(OUT)

Reimplemented from BCP_lp_user.

virtual void MCF2_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.

virtual BCP_branching_decision MCF2_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
	)			`[virtual]`

Decide whether to branch or not and select a set of branching candidates if branching is decided upon.

The return value indicates what should be done: branching, continuing with the same node or abandoning the node completely.

Default: Branch if both local pools are empty. If branching is done then several (based on the StrongBranch_CloseToHalfNum and StrongBranch_CloseToOneNum parameters in BCP_lp_par) variables are selected for strong branching.

"Close-to-half" variables are those that should be integer and are at a fractional level. The measure of their fractionality is their distance from the closest integer. The most fractional variables will be selected, i.e., those that are close to half. If there are too many such variables then those with higher objective value have priority.

"Close-to-on" is interpreted in a more literal sense. It should be used only if the integer variables are binary as it select those fractional variables which are away from 1 but are still close. If there are too many such variables then those with lower objective value have priority.

Parameters:

	lpres	the result of the most recent LP optimization.
	vars	the variables in the current formulation.
	cuts	the cuts in the current formulation.
	local_var_pool	the local pool that holds variables with negative reduced cost. In case of continuing with the node the best so many variables will be added to the formulation (those with the most negative reduced cost).
	local_cut_pool	the local pool that holds violated cuts. In case of continuing with the node the best so many cuts will be added to the formulation (the most violated ones).
	cands	the generated branching candidates.