#include <BCP_lp_user.hpp>
Inheritance diagram for BCP_lp_user:
Public Member Functions | |
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. | |
int | process_id () const |
What is the process id of the current process. | |
int | parent () const |
the process id of the parent | |
void | send_message (const int target, const BCP_buffer &buf, BCP_message_tag tag=BCP_Msg_User) |
Send a message to a particular process. | |
void | receive_message (const int sender, BCP_buffer &buf, BCP_message_tag tag=BCP_Msg_User) |
Wait for a message and receive it. | |
void | broadcast_message (const BCP_process_t proc_type, const BCP_buffer &buf) |
Broadcast the message to all processes of the given type. | |
virtual void | process_message (BCP_buffer &buf) |
Process a message that has been sent by another process' user part to this process' user part. | |
virtual OsiSolverInterface * | initialize_solver_interface () |
Create LP solver environment. | |
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). | |
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 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. | |
virtual void | modify_lp_parameters (OsiSolverInterface *lp, const int changeType, bool in_strong_branching) |
Modify parameters of the LP solver before optimization. | |
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. | |
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 | 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. | |
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 | set_user_data_for_children (BCP_presolved_lp_brobj *best, const int selected) |
For each child create a user data object and put it into the appropriate entry in best->user_data() . | |
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). | |
Methods to set and get the pointer to the BCP_lp_prob | |
object. It is unlikely that the users would want to muck around with these (especially with the set method!) but they are here to provide total control. | |
void | setLpProblemPointer (BCP_lp_prob *ptr) |
Set the pointer. | |
BCP_lp_prob * | getLpProblemPointer () |
Get the pointer. | |
Informational methods for the user. | |
double | upper_bound () const |
Return what is the best known upper bound (might be BCP_DBL_MAX). | |
bool | over_ub (double lb) const |
Return true / false depending on whether the lb argument is over the current upper bound or not. | |
int | current_phase () const |
Return the phase the algorithm is in. | |
int | current_level () const |
Return the level of the search tree node being processed. | |
int | current_index () const |
Return the internal index of the search tree node being processed. | |
int | current_iteration () const |
Return the iteration count within the search tree node being processed. | |
double | start_time () const |
Return when the LP process started. | |
BCP_user_data * | get_user_data () |
Return a pointer to the BCP_user_data structure the user (may have) stored in this node. | |
Methods to get/set BCP parameters on the fly | |
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) |
A methods to send a solution to the Tree Manager. The user can | |
invoke this method at any time to send off a solution. | |
void | send_feasible_solution (const BCP_solution *sol) |
Constructor, Destructor | |
BCP_lp_user () | |
virtual | ~BCP_lp_user () |
Being virtual, the destructor invokes the destructor for the real type of the object being deleted. | |
Helper functions for selecting subset of entries from a double | |
vector. The indices (their position with respect to first ) of the variables satisfying the criteria are returned in the last argument. | |
void | select_nonzeros (const double *first, const double *last, const double etol, BCP_vec< int > &nonzeros) const |
Select all nonzero entries. | |
void | select_zeros (const double *first, const double *last, const double etol, BCP_vec< int > &zeros) const |
Select all zero entries. | |
void | select_positives (const double *first, const double *last, const double etol, BCP_vec< int > &positives) const |
Select all positive entries. | |
void | select_fractions (const double *first, const double *last, const double etol, BCP_vec< int > &fractions) const |
Select all fractional entries. | |
Packing and unpacking methods | |
virtual void | unpack_module_data (BCP_buffer &buf) |
Unpack the initial information sent to the LP process by the Tree Manager. | |
MIP feasibility testing of LP solutions and heuristics | |
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. | |
Helper functions for test_feasibility .
If the solution is feasible a pointer to a BCP_solution_generic object is returned. Note that the solutions generated by these helper functions DO NOT OWN the pointers in the | |
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. | |
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. | |
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. | |
Packing of solutions | |
virtual void | pack_feasible_solution (BCP_buffer &buf, const BCP_solution *sol) |
Pack a MIP feasible solution into a buffer. | |
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. | |
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. | |
Displaying of LP solutions | |
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. | |
Converting cuts and variables into rows and columns | |
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) |
Convert (and possibly lift) a set of cuts into corresponding rows for the current LP relaxation. | |
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. | |
Generating cuts and variables | |
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. | |
Logical fixing | |
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. | |
Branching related methods | |
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) |
Decide whether to branch or not and select a set of branching candidates if branching is decided upon. | |
Helper functions for select_branching_candidates() | |
virtual int | try_to_branch (OsiBranchingInformation &branchInfo, OsiSolverInterface *solver, OsiChooseVariable *choose, OsiBranchingObject *&branchObject, bool allowVarFix) |
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. | |
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. | |
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 . | |
Purging the slack pool | |
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. | |
Private Member Functions | |
BCP_lp_user (const BCP_lp_user &) | |
BCP_lp_user & | operator= (const BCP_lp_user &) |
Private Attributes | |
bool | using_deprecated_set_user_data_for_children |
BCP_lp_prob * | p |
OsiBabSolver * | babSolver_ |
In that derived class the user can store data to be used in the methods she overrides. Also that is the object the user must return in the USER_initialize::lp_init() method.
There are two kind of methods in the class. The non-virtual methods are helper functions for the built-in defaults, but the user can use them as well. The virtual methods execute steps in the BCP algorithm where the user might want to override the default behavior.
The default implementations fall into three major categories.
Definition at line 75 of file BCP_lp_user.hpp.
BCP_lp_user::BCP_lp_user | ( | const BCP_lp_user & | ) | [private] |
BCP_lp_user::BCP_lp_user | ( | ) | [inline] |
Definition at line 154 of file BCP_lp_user.hpp.
virtual BCP_lp_user::~BCP_lp_user | ( | ) | [inline, virtual] |
Being virtual, the destructor invokes the destructor for the real type of the object being deleted.
Definition at line 157 of file BCP_lp_user.hpp.
BCP_lp_user& BCP_lp_user::operator= | ( | const BCP_lp_user & | ) | [private] |
void BCP_lp_user::setLpProblemPointer | ( | BCP_lp_prob * | ptr | ) | [inline] |
Set the pointer.
Definition at line 93 of file BCP_lp_user.hpp.
References p.
Referenced by BCP_lp_main(), and BCP_single_environment::register_process().
BCP_lp_prob* BCP_lp_user::getLpProblemPointer | ( | ) | [inline] |
Get the pointer.
Definition at line 95 of file BCP_lp_user.hpp.
References p.
Referenced by BM_lp::bbBranch(), BM_lp::do_distributed_SB(), BM_lp::generate_cuts_in_lp(), BM_lp::initialize_new_search_tree_node(), BM_lp::initialize_solver_interface(), OS_lp::process_lp_result(), BM_lp::select_branching_candidates(), MCF3_lp::test_feasibility(), MCF2_lp::test_feasibility(), MCF1_lp::test_feasibility(), BB_lp::test_feasibility(), BM_lp::test_feasibility_hybrid(), and BM_lp::unpack_module_data().
void BCP_lp_user::setOsiBabSolver | ( | OsiBabSolver * | ptr | ) | [inline] |
Definition at line 98 of file BCP_lp_user.hpp.
References babSolver_.
Referenced by BM_lp::initialize_solver_interface().
OsiBabSolver* BCP_lp_user::getOsiBabSolver | ( | ) | [inline] |
Definition at line 99 of file BCP_lp_user.hpp.
References babSolver_.
Referenced by BCP_lp_perform_strong_branching(), and reduced_cost_fixing().
double BCP_lp_user::upper_bound | ( | ) | const |
Return what is the best known upper bound (might be BCP_DBL_MAX).
Definition at line 29 of file BCP_lp_user.cpp.
References p, and BCP_lp_prob::ub().
Referenced by BM_lp::select_branching_candidates(), MCF3_lp::select_branching_candidates(), MCF2_lp::select_branching_candidates(), and MCF1_lp::select_branching_candidates().
bool BCP_lp_user::over_ub | ( | double | lb | ) | const |
Return true / false depending on whether the lb argument is over the current upper bound or not.
Definition at line 30 of file BCP_lp_user.cpp.
References BCP_lp_prob::over_ub(), and p.
Referenced by BM_lp::isBranchFathomable().
int BCP_lp_user::current_phase | ( | ) | const |
Return the phase the algorithm is in.
Definition at line 31 of file BCP_lp_user.cpp.
References p, and BCP_lp_prob::phase.
int BCP_lp_user::current_level | ( | ) | const |
Return the level of the search tree node being processed.
Definition at line 32 of file BCP_lp_user.cpp.
References BCP_lp_node::level, BCP_lp_prob::node, and p.
Referenced by OS_lp::select_branching_candidates(), BM_lp::select_branching_candidates(), select_branching_candidates(), BB_lp::select_branching_candidates(), BM_lp::sort_objects(), and BM_lp::test_feasibility_BB().
int BCP_lp_user::current_index | ( | ) | const |
Return the internal index of the search tree node being processed.
Definition at line 33 of file BCP_lp_user.cpp.
References BCP_lp_node::index, BCP_lp_prob::node, and p.
Referenced by load_problem(), BM_lp::process_SB_results(), BM_lp::select_branching_candidates(), BM_lp::sort_objects(), BM_lp::test_feasibility_BB(), and BM_lp::try_to_branch().
int BCP_lp_user::current_iteration | ( | ) | const |
Return the iteration count within the search tree node being processed.
Definition at line 34 of file BCP_lp_user.cpp.
References BCP_lp_node::iteration_count, BCP_lp_prob::node, and p.
Referenced by purge_slack_pool().
double BCP_lp_user::start_time | ( | ) | const |
Return when the LP process started.
Definition at line 35 of file BCP_lp_user.cpp.
References p, and BCP_lp_prob::start_time.
Referenced by BM_lp::process_SB_results(), BM_lp::sort_objects(), and BM_lp::test_feasibility_BB().
BCP_user_data * BCP_lp_user::get_user_data | ( | ) |
Return a pointer to the BCP_user_data structure the user (may have) stored in this node.
Definition at line 36 of file BCP_lp_user.cpp.
References BCP_lp_prob::node, p, and BCP_lp_node::user_data.
Referenced by OS_lp::initialize_new_search_tree_node(), BM_lp::initialize_new_search_tree_node(), MCF3_lp::initialize_new_search_tree_node(), BB_lp::initialize_new_search_tree_node(), BM_lp::numNlpFailed(), OS_lp::set_user_data_for_children(), MCF3_lp::set_user_data_for_children(), and BB_lp::set_user_data_for_children().
void BCP_lp_user::print | ( | const bool | ifprint, | |
const char * | format, | |||
... | ||||
) | const |
A method to print a message with the process id.
Definition at line 38 of file BCP_lp_user.cpp.
Referenced by BM_lp::bbBranch(), BCP_lp_branch(), BCP_lp_main_loop(), BCP_lp_perform_fathom(), BCP_lp_perform_strong_branching(), BCP_lp_select_branching_object(), BCP_print_brobj_stat(), compare_branching_candidates(), compare_cuts(), compare_vars(), cuts_to_rows(), display_lp_solution(), generate_cuts_in_lp(), generate_heuristic_solution(), generate_vars_in_lp(), initialize_new_search_tree_node(), logical_fixing(), modify_lp_parameters(), pack_dual_solution(), pack_feasible_solution(), pack_primal_solution(), purge_slack_pool(), restore_feasibility(), BM_lp::select_branching_candidates(), select_branching_candidates(), set_actions_for_children(), set_user_data_for_children(), test_binary(), test_feasibility(), test_full(), test_integral(), unpack_module_data(), and vars_to_cols().
char BCP_lp_user::get_param | ( | const BCP_lp_par::chr_params | key | ) | const |
Definition at line 51 of file BCP_lp_user.cpp.
References BCP_parameter_set< Par >::entry(), p, and BCP_lp_prob::par.
Referenced by OS_lp::display_lp_solution(), OS_lp::initialize_new_search_tree_node(), load_problem(), reduced_cost_fixing(), OS_lp::select_branching_candidates(), BM_lp::select_branching_candidates(), and select_branching_candidates().
int BCP_lp_user::get_param | ( | const BCP_lp_par::int_params | key | ) | const |
Definition at line 54 of file BCP_lp_user.cpp.
References BCP_parameter_set< Par >::entry(), p, and BCP_lp_prob::par.
double BCP_lp_user::get_param | ( | const BCP_lp_par::dbl_params | key | ) | const |
Definition at line 57 of file BCP_lp_user.cpp.
References BCP_parameter_set< Par >::entry(), p, and BCP_lp_prob::par.
const BCP_string & BCP_lp_user::get_param | ( | const BCP_lp_par::str_params | key | ) | const |
Definition at line 60 of file BCP_lp_user.cpp.
References BCP_parameter_set< Par >::entry(), p, and BCP_lp_prob::par.
void BCP_lp_user::set_param | ( | const BCP_lp_par::chr_params | key, | |
const bool | val | |||
) |
Definition at line 63 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::par, and BCP_parameter_set< Par >::set_entry().
Referenced by OS_lp::initialize_new_search_tree_node().
void BCP_lp_user::set_param | ( | const BCP_lp_par::chr_params | key, | |
const char | val | |||
) |
Definition at line 65 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::par, and BCP_parameter_set< Par >::set_entry().
void BCP_lp_user::set_param | ( | const BCP_lp_par::int_params | key, | |
const int | val | |||
) |
Definition at line 67 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::par, and BCP_parameter_set< Par >::set_entry().
void BCP_lp_user::set_param | ( | const BCP_lp_par::dbl_params | key, | |
const double | val | |||
) |
Definition at line 69 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::par, and BCP_parameter_set< Par >::set_entry().
void BCP_lp_user::set_param | ( | const BCP_lp_par::str_params | key, | |
const char * | val | |||
) |
Definition at line 71 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::par, and BCP_parameter_set< Par >::set_entry().
void BCP_lp_user::send_feasible_solution | ( | const BCP_solution * | sol | ) |
Definition at line 77 of file BCP_lp_user.cpp.
References BCP_GenerateColumns, BCP_Msg_FeasibleSolution, BCP_buffer::clear(), BCP_lp_node::colgen, BCP_process::get_parent(), BCP_lp_prob::granularity(), BCP_lp_prob::lp_solver, BCP_lp_prob::msg_buf, BCP_lp_prob::msg_env, BCP_lp_prob::node, BCP_solution::objective_value(), p, pack_feasible_solution(), BCP_message_environment::send(), and BCP_lp_prob::ub().
Referenced by BM_lp::bbBranch(), BCP_lp_main_loop(), and BCP_lp_test_feasibility().
void BCP_lp_user::select_nonzeros | ( | const double * | first, | |
const double * | last, | |||
const double | etol, | |||
BCP_vec< int > & | nonzeros | |||
) | const |
Select all nonzero entries.
Those are considered nonzero that have absolute value greater than etol
.
Definition at line 104 of file BCP_lp_user.cpp.
References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back().
Referenced by display_lp_solution(), pack_dual_solution(), and pack_primal_solution().
void BCP_lp_user::select_zeros | ( | const double * | first, | |
const double * | last, | |||
const double | etol, | |||
BCP_vec< int > & | zeros | |||
) | const |
Select all zero entries.
Those are considered zero that have absolute value less than etol
.
Definition at line 115 of file BCP_lp_user.cpp.
References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back().
void BCP_lp_user::select_positives | ( | const double * | first, | |
const double * | last, | |||
const double | etol, | |||
BCP_vec< int > & | positives | |||
) | const |
Select all positive entries.
Those are considered positive that have value greater than etol
.
Definition at line 126 of file BCP_lp_user.cpp.
References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back().
void BCP_lp_user::select_fractions | ( | const double * | first, | |
const double * | last, | |||
const double | etol, | |||
BCP_vec< int > & | fractions | |||
) | const |
Select all fractional entries.
Those are considered fractional that are further than etol
away from any integer value.
Definition at line 137 of file BCP_lp_user.cpp.
References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back().
Referenced by pack_primal_solution().
void BCP_lp_user::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 in BB_lp, MCF1_lp, MCF2_lp, MCF3_lp, BM_lp, and OS_lp.
Definition at line 151 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_main(), and BCP_single_environment::register_process().
int BCP_lp_user::process_id | ( | ) | const |
What is the process id of the current process.
Definition at line 161 of file BCP_lp_user.cpp.
References BCP_process::get_process_id(), and p.
int BCP_lp_user::parent | ( | ) | const |
the process id of the parent
Definition at line 168 of file BCP_lp_user.cpp.
References BCP_process::get_parent(), and p.
Referenced by BM_lp::process_message(), and BM_lp::try_to_branch().
void BCP_lp_user::send_message | ( | const int | target, | |
const BCP_buffer & | buf, | |||
BCP_message_tag | tag = BCP_Msg_User | |||
) |
Send a message to a particular process.
Definition at line 175 of file BCP_lp_user.cpp.
References BCP_lp_prob::msg_env, p, and BCP_message_environment::send().
Referenced by BM_lp::do_distributed_SB(), BM_lp::process_message(), and BM_lp::try_to_branch().
void BCP_lp_user::receive_message | ( | const int | sender, | |
BCP_buffer & | buf, | |||
BCP_message_tag | tag = BCP_Msg_User | |||
) |
Wait for a message and receive it.
Definition at line 183 of file BCP_lp_user.cpp.
References BCP_lp_prob::msg_env, p, and BCP_message_environment::receive().
Referenced by BM_lp::do_distributed_SB(), and BM_lp::try_to_branch().
void BCP_lp_user::broadcast_message | ( | const BCP_process_t | proc_type, | |
const BCP_buffer & | buf | |||
) |
Broadcast the message to all processes of the given type.
Definition at line 191 of file BCP_lp_user.cpp.
void BCP_lp_user::process_message | ( | BCP_buffer & | buf | ) | [virtual] |
Process a message that has been sent by another process' user part to this process' user part.
Reimplemented in BM_lp.
Definition at line 201 of file BCP_lp_user.cpp.
Referenced by BCP_lp_prob::process_message().
OsiSolverInterface * BCP_lp_user::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 in BB_lp, MCF1_lp, MCF2_lp, MCF3_lp, BM_lp, and OS_lp.
Definition at line 210 of file BCP_lp_user.cpp.
Referenced by BCP_lp_main(), and BCP_single_environment::register_process().
void BCP_lp_user::initialize_int_and_sos_list | ( | std::vector< OsiObject * > & | intAndSosObjects | ) | [virtual] |
Create the list of objects that can be used for branching (simple integer vars and SOS sets).
If nothing is done here then for each search tree node (just before starting to process the node) BCP will scan the variables and the matrix for candidates.
Definition at line 220 of file BCP_lp_user.cpp.
Referenced by BCP_lp_main().
void BCP_lp_user::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.
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 in BB_lp, MCF1_lp, MCF2_lp, MCF3_lp, BM_lp, and OS_lp.
Definition at line 227 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_prepare_for_new_node().
void BCP_lp_user::load_problem | ( | OsiSolverInterface & | osi, | |
BCP_problem_core * | core, | |||
BCP_var_set & | vars, | |||
BCP_cut_set & | cuts | |||
) | [virtual] |
Load the problem specified by core, vars, and cuts into the solver interface.
If the solver is an LP solver then the default is fine. If it's an NLP then the user has to do this herself.
Reimplemented in BM_lp.
Definition at line 243 of file BCP_lp_user.cpp.
References BCP_fatal_error::abort_on_error, BCP_lp_add_cols_to_lp(), BCP_lp_add_rows_to_lp(), BCP_Object_FromTreeManager, BCP_vec< T >::begin(), current_index(), BCP_problem_core::cutnum(), cuts_to_rows(), BCP_vec< T >::end(), BCP_vec< T >::entry(), get_param(), BCP_lp_par::Lp_DumpNodeDescCuts, BCP_lp_par::Lp_DumpNodeDescVars, BCP_lp_prob::lp_result, m, BCP_problem_core::matrix, p, purge_ptr_vector(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), BCP_vec< T >::unchecked_push_back(), BCP_problem_core::varnum(), and vars_to_cols().
Referenced by BCP_lp_create_lp(), and BM_lp::load_problem().
void BCP_lp_user::modify_lp_parameters | ( | OsiSolverInterface * | lp, | |
const int | changeType, | |||
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 what has changed in the LP before this method is called. 0: no change; 1: changes that affect primal feasibility (change in column/row bounds, added cuts); 2: changes that affect dual feasibility (added columns); 3: both. The last argument indicates whether the optimization is a "regular" optimization or it will take place in strong branching.
Default: If 1 or 2 then the appropriate simplex method will be hinted to the solver.
Reimplemented in BB_lp.
Definition at line 404 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_main_loop(), BCP_lp_perform_strong_branching(), and BCP_lp_select_branching_object().
void BCP_lp_user::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:
The default behavior is to do nothing and invoke the individual methods one-by-one.
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) |
Reimplemented in OS_lp.
Definition at line 424 of file BCP_lp_user.cpp.
References p, and BCP_lp_prob::user_has_lp_result_processing.
Referenced by BCP_lp_process_result(), and OS_lp::process_lp_result().
double BCP_lp_user::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 in MCF1_lp, MCF2_lp, MCF3_lp, and BM_lp.
Definition at line 441 of file BCP_lp_user.cpp.
References BCP_DoNotGenerateColumns_Fathom, BCP_DualObjLimReached, BCP_ProvenOptimal, BCP_lp_node::colgen, e, BCP_lp_prob::node, BCP_lp_result::objval(), p, BCP_lp_result::termcode(), and BCP_lp_prob::ub().
Referenced by BCP_lp_compute_lower_bound().
BCP_solution * BCP_lp_user::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
.
lp_result | the result of the most recent LP optimization | |
vars | variables currently in the formulation | |
cuts | variables currently in the formulation |
Reimplemented in BB_lp, MCF1_lp, MCF2_lp, MCF3_lp, and BM_lp.
Definition at line 474 of file BCP_lp_user.cpp.
References BCP_Binary_Feasible, BCP_FullTest_Feasible, BCP_Integral_Feasible, BCP_lp_par::FeasibilityTest, BCP_lp_par::IntegerTolerance, p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, test_binary(), test_full(), and test_integral().
Referenced by BCP_lp_test_feasibility(), and BB_lp::test_feasibility().
BCP_solution_generic * BCP_lp_user::test_binary | ( | const BCP_lp_result & | lpres, | |
const BCP_vec< BCP_var * > & | vars, | |||
const double | etol | |||
) | const |
Test whether all variables are 0/1.
Note that this method assumes that all variables are binary, i.e., their original lower/upper bounds are 0/1.
Definition at line 500 of file BCP_lp_user.cpp.
References BCP_solution_generic::_objective, BCP_solution_generic::add_entry(), BCP_ProvenOptimal, p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, BCP_vec< T >::size(), BCP_lp_result::termcode(), BCP_lp_result::x(), and x.
Referenced by test_feasibility().
BCP_solution_generic * BCP_lp_user::test_integral | ( | const BCP_lp_result & | lpres, | |
const BCP_vec< BCP_var * > & | vars, | |||
const double | etol | |||
) | const |
Test whether all variables are integer.
Note that this method assumes that all variables are integer.
Definition at line 537 of file BCP_lp_user.cpp.
References BCP_solution_generic::_objective, BCP_solution_generic::add_entry(), BCP_ProvenOptimal, p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, BCP_vec< T >::size(), BCP_lp_result::termcode(), BCP_lp_result::x(), and x.
Referenced by test_feasibility().
BCP_solution_generic * BCP_lp_user::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.
Definition at line 576 of file BCP_lp_user.cpp.
References BCP_solution_generic::_objective, BCP_solution_generic::add_entry(), BCP_BinaryVar, BCP_ContinuousVar, BCP_IntegerVar, BCP_ProvenOptimal, p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, BCP_vec< T >::size(), BCP_lp_result::termcode(), BCP_lp_result::x(), and x.
Referenced by test_feasibility(), BM_lp::test_feasibility_BB(), and BM_lp::test_feasibility_hybrid().
BCP_solution * BCP_lp_user::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.
Default: Return a NULL pointer
Reimplemented in BB_lp, and OS_lp.
Definition at line 633 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_main_loop().
void BCP_lp_user::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.
buf | (OUT) the buffer to pack into | |
sol | (IN) the solution to be packed |
Definition at line 644 of file BCP_lp_user.cpp.
References p, BCP_buffer::pack(), BCP_lp_prob::pack_var(), BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by send_feasible_solution().
void BCP_lp_user::pack_primal_solution | ( | BCP_buffer & | buf, | |
const BCP_lp_result & | lp_result, | |||
const BCP_vec< BCP_var * > & | vars, | |||
const BCP_vec< BCP_cut * > & | cuts | |||
) | [virtual] |
Pack the information necessary for cut generation into the buffer.
Note that the name of the method is pack_primal_solution because most likely that (or some part of that) will be needed for cut generation. However, if the user overrides the method she is free to pack anything (of course she'll have to unpack it in CG).
This information will be sent to the Cut Generator (and possibly to the Cut Pool) where the user has to unpack it. If the user uses the built-in method here, then the built-in method will be used in the Cut Generator as well.
Default: The content of the message depends on the value of the PrimalSolForCG
parameter in BCP_lp_par. By default the variables at nonzero level are packed.
buf | (OUT) the buffer to pack into | |
lp_result | (IN) the result of the most recent LP optimization | |
vars | (IN) variables currently in the formulation | |
cuts | (IN) cuts currently in the formulation |
Definition at line 666 of file BCP_lp_user.cpp.
References BCP_Msg_ForCG_PrimalFractions, BCP_Msg_ForCG_PrimalFull, BCP_Msg_ForCG_PrimalNonzeros, BCP_PrimalSolution_Fractions, BCP_PrimalSolution_Full, BCP_PrimalSolution_Nonzeros, BCP_lp_par::InfoForCG, p, BCP_buffer::pack(), BCP_lp_prob::pack_var(), BCP_lp_prob::param(), BCP_lp_result::primalTolerance(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, select_fractions(), select_nonzeros(), BCP_buffer::set_msgtag(), BCP_vec< T >::size(), BCP_lp_result::x(), and x.
Referenced by BCP_lp_pack_for_cg().
void BCP_lp_user::pack_dual_solution | ( | BCP_buffer & | buf, | |
const BCP_lp_result & | lp_result, | |||
const BCP_vec< BCP_var * > & | vars, | |||
const BCP_vec< BCP_cut * > & | cuts | |||
) | [virtual] |
Pack the information necessary for variable generation into the buffer.
Note that the name of the method is pack_dual_solution because most likely that (or some part of that) will be needed for variable generation. However, if the user overrides the method she is free to pack anything (of course she'll have to unpack it in CG).
This information will be sent to the Variable Generator (and possibly to the Variable Pool) where the user has to unpack it. If the user uses the built-in method here, then the built-in method will be used in the Variable Generator as well.
Default: The content of the message depends on the value of the DualSolForVG
parameter in BCP_lp_par. By default the full dual solution is packed.
buf | (OUT) the buffer to pack into | |
lp_result | (IN) the result of the most recent LP optimization | |
vars | (IN) variables currently in the formulation | |
cuts | (IN) cuts currently in the formulation |
Definition at line 716 of file BCP_lp_user.cpp.
References BCP_DualSolution_Full, BCP_DualSolution_Nonzeros, BCP_Msg_ForVG_DualFull, BCP_Msg_ForVG_DualNonzeros, BCP_lp_result::dualTolerance(), BCP_lp_par::InfoForVG, p, BCP_buffer::pack(), BCP_lp_prob::pack_cut(), BCP_lp_prob::param(), BCP_lp_result::pi(), pi, print(), BCP_lp_par::ReportWhenDefaultIsExecuted, select_nonzeros(), BCP_buffer::set_msgtag(), and BCP_vec< T >::size().
Referenced by BCP_lp_pack_for_vg().
void BCP_lp_user::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 | |||
) | [virtual] |
Display the result of most recent LP optimization.
This method is invoked every time an LP relaxation is optimized and the user can display (or not display) it.
Note that this method is invoked only if final_lp_solution
is true (i.e., no cuts/variables were found) and the LpVerb_FinalRelaxedSolution
parameter of BCP_lp_par is set to true (or alternatively, final_lp_solution
is false and LpVerb_RelaxedSolution
is true).
Default: display the solution if the appropriate verbosity code entry is set.
lp_result | (IN) the result of the most recent LP optimization | |
vars | (IN) variables currently in the formulation | |
final_lp_solution | (IN) whether the lp solution is final or not. |
Reimplemented in OS_lp.
Definition at line 761 of file BCP_lp_user.cpp.
References BCP_lp_par::IntegerTolerance, BCP_lp_par::LpVerb_FinalRelaxedSolution, BCP_lp_par::LpVerb_RelaxedSolution, p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, select_nonzeros(), BCP_vec< T >::size(), BCP_lp_result::x(), and x.
Referenced by BCP_lp_main_loop(), and OS_lp::display_lp_solution().
void BCP_lp_user::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.
Definition at line 795 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_restore_feasibility().
void BCP_lp_user::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] |
Convert (and possibly lift) a set of cuts into corresponding rows for the current LP relaxation.
Converting means computing for each cut the coefficients corresponding to each variable and creating BCP_row objects that can be added to the formulation.
This method has different purposes depending on the value of the last argument. If multiple expansion is not allowed then the user must generate a unique row for each cut. This unique row must always be the same for any given cut. This kind of operation is needed so that an LP relaxation can be exactly recreated.
On the other hand if multiple expansion is allowed then the user has (almost) free reign over what she returns. She can delete some of the cuts
or append new ones (e.g., lifted ones) to the end. The result of the LP relaxation and the origin of the cuts are there to help her to make a decision about what to do. For example, she might want to lift cuts coming from the Cut Generator, but not those coming from the Cut Pool. The only requirement is that when this method returns the number of cuts and rows must be the same and the i-th row must be the unique row corresponding to the i-th cut.
vars | the variables currently in the relaxation (IN) | |
cuts | the cuts to be converted (IN/OUT) | |
rows | the rows into which the cuts are converted (OUT) | |
lpres | solution to the current LP relaxation (IN) | |
origin | where the cuts come from (IN) | |
allow_multiple | whether multiple expansion, i.e., lifting, is allowed (IN) |
Reimplemented in BB_lp, BM_lp, and OS_lp.
Definition at line 810 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_add_branching_objects(), BCP_lp_generate_cuts(), load_problem(), and BCP_lp_prob::process_message().
void BCP_lp_user::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 in MCF1_lp, MCF2_lp, MCF3_lp, and OS_lp.
Definition at line 824 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_add_branching_objects(), BCP_lp_generate_vars(), BCP_price_vars(), BCP_restore_feasibility(), load_problem(), and BCP_lp_prob::process_message().
void BCP_lp_user::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] |
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 in BB_lp, and BM_lp.
Definition at line 840 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_generate_cuts(), and BCP_lp_perform_strong_branching().
void BCP_lp_user::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 in MCF1_lp, MCF2_lp, and MCF3_lp.
Definition at line 851 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_price_vars().
BCP_object_compare_result BCP_lp_user::compare_cuts | ( | const BCP_cut * | c0, | |
const BCP_cut * | c1 | |||
) | [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
.
Definition at line 863 of file BCP_lp_user.cpp.
References BCP_DifferentObjs, p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_prob::process_message().
BCP_object_compare_result BCP_lp_user::compare_vars | ( | const BCP_var * | v0, | |
const BCP_var * | v1 | |||
) | [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
.
Definition at line 871 of file BCP_lp_user.cpp.
References BCP_DifferentObjs, p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_prob::process_message().
void BCP_lp_user::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] |
Definition at line 881 of file BCP_lp_user.cpp.
References BCP_lp_prob::core, BCP_lp_par::NoCompressionAtFathom, p, BCP_lp_prob::param(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), BCP_vec< T >::unchecked_push_back(), and BCP_problem_core::varnum().
Referenced by BCP_lp_delete_cols_and_rows().
void BCP_lp_user::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 | |||
) | [virtual] |
Definition at line 903 of file BCP_lp_user.cpp.
References BCP_lp_prob::core, BCP_problem_core::cutnum(), BCP_lp_par::IneffectiveBeforeDelete, BCP_lp_node::lb_at_cutgen, BCP_lp_par::NoCompressionAtFathom, BCP_lp_prob::node, BCP_lp_result::objval(), p, BCP_lp_prob::param(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), and BCP_vec< T >::unchecked_push_back().
Referenced by BCP_lp_delete_cols_and_rows().
void BCP_lp_user::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.
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 in BB_lp.
Definition at line 930 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_fix_vars().
void BCP_lp_user::reduced_cost_fixing | ( | const double * | dj, | |
const double * | x, | |||
const double | gap, | |||
BCP_vec< BCP_var * > & | vars, | |||
int & | newly_changed | |||
) |
Reduced cost fixing.
This is not exactly a helper function, but the user might want to invoke it...
Definition at line 945 of file BCP_lp_user.cpp.
References BCP_ContinuousVar, BCP_vec< T >::begin(), BCP_lp_par::DoReducedCostFixingAtAnything, BCP_lp_par::DoReducedCostFixingAtZero, BCP_vec< T >::end(), get_param(), getOsiBabSolver(), BCP_lp_prob::lp_solver, p, BCP_vec< T >::reserve(), BCP_vec< T >::size(), and BCP_vec< T >::unchecked_push_back().
Referenced by BCP_lp_fix_vars().
BCP_branching_decision BCP_lp_user::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] |
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-one" 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.
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. | |
force_branch | indicate whether to force branching regardless of the size of the local cut/var pools |
Pseudo Shadow Price mode 0 - off 1 - use and multiply by strong info 2 - use
Reimplemented in BB_lp, MCF1_lp, MCF2_lp, MCF3_lp, BM_lp, and OS_lp.
Definition at line 1100 of file BCP_lp_user.cpp.
References BCP_Abandoned, BCP_DoBranch, BCP_DoNotBranch, BCP_DoNotBranch_Fathomed, current_level(), get_param(), BCP_lp_par::IntegerTolerance, lp, BCP_lp_prob::lp_solver, BCP_lp_par::MaxRunTime, BCP_lp_prob::node, p, BCP_lp_prob::param(), print(), BCP_vec< T >::push_back(), BCP_lp_par::ReportWhenDefaultIsExecuted, BCP_vec< T >::size(), BCP_lp_par::StrongBranchNum, BCP_lp_result::termcode(), try_to_branch(), and BCP_lp_node::vars.
Referenced by BCP_lp_select_branching_object(), and BB_lp::select_branching_candidates().
int BCP_lp_user::try_to_branch | ( | OsiBranchingInformation & | branchInfo, | |
OsiSolverInterface * | solver, | |||
OsiChooseVariable * | choose, | |||
OsiBranchingObject *& | branchObject, | |||
bool | allowVarFix | |||
) | [virtual] |
Definition at line 1018 of file BCP_lp_user.cpp.
References BCP_lp_prob::node, p, and BCP_lp_node::vars.
Referenced by select_branching_candidates(), and BM_lp::try_to_branch().
void BCP_lp_user::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.
Variables that are at least etol
away from integrality are considered and to_be_selected
of them will be picked up.
void BCP_lp_user::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.
Variables that are at least etol
away from integrality are considered and to_be_selected
of them will be picked up.
void BCP_lp_user::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
.
The indices (in the current formulation) of the variables from which candidates should be created are listed in select_pos
.
Definition at line 1249 of file BCP_lp_user.cpp.
References BCP_vec< T >::begin(), BCP_vec< T >::end(), and BCP_vec< T >::push_back().
Referenced by OS_lp::select_branching_candidates(), and BB_lp::select_branching_candidates().
BCP_branching_object_relation BCP_lp_user::compare_branching_candidates | ( | BCP_presolved_lp_brobj * | new_solved, | |
BCP_presolved_lp_brobj * | old_solved | |||
) | [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.
Definition at line 1275 of file BCP_lp_user.cpp.
References BCP_Comparison_Objval, BCP_DBL_MAX, BCP_HighestAverageObjval, BCP_HighestHighObjval, BCP_HighestLowObjval, BCP_LowestAverageObjval, BCP_LowestHighObjval, BCP_LowestLowObjval, BCP_NewPresolvedIsBetter, BCP_NewPresolvedIsBetter_BranchOnIt, BCP_OldPresolvedIsBetter, BCP_vec< T >::begin(), BCP_lp_par::BranchingObjectComparison, e, BCP_vec< T >::end(), BCP_presolved_lp_brobj::fake_objective_values(), BCP_presolved_lp_brobj::fathomable(), BCP_presolved_lp_brobj::get_lower_bounds(), BCP_lp_prob::granularity(), BCP_presolved_lp_brobj::had_numerical_problems(), BCP_vec< T >::index(), BCP_lp_prob::lp_result, BCP_lp_result::objval(), p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, and BCP_lp_prob::ub().
Referenced by BCP_lp_perform_strong_branching().
void BCP_lp_user::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_FathomChild
, 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?
Definition at line 1413 of file BCP_lp_user.cpp.
References BCP_presolved_lp_brobj::action(), BCP_DoNotDive, BCP_KeepChild, BCP_PreferChild_HighBound, BCP_PreferChild_LowBound, BCP_PreferDiveDown, BCP_PreferDiveUp, BCP_presolved_lp_brobj::candidate(), BCP_lp_branching_object::child_num, BCP_lp_par::ChildPreference, BCP_lp_node::dive, BCP_presolved_lp_brobj::lpres(), BCP_lp_prob::node, BCP_lp_result::objval(), BCP_lp_prob::over_ub(), p, BCP_lp_prob::param(), print(), and BCP_lp_par::ReportWhenDefaultIsExecuted.
Referenced by BCP_lp_select_branching_object().
void BCP_lp_user::set_user_data_for_children | ( | BCP_presolved_lp_brobj * | best, | |
const int | selected | |||
) | [virtual] |
For each child create a user data object and put it into the appropriate entry in best->user_data()
.
When this function is called the best->user_data()
vector is already the right size and is filled will 0 pointers. The second argument is usefule if strong branching was done. It is the index of the branching candidate that was selected for branching (the one that's the source of best
.
Reimplemented in BB_lp, MCF3_lp, BM_lp, and OS_lp.
Definition at line 1463 of file BCP_lp_user.cpp.
References print(), and using_deprecated_set_user_data_for_children.
Referenced by BCP_lp_select_branching_object().
void BCP_lp_user::set_user_data_for_children | ( | BCP_presolved_lp_brobj * | best | ) | [virtual] |
Deprecated version of the previos method (it does not pass the index of the selected branching candidate).
Definition at line 1485 of file BCP_lp_user.cpp.
References p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, and using_deprecated_set_user_data_for_children.
void BCP_lp_user::purge_slack_pool | ( | const BCP_vec< BCP_cut * > & | slack_pool, | |
BCP_vec< int > & | to_be_purged | |||
) | [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) |
Definition at line 1495 of file BCP_lp_user.cpp.
References BCP_DiscardSlackCutsAtNewIteration, BCP_DiscardSlackCutsAtNewNode, current_iteration(), p, BCP_lp_prob::param(), print(), BCP_lp_par::ReportWhenDefaultIsExecuted, BCP_vec< T >::reserve(), BCP_vec< T >::size(), BCP_lp_par::SlackCutDiscardingStrategy, and BCP_vec< T >::unchecked_push_back().
Referenced by BCP_lp_purge_slack_pool().
bool BCP_lp_user::using_deprecated_set_user_data_for_children [private] |
BCP_lp_prob* BCP_lp_user::p [private] |
Definition at line 82 of file BCP_lp_user.hpp.
Referenced by BM_lp::bbBranch(), compare_branching_candidates(), compare_cuts(), compare_vars(), compute_lower_bound(), current_index(), current_iteration(), current_level(), current_phase(), cuts_to_rows(), display_lp_solution(), BM_lp::do_distributed_SB(), generate_cuts_in_lp(), generate_heuristic_solution(), generate_vars_in_lp(), get_param(), get_user_data(), getLpProblemPointer(), initialize_new_search_tree_node(), load_problem(), logical_fixing(), modify_lp_parameters(), over_ub(), pack_dual_solution(), pack_feasible_solution(), pack_primal_solution(), parent(), process_id(), process_lp_result(), purge_slack_pool(), receive_message(), reduced_cost_fixing(), restore_feasibility(), select_branching_candidates(), select_cuts_to_delete(), select_vars_to_delete(), send_feasible_solution(), send_message(), set_actions_for_children(), set_param(), set_user_data_for_children(), setLpProblemPointer(), start_time(), test_binary(), test_feasibility(), test_full(), test_integral(), try_to_branch(), unpack_module_data(), upper_bound(), and vars_to_cols().
OsiBabSolver* BCP_lp_user::babSolver_ [private] |
Definition at line 83 of file BCP_lp_user.hpp.
Referenced by getOsiBabSolver(), and setOsiBabSolver().