MKC_lp Class Reference

#include <MKC_lp.hpp>

Inheritance diagram for MKC_lp:

Inheritance graph
[legend]
Collaboration diagram for MKC_lp:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 MKC_lp ()
 ~MKC_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)
virtual BCP_var_algounpack_var_algo (BCP_buffer &buf)
virtual OsiSolverInterfaceinitialize_solver_interface ()
 Create LP solver environment.
void modify_lp_parameters (OsiSolverInterface *lp, bool in_strong_branching)
 Modify parameters of the LP solver before optimization.
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 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 BCP_solutiontest_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 void pack_feasible_solution (BCP_buffer &buf, const BCP_solution *sol)
 Pack a MIP feasible solution into a buffer.
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.
void vars_to_cols (const BCP_vec< BCP_cut * > &cuts, BCP_vec< BCP_var * > &vars, BCP_vec< BCP_col * > &cols)
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.
void generate_vars (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double rc_bound, BCP_vec< BCP_var * > &new_vars)
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.
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 * > &candidates)

Public Attributes

BCP_parameter_set< MKC_lp_parpar
double * objhist
MKC_knapsack_set kss
MKC_knapsack_fixingks_fixings
BCP_vec< MKC_var * > * enumerated_ks
BCP_vec< MKC_var * > input_vars
BCP_vec< BCP_var * > generated_vars
double best_lb_in_root
double start_time

Detailed Description

Definition at line 17 of file MKC_lp.hpp.


Constructor & Destructor Documentation

MKC_lp::MKC_lp (  )  [inline]

Definition at line 33 of file MKC_lp.hpp.

MKC_lp::~MKC_lp (  )  [inline]

Definition at line 35 of file MKC_lp.hpp.

References enumerated_ks, input_vars, ks_fixings, MKC_knapsack_set::ks_num, kss, objhist, and purge_ptr_vector().


Member Function Documentation

virtual void MKC_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 MKC_lp::pack_var_algo ( const BCP_var_algo var,
BCP_buffer buf 
) [virtual]

virtual BCP_var_algo* MKC_lp::unpack_var_algo ( BCP_buffer buf  )  [virtual]

virtual OsiSolverInterface* MKC_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.

void MKC_lp::modify_lp_parameters ( OsiSolverInterface lp,
bool  in_strong_branching 
) [virtual]

Modify parameters of the LP solver before optimization.

This method provides an opportunity for the user to change parameters of the LP solver before optimization in the LP solver starts. The second argument indicates whether the optimization is a "regular" optimization or it will take place in strong branching. Default: empty method.

Reimplemented from BCP_lp_user.

virtual void MKC_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 double MKC_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 BCP_solution* MKC_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 void MKC_lp::pack_feasible_solution ( BCP_buffer buf,
const BCP_solution sol 
) [virtual]

Pack a MIP feasible solution into a buffer.

The solution will be unpacked in the Tree Manager by the BCP_tm_user::unpack_feasible_solution() method.

Default: The default implementation assumes that sol is a BCP_solution_generic object (containing variables at nonzero level) and packs it.

Parameters:
buf (OUT) the buffer to pack into
sol (IN) the solution to be packed

Reimplemented from BCP_lp_user.

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

void MKC_lp::vars_to_cols ( const BCP_vec< BCP_cut * > &  cuts,
BCP_vec< BCP_var * > &  vars,
BCP_vec< BCP_col * > &  cols 
)

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

void MKC_lp::generate_vars ( const BCP_lp_result lpres,
const BCP_vec< BCP_var * > &  vars,
const double  rc_bound,
BCP_vec< BCP_var * > &  new_vars 
)

virtual void MKC_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]

This method provides an opportunity for the user to tighten the bounds of variables.

The method is invoked after reduced cost fixing. The results are returned in the last two parameters.
Default: empty method.

Parameters:
lpres the result of the most recent LP optimization,
vars the variables in the current formulation,
status the stati of the variables as known to the system,
var_bound_changes_since_logical_fixing the number of variables whose bounds have changed (by reduced cost fixing) since the most recent invocation of this method that has actually forced changes returned something in the last two arguments,
changed_pos the positions of the variables whose bounds should be changed
new_bd the new bounds (lb/ub pairs) of these variables.

Reimplemented from BCP_lp_user.

virtual BCP_branching_decision MKC_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 * > &  candidates 
) [virtual]


Member Data Documentation

BCP_parameter_set<MKC_lp_par> MKC_lp::par

Definition at line 19 of file MKC_lp.hpp.

double* MKC_lp::objhist

Definition at line 20 of file MKC_lp.hpp.

Referenced by ~MKC_lp().

MKC_knapsack_set MKC_lp::kss

Definition at line 21 of file MKC_lp.hpp.

Referenced by ~MKC_lp().

MKC_knapsack_fixing* MKC_lp::ks_fixings

Definition at line 23 of file MKC_lp.hpp.

Referenced by ~MKC_lp().

BCP_vec<MKC_var*>* MKC_lp::enumerated_ks

Definition at line 24 of file MKC_lp.hpp.

Referenced by ~MKC_lp().

BCP_vec<MKC_var*> MKC_lp::input_vars

Definition at line 25 of file MKC_lp.hpp.

Referenced by ~MKC_lp().

BCP_vec<BCP_var*> MKC_lp::generated_vars

Definition at line 27 of file MKC_lp.hpp.

double MKC_lp::best_lb_in_root

Definition at line 29 of file MKC_lp.hpp.

double MKC_lp::start_time

Definition at line 30 of file MKC_lp.hpp.


The documentation for this class was generated from the following file:
Generated on Thu Jan 15 03:03:29 2009 for coin-Bcp by  doxygen 1.4.7