#include <CSP_lp.hpp>
Inheritance diagram for CSP_lp:
Public Member Functions | |
CSP_lp () | |
~CSP_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 a ptr to an OsiSolverInterface object that will be used for solving the LP relaxations. | |
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) |
This method serves as hook for the user to do some preprocessing on a search tree node before the node is processed. | |
virtual void | modify_lp_parameters (OsiSolverInterface *lp, bool in_strong_branching) |
This method provides an opportunity for the user to change parameters of the LP solver before optimization in the LP solver starts. | |
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_solution * | generate_heuristic_solution (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts) |
Try to generate a heuristic solution (or return one generated during cut/variable generation. | |
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. | |
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 (BCP_vec< BCP_var * > &vars, BCP_vec< BCP_col * > &cols) |
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. | |
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 BCP_object_compare_result | compare_cuts (const BCP_cut *c0, const BCP_cut *c1) |
Compare two generated cuts. | |
virtual BCP_object_compare_result | compare_vars (const BCP_var *v0, const BCP_var *v1) |
Compare two generated variables. | |
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 * > &cands) |
Decide whether to branch or not and select a set of branching candidates if branching is decided upon. | |
BCP_lp_branching_object * | branch_on_half (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars) |
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. | |
virtual void | set_actions_for_children (BCP_presolved_lp_brobj *best) |
Decide what to do with the children of the selected branching object. | |
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. | |
Public Attributes | |
BCP_parameter_set< CSP_lp_par > | par |
CSPROBLEM * | csproblem |
CSP_colgen * | colgen |
Private Attributes | |
std::vector< PATTERN * > | improving_patterns_ |
Definition at line 19 of file CSP_lp.hpp.
CSP_lp::CSP_lp | ( | ) | [inline] |
Definition at line 40 of file CSP_lp.hpp.
CSP_lp::~CSP_lp | ( | ) | [inline] |
virtual void CSP_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.
Reimplemented from BCP_lp_user.
virtual void CSP_lp::pack_var_algo | ( | const BCP_var_algo * | var, | |
BCP_buffer & | buf | |||
) | [inline, virtual] |
virtual BCP_var_algo* CSP_lp::unpack_var_algo | ( | BCP_buffer & | buf | ) | [inline, virtual] |
Unpack an algorithmic variable.
Definition at line 68 of file CSP_lp.hpp.
References CSP_var_unpack().
virtual OsiSolverInterface* CSP_lp::initialize_solver_interface | ( | ) | [virtual] |
Create a ptr to an OsiSolverInterface object that will be used for solving the LP relaxations.
The default implementation uses Clp. 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 CSP_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] |
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.
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 void CSP_lp::modify_lp_parameters | ( | OsiSolverInterface * | lp, | |
bool | in_strong_branching | |||
) | [virtual] |
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 double CSP_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* CSP_lp::generate_heuristic_solution | ( | const BCP_lp_result & | lpres, | |
const BCP_vec< BCP_var * > & | vars, | |||
const BCP_vec< BCP_cut * > & | cuts | |||
) | [virtual] |
Try to generate a heuristic solution (or return one generated during cut/variable generation.
Return a pointer to the generated solution or return a NULL pointer.
Reimplemented from BCP_lp_user.
virtual void CSP_lp::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 | |||
) | [virtual] |
Restoring feasibility.
This method is invoked before fathoming a search tree node that has been found infeasible and the variable pricing did not generate any new variables.
The user has to check all variables here.
Reimplemented from BCP_lp_user.
virtual void CSP_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.)
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) |
Reimplemented from BCP_lp_user.
virtual void CSP_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 | |||
) | [inline, virtual] |
Generate cuts within the LP process.
Sometimes too much information would need to be transmitted for cut generation (e.g., the full tableau for Gomory cuts) or the cut generation is so fast that transmitting the info would take longer than generating the cuts. In such cases it might better to generate the cuts locally. This routine provides the opportunity.
Default: empty for now. To be interfaced to Cgl.
lpres | solution to the current LP relaxation (IN) | |
vars | the variabless currently in the relaxation (IN) | |
cuts | the cuts currently in the relaxation (IN) | |
new_cuts | the vector of generated cuts (OUT) | |
new_rows | the correspontding rows(OUT) |
Reimplemented from BCP_lp_user.
Definition at line 255 of file CSP_lp.hpp.
References BCP_lp_user::generate_cuts_in_lp().
virtual void CSP_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.
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 BCP_object_compare_result CSP_lp::compare_cuts | ( | const BCP_cut * | c0, | |
const BCP_cut * | c1 | |||
) | [inline, virtual] |
Compare two generated cuts.
Cuts are generated in different iterations, they come from the Cut Pool, etc. There is a very real possibility that the LP process receives several cuts that are either identical or one of them is better then another (cuts off everything the other cuts off). This routine is used to decide which one to keep if not both.
Default: Return BCP_DifferentObjs
.
Reimplemented from BCP_lp_user.
Definition at line 298 of file CSP_lp.hpp.
References BCP_lp_user::compare_cuts().
virtual BCP_object_compare_result CSP_lp::compare_vars | ( | const BCP_var * | v0, | |
const BCP_var * | v1 | |||
) | [inline, virtual] |
Compare two generated variables.
Variables are generated in different iterations, they come from the Variable Pool, etc. There is a very real possibility that the LP process receives several variables that are either identical or one of them is better then another (e.g., almost identical but has much lower reduced cost). This routine is used to decide which one to keep if not both.
Default: Return BCP_DifferentObjs
.
Reimplemented from BCP_lp_user.
Definition at line 314 of file CSP_lp.hpp.
References BCP_lp_user::compare_vars().
virtual void CSP_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 | |||
) | [inline, 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.
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.
Definition at line 337 of file CSP_lp.hpp.
References BCP_lp_user::logical_fixing().
virtual BCP_branching_decision CSP_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.
BCP_lp_branching_object* CSP_lp::branch_on_half | ( | const BCP_lp_result & | lpres, | |
const BCP_vec< BCP_var * > & | vars | |||
) |
virtual BCP_branching_object_relation CSP_lp::compare_branching_candidates | ( | BCP_presolved_lp_brobj * | new_solved, | |
BCP_presolved_lp_brobj * | old_solved | |||
) | [inline, virtual] |
Decide which branching object is preferred for branching.
Based on the member fields of the two presolved candidate branching objects decide which one should be preferred for really branching on it. Possible return values are: BCP_OldPresolvedIsBetter
, BCP_NewPresolvedIsBetter
and BCP_NewPresolvedIsBetter_BranchOnIt
. This last value (besides specifying which candidate is preferred) also indicates that no further candidates should be examined, branching should be done on this candidate.
Default: The behavior of this method is governed by the BranchingObjectComparison
parameter in BCP_lp_par.
Reimplemented from BCP_lp_user.
Definition at line 380 of file CSP_lp.hpp.
References BCP_lp_user::compare_branching_candidates().
virtual void CSP_lp::set_actions_for_children | ( | BCP_presolved_lp_brobj * | best | ) | [virtual] |
Decide what to do with the children of the selected branching object.
Fill out the _child_action
field in best
. This will specify for every child what to do with it. Possible values for each individual child are BCP_PruneChild
, BCP_ReturnChild
and BCP_KeepChild
. There can be at most child with this last action specified. It means that in case of diving this child will be processed by this LP process as the next search tree node.
Default: Every action is BCP_ReturnChild
. However, if BCP dives then one child will be mark with BCP_KeepChild
. The decision which child to keep is based on the ChildPreference
parameter in BCP_lp_par. Also, if a child has a presolved lower bound that is higher than the current upper bound then that child is mark as BCP_FathomChild
.
THINK*: Should those children be sent back for processing in the next phase?
Reimplemented from BCP_lp_user.
virtual void CSP_lp::purge_slack_pool | ( | const BCP_vec< BCP_cut * > & | slack_pool, | |
BCP_vec< int > & | to_be_purged | |||
) | [inline, virtual] |
Selectively purge the list of slack cuts.
When a cut becomes ineffective and is eventually purged from the LP formulation it is moved into slack_pool
. The user might consider cuts might later for branching. This function enables the user to purge any cut from the slack pool (those she wouldn't consider anyway). Of course, the user is not restricted to these cuts when branching, this is only there to help to collect slack cuts. The user should put the indices of the cuts to be purged into the provided vector.
Default: Purges the slack cut pool according to the SlackCutDiscardingStrategy
rule in BCP_lp_par (purge everything before every iteration or before a new search tree node).
slack_pool | the pool of slacks. (IN) | |
to_be_purged | the indices of the cuts to be purged. (OUT) |
Reimplemented from BCP_lp_user.
Definition at line 432 of file CSP_lp.hpp.
References BCP_lp_user::purge_slack_pool().
std::vector<PATTERN*> CSP_lp::improving_patterns_ [private] |
Definition at line 29 of file CSP_lp.hpp.