Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members

BCP_lp_user Class Reference

#include <BCP_lp_user.hpp>

List of all members.

Public Member Functions

virtual OsiSolverInterface * initialize_solver_interface ()
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)
virtual void modify_lp_parameters (OsiSolverInterface *lp, bool in_strong_branching)
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)
virtual BCP_solution * generate_heuristic_solution (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const BCP_vec< BCP_cut * > &cuts)
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)
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)
virtual BCP_branching_object_relation compare_branching_candidates (BCP_presolved_lp_brobj *new_solved, BCP_presolved_lp_brobj *old_solved)
virtual void set_actions_for_children (BCP_presolved_lp_brobj *best)
virtual void set_user_data_for_children (BCP_presolved_lp_brobj *best, const int selected)
virtual void set_user_data_for_children (BCP_presolved_lp_brobj *best)
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 DBL_MAX).

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.

BCP_user_data * get_user_data ()
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
virtual ~BCP_lp_user ()
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
void select_zeros (const double *first, const double *last, const double etol, BCP_vec< int > &zeros) const
void select_positives (const double *first, const double *last, const double etol, BCP_vec< int > &positives) const
void select_fractions (const double *first, const double *last, const double etol, BCP_vec< int > &fractions) const
Packing and unpacking methods
virtual void unpack_module_data (BCP_buffer &buf)
Methods that pack/unpack warmstart, var_algo and cut_algo objects.
The packing methods take an object and a buffer as an argument and the user is supposed to pack the object into the buffer.

The argument of the unpacking methods is just the buffer. The user is supposed to return a pointer to the unpacked object.

virtual void pack_warmstart (const BCP_warmstart *ws, BCP_buffer &buf)
virtual BCP_warmstart * unpack_warmstart (BCP_buffer &buf)
virtual void pack_var_algo (const BCP_var_algo *var, BCP_buffer &buf)
virtual BCP_var_algo * unpack_var_algo (BCP_buffer &buf)
virtual void pack_cut_algo (const BCP_cut_algo *cut, BCP_buffer &buf)
virtual BCP_cut_algo * unpack_cut_algo (BCP_buffer &buf)
virtual void pack_user_data (const BCP_user_data *ud, BCP_buffer &buf)
virtual BCP_user_data * unpack_user_data (BCP_buffer &buf)
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)
Helper functions for <code>test_feasibility</code>. 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 _vars member of the solution.

BCP_solution_generic * test_binary (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
BCP_solution_generic * test_integral (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
BCP_solution_generic * test_full (const BCP_lp_result &lpres, const BCP_vec< BCP_var * > &vars, const double etol) const
Packing of solutions
virtual void pack_feasible_solution (BCP_buffer &buf, const BCP_solution *sol)
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)
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)
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)
Methods related to indexed variables. These methods must be
overridden if and only if BCP is supposed to track the indexed variables yet to be priced out, i.e., if the parameter MaintainIndexedVarPricingList is set to true.

virtual int next_indexed_var (int prev_index)
virtual BCP_var_indexed * create_indexed_var (int index, const BCP_vec< BCP_cut * > &cuts, BCP_col &col)
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)
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)
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)
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)
virtual BCP_object_compare_result compare_cuts (const BCP_cut *c0, const BCP_cut *c1)
virtual BCP_object_compare_result compare_vars (const BCP_var *v0, const BCP_var *v1)
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)
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)
Helper functions for select_branching_candidates()
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)
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)
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)
Purging the slack pool
virtual void purge_slack_pool (const BCP_vec< BCP_cut * > &slack_pool, BCP_vec< int > &to_be_purged)

Private Attributes

bool using_deprecated_set_user_data_for_children
BCP_lp_prob * p

Detailed Description

The BCP_lp_user class is the base class from which the user can derive a problem specific class to be used in the LP process.

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 72 of file BCP_lp_user.hpp.

Constructor & Destructor Documentation

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 138 of file BCP_lp_user.hpp. 

00138 {}

Member Function Documentation

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 1081 of file BCP_lp_user.cpp.

References BCP_vec< T >::begin(), BCP_vec< T >::end(), and BCP_vec< T >::push_back().

Referenced by branch_close_to_half(), and branch_close_to_one(). 

01085 {
01086   BCP_vec<int>::const_iterator spi;
01087   BCP_vec<double> vbd(4, 0.0);
01088   BCP_vec<int> vpos(1, 0);
01089 
01090   for (spi = select_pos.begin(); spi != select_pos.end(); ++spi) {
01091     const int pos = *spi;
01092     vpos[0] = pos;
01093     vbd[0] = vars[pos]->lb();
01094     vbd[1] = floor(x[pos]);
01095     vbd[2] = ceil(x[pos]);
01096     vbd[3] = vars[pos]->ub();
01097     cans.push_back
01098       (new  BCP_lp_branching_object(2,
01099                                     0, 0, /* vars/cuts_to_add */
01100                                     &vpos, 0, &vbd, 0, /* forced parts */
01101                                     0, 0, 0, 0 /* implied parts */));
01102   }
01103 }

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.

Definition at line 906 of file BCP_lp_user.cpp.

References append_branching_vars(), BCP_vec< T >::begin(), BCP_vec< T >::clear(), BCP_vec< T >::end(), BCP_vec< T >::entry(), BCP_vec< T >::erase(), BCP_vec< T >::index(), BCP_vec< T >::insert(), BCP_lp_prob::lp_solver, BCP_vec< T >::pop_back(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), BCP_vec< T >::swap(), and BCP_lp_result::x().

Referenced by select_branching_candidates(). 

00911 {
00912   // order the variables based on their distance from a MIP feasible value
00913   const double etol5 = .5 - etol;
00914   BCP_vec<BCP_var*>::const_iterator vi = vars.begin();
00915   const double * x = lpres.x();
00916   const double * xi = x;
00917   const double * lastxi = x + vars.size();
00918 
00919   // choose 5 times the required ones (ordered primarily by closeness to half
00920   // and secondarily by cost)
00921   int to_select = 5*to_be_selected;
00922 
00923   BCP_vec<int> select_pos(to_select + 1, -1);
00924   BCP_vec<double> select_val(to_select + 1, 1.0);
00925   BCP_vec<double> select_cost(to_select + 1, -1e20);
00926 
00927   const double* objcoeff = p->lp_solver->getObjCoefficients();
00928 
00929   double val;
00930   int pos, i, k;
00931 
00932   for (pos = 0, k = 0; k < to_select && xi != lastxi; ++pos, ++xi, ++vi){
00933     // check if the next var violates MIP feasibility
00934     if ((*vi)->var_type() == BCP_ContinuousVar)
00935       continue;
00936     val = CoinAbs(*xi - .5 - floor(*xi));
00937     if (val > etol5)
00938       continue;
00939     // if not, insert it into the list
00940     const double cost = CoinAbs(objcoeff[pos]);
00941     for (i = k - 1; i >= 0; --i) {
00942       if (select_val[i] < val ||
00943           (select_val[i] == val && select_cost[i] >= cost))
00944         break;
00945       select_pos[i+1] = select_pos[i];
00946       select_val[i+1] = select_val[i];
00947       select_cost[i+1] = select_cost[i];
00948     }
00949     select_pos[i+1] = pos;
00950     select_val[i+1] = val;
00951     select_cost[i+1] = cost;
00952     ++k;
00953   }
00954 
00955   for ( ; xi != lastxi; ++pos, ++xi, ++vi) {
00956     // check if the next var violates MIP feasibility
00957     if ((*vi)->var_type() == BCP_ContinuousVar)
00958       continue;
00959     val = CoinAbs(*xi - .5 - floor(*xi));
00960     if (val > etol5)
00961       continue;
00962     // if not, insert it into the list
00963     const double cost = objcoeff[pos];
00964     for (i = to_select - 1; i >= 0; --i) {
00965       if (select_val[i] < val ||
00966           (select_val[i] == val && select_cost[i] >= cost))
00967         break;
00968       select_pos[i+1] = select_pos[i];
00969       select_val[i+1] = select_val[i];
00970       select_cost[i+1] = select_cost[i];
00971     }
00972     if (i != to_select - 1) {
00973       select_pos[i+1] = pos;
00974       select_val[i+1] = val;
00975       select_cost[i+1] = cost;
00976     }
00977   }
00978 
00979   k = select_val.index(std::upper_bound(select_val.begin(),
00980                                         select_val.entry(k),
00981                                         2 * select_val[to_be_selected - 1]));
00982 
00983   select_pos.erase(select_pos.entry(k), select_pos.end());
00984   select_cost.erase(select_cost.entry(k), select_cost.end());
00985 
00986   // now reorder these and keep only as many as required. this time order by
00987   // cost alone.
00988   if (k > to_be_selected) {
00989     BCP_vec<double>::iterator di;
00990     BCP_vec<int> new_pos;
00991     new_pos.reserve(to_be_selected);
00992     BCP_vec<double>& new_cost = select_val;
00993     new_cost.clear();
00994     for (pos = 0; pos < to_be_selected; ++pos) {
00995       const double val = select_cost[pos];
00996       // insert the next into the list
00997       di = std::upper_bound(new_cost.begin(), new_cost.end(), val);
00998       new_pos.insert(new_pos.entry(new_cost.index(di)), select_pos[pos]);
00999       new_cost.insert(di, val);
01000     }
01001     for ( ; pos < k; ++pos) {
01002       const double val = select_cost[pos];
01003       // insert the next into the list
01004       di = std::upper_bound(new_cost.begin(), new_cost.end(), val);
01005       if (di != new_cost.end()) {
01006         new_cost.pop_back();
01007         new_pos.pop_back();
01008         new_pos.insert(new_pos.entry(new_cost.index(di)), select_pos[pos]);
01009         new_cost.insert(di, val);
01010       }
01011     }
01012     select_pos.swap(new_pos);
01013   }
01014 
01015   append_branching_vars(lpres.x(), vars, select_pos, cans);
01016 }

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.

Definition at line 1019 of file BCP_lp_user.cpp.

References append_branching_vars(), BCP_vec< T >::begin(), BCP_vec< T >::end(), BCP_vec< T >::entry(), BCP_vec< T >::index(), BCP_vec< T >::insert(), BCP_vec< T >::pop_back(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), and BCP_lp_result::x().

Referenced by select_branching_candidates(). 

01024 {
01025   // order the variables based on their distance from a MIP feasible value
01026   BCP_vec<BCP_var*>::const_iterator vi = vars.begin();
01027   const double * x = lpres.x();
01028   const double * xi = x;
01029   const double * lastxi = x + vars.size();
01030 
01031   BCP_vec<int> select_pos;
01032   select_pos.reserve(to_be_selected);
01033   BCP_vec<double> select_val;
01034   select_val.reserve(to_be_selected);
01035   BCP_vec<double>::iterator spv;
01036 
01037   double val;
01038   int pos;
01039 
01040   for (pos = 0;
01041        select_pos.size() < static_cast<const size_t>(to_be_selected) &&
01042          xi != lastxi;
01043        ++pos, ++xi, ++vi) {
01044     // check if the next var violates MIP feasibility
01045     if ((*vi)->var_type() == BCP_ContinuousVar)
01046       continue;
01047     if (*xi < etol)
01048        continue;
01049     val = 1 - *xi;
01050     if (val < etol)
01051       continue;
01052     // if not, insert it into the list
01053     spv = std::upper_bound(select_val.begin(), select_val.end(), val);
01054     select_pos.insert(select_pos.entry(select_val.index(spv)), pos);
01055     select_val.insert(spv, val);
01056   }
01057 
01058   for ( ; xi != lastxi; ++pos, ++xi, ++vi) {
01059     // check if the next var violates MIP feasibility
01060     if ((*vi)->var_type() == BCP_ContinuousVar)
01061       continue;
01062     if (*xi < etol)
01063        continue;
01064     val = 1 - *xi;
01065     if (val < etol)
01066       continue;
01067     // if not, insert it into the list
01068     spv = std::upper_bound(select_val.begin(), select_val.end(), val);
01069     if (spv != select_val.end()) {
01070       select_pos.pop_back();
01071       select_pos.insert(select_pos.entry(select_val.index(spv)), pos);
01072       select_val.pop_back();
01073       select_val.insert(spv, val);
01074     }
01075   }
01076 
01077   append_branching_vars(lpres.x(), vars, select_pos, cans);
01078 }

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 1107 of file BCP_lp_user.cpp.

References BCP_vec< T >::begin(), 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(), BCP_lp_prob::param(), and BCP_lp_prob::ub(). 

01109 {
01110   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
01111     printf(" LP: Default compare_presolved_branching_objects() executed.\n");
01112   }
01113 
01114   // change the objvals according to the termcodes (in order to be able to
01115   // make decisions based on objval, no matter what the termcode is).
01116   new_presolved->fake_objective_values(p->lp_result->objval());
01117 
01118    // If using this branching object we can fathom all children, then choose
01119    // this object
01120   if (new_presolved->fathomable(p->ub() - p->granularity()))
01121     return(BCP_NewPresolvedIsBetter_BranchOnIt);
01122 
01123    // If this is the first, keep it
01124   if (! old_presolved)
01125     return(BCP_NewPresolvedIsBetter);
01126 
01127    // If something had gone wrong with at least one descendant in the new then
01128    // we prefer to keep the old.
01129   if (new_presolved->had_numerical_problems())
01130     return(BCP_OldPresolvedIsBetter);
01131 
01132    // OK, so all descendants finished just fine. Do whatever the parameter says
01133 
01134   if (p->param(BCP_lp_par::BranchingObjectComparison) & BCP_Comparison_Objval){
01135     const double objetol = 1e-7;
01136       
01137     BCP_vec<double> new_obj;
01138     new_presolved->get_lower_bounds(new_obj);
01139     std::sort(new_obj.begin(), new_obj.end());
01140     const int new_not_fathomed =
01141       new_obj.index(std::lower_bound(new_obj.begin(), new_obj.end(),
01142                                      DBL_MAX / 4));
01143 
01144     BCP_vec<double> old_obj;
01145     old_presolved->get_lower_bounds(old_obj);
01146     std::sort(old_obj.begin(), old_obj.end());
01147     const int old_not_fathomed =
01148       old_obj.index(std::lower_bound(old_obj.begin(), old_obj.end(),
01149                                      DBL_MAX / 4));
01150 
01151     if (new_not_fathomed < old_not_fathomed)
01152       return BCP_NewPresolvedIsBetter;
01153 
01154     if (new_not_fathomed > old_not_fathomed)
01155       return BCP_OldPresolvedIsBetter;
01156 
01157     BCP_vec<double>::const_iterator new_first = new_obj.begin();
01158     BCP_vec<double>::const_iterator new_last = new_obj.end();
01159     BCP_vec<double>::const_iterator old_first = old_obj.begin();
01160     BCP_vec<double>::const_iterator old_last = old_obj.end();
01161    
01162     switch(p->param(BCP_lp_par::BranchingObjectComparison)){
01163     case BCP_LowestAverageObjval:
01164     case BCP_HighestAverageObjval:
01165       {
01166         double newavg = 0;
01167         for ( ; new_first != new_last; ++new_first) {
01168           if (*new_first < DBL_MAX / 4)
01169             newavg += *new_first;
01170         }
01171         newavg /= new_not_fathomed;
01172         double oldavg = 0;
01173         for ( ; old_first != old_last; ++old_first) {
01174           if (*old_first < DBL_MAX / 4)
01175             oldavg += *old_first;
01176         }
01177         oldavg /= old_not_fathomed;
01178         const bool high = (p->param(BCP_lp_par::BranchingObjectComparison)
01179                            == BCP_HighestAverageObjval);
01180         return (high && newavg > oldavg) || (!high && newavg < oldavg) ?
01181           BCP_NewPresolvedIsBetter : BCP_OldPresolvedIsBetter;
01182       }
01183 
01184     case BCP_LowestLowObjval:
01185       for ( ; new_first != new_last && old_first != old_last;
01186             ++new_first, ++old_first) {
01187         if (*new_first < *old_first - objetol)
01188           return BCP_NewPresolvedIsBetter;
01189         if (*new_first > *old_first + objetol)
01190           return BCP_OldPresolvedIsBetter;
01191       }
01192       return old_first == old_last ?
01193         BCP_OldPresolvedIsBetter : BCP_NewPresolvedIsBetter;
01194 
01195     case BCP_HighestLowObjval:
01196       for ( ; new_first != new_last && old_first != old_last;
01197             ++new_first, ++old_first) {
01198         if (*new_first > *old_first + objetol)
01199           return BCP_NewPresolvedIsBetter;
01200         if (*new_first < *old_first - objetol)
01201           return BCP_OldPresolvedIsBetter;
01202       }
01203       return old_first == old_last ?
01204         BCP_OldPresolvedIsBetter : BCP_NewPresolvedIsBetter;
01205 
01206     case BCP_LowestHighObjval:
01207       while (new_first != new_last && old_first != old_last) {
01208         --new_last;
01209         --old_last;
01210         if (*new_last < *old_last - objetol)
01211           return BCP_NewPresolvedIsBetter;
01212         if (*new_last > *old_last + objetol)
01213           return BCP_OldPresolvedIsBetter;
01214       }
01215       return old_first == old_last ?
01216         BCP_OldPresolvedIsBetter : BCP_NewPresolvedIsBetter;
01217 
01218     case BCP_HighestHighObjval:
01219       while (new_first != new_last && old_first != old_last) {
01220         --new_last;
01221         --old_last;
01222         if (*new_last > *old_last + objetol)
01223           return BCP_NewPresolvedIsBetter;
01224         if (*new_last < *old_last - objetol)
01225           return BCP_OldPresolvedIsBetter;
01226       }
01227       return old_first == old_last ?
01228         BCP_OldPresolvedIsBetter : BCP_NewPresolvedIsBetter;
01229     default:
01230       throw BCP_fatal_error("Unknown branching object comparison rule.\n");
01231     }
01232   }
01233 
01234   // shouldn't ever get here
01235   throw BCP_fatal_error("No branching object comparison rule is chosen.\n");
01236 
01237   // fake return
01238   return BCP_NewPresolvedIsBetter;
01239 }

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 704 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00705 {
00706   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00707     printf(" LP: Default compare_cuts() executed.\n");
00708   }
00709    return BCP_DifferentObjs;
00710 }

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 713 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00714 {
00715   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00716     printf(" LP: Default compare_vars() executed.\n");
00717   }
00718    return BCP_DifferentObjs;
00719 }

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.

Definition at line 245 of file BCP_lp_user.cpp.

References BCP_lp_node::colgen, BCP_lp_prob::node, BCP_lp_result::objval(), BCP_lp_result::termcode(), and BCP_lp_prob::ub(). 

00249 {
00250    // If columns are to be generated then we can't say anything, just return
00251    // the current lower bound
00252    if (p->node->colgen != BCP_DoNotGenerateColumns_Fathom)
00253       return old_lower_bound;
00254 
00255    // Otherwise we got the examine the termination code and the objective
00256    // value of the LP solution
00257    const int tc = lpres.termcode();
00258    if (tc & BCP_ProvenOptimal)
00259       return lpres.objval();
00260 
00261    // The limit (the upper bound) on the dual objective is proven to be
00262    // reached, but the objval might not reflect this! (the LP solver may not
00263    // make the last iteration that pushes objval over the limit). So we return
00264    // a high value ourselves.
00265    if (tc & BCP_DualObjLimReached)
00266       return p->ub() + 1e-5;
00267 
00268    // We can't say anything in any other case
00269    // (BCP_ProvenPrimalInf | BCP_ProvenDualInf | BCP_PrimalObjLimReached |
00270    //  BCP_TimeLimit | BCP_Abandoned), not to mention that some of these are
00271    //  impossible. Just return the current bound.
00272    return old_lower_bound;
00273 }

BCP_var_indexed * BCP_lp_user::create_indexed_var (  int  index,
const BCP_vec< BCP_cut * > &  cuts,
BCP_col &  col
)  [virtual]
 

Create the variable corresponding to the given index. The routine should return a pointer to a newly created indexed variable and return the corresponding column in col.
Default: throw an exception.

Definition at line 618 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00621 {
00622   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00623     printf(" LP: Default create_indexed_var() executed.\n");
00624   }
00625    throw BCP_fatal_error("create_indexed_var() missing.\n");
00626 }

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.

Parameters:
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)
Default: throw an exception (if this method is invoked then the user must have generated cuts and BCP has no way to know how to convert them).

Definition at line 647 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00654 {
00655   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00656     printf(" LP: Default cuts_to_rows() executed.\n");
00657   }
00658   throw BCP_fatal_error("cuts_to_rows() missing.\n");
00659 }

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.

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

Definition at line 573 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(), select_nonzeros(), BCP_vec< T >::size(), and BCP_lp_result::x(). 

00577 {
00578   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00579     printf(" LP: Default display_lp_solution() executed.\n");
00580   }
00581 
00582   if (final_lp_solution) {
00583     if (! p->param(BCP_lp_par::LpVerb_FinalRelaxedSolution))
00584       return;
00585     printf("  LP : Displaying LP solution (FinalRelaxedSolution) :\n");
00586   } else {
00587     if (! p->param(BCP_lp_par::LpVerb_RelaxedSolution))
00588       return;
00589     printf("  LP : Displaying LP solution (RelaxedSolution) :\n");
00590   }
00591 
00592   const double ietol = p->param(BCP_lp_par::IntegerTolerance);
00593 
00594   printf("  LP : Displaying solution :\n");
00595   BCP_vec<int> coll;
00596   const double * x = lpres.x();
00597   select_nonzeros(x, x+vars.size(), ietol, coll);
00598   const int size = coll.size();
00599   for (int i = 0; i < size; ++i) {
00600     const int ind = coll[i];
00601     vars[ind]->display(x[ind]);
00602   }
00603 }

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.

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)
new_cuts the vector of generated cuts (OUT)
new_rows the correspontding rows(OUT)

Definition at line 679 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00684 {
00685   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00686     printf(" LP: Default generate_cuts_in_lp() executed.\n");
00687   }
00688 }

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

Definition at line 442 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00445 {
00446   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00447     printf(" LP: Default generate_heuristic_solution() executed.\n");
00448   }
00449   return NULL;
00450 }

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.

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)

Definition at line 691 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00697 {
00698   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00699     printf(" LP: Default generate_vars_in_lp() executed.\n");
00700   }
00701 }

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 28 of file BCP_lp_user.cpp.

References BCP_lp_prob::node, and BCP_lp_node::user_data. 

00028 { return p->node->user_data; }

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.

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

Definition at line 217 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00225 {
00226   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00227     printf(" LP: Default initialize_new_search_tree_node() executed.\n");
00228   }
00229 }

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.

Definition at line 208 of file BCP_lp_user.cpp. 

00209 {
00210    throw BCP_fatal_error("\
00211 BCP_lp_user::initialize_solver_interface() invoked but not overridden!\n");
00212    return 0;
00213 }

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.

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.

Definition at line 773 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00781 {
00782   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00783     printf(" LP: Default logical_fixing() executed.\n");
00784   }
00785 }

void BCP_lp_user::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.

Definition at line 234 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00236 {
00237   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00238     printf(" LP: Default prepare_for_optimization() executed.\n");
00239   }
00240 }

int BCP_lp_user::next_indexed_var (  int  prev_index  )  [virtual]
 

Return the index of the indexed variable following prev_index. Return -1 if there are no more indexed variables. If prev_index is -1 then return the index of the first indexed variable.
Default: Return -1.

Definition at line 609 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00610 {
00611   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00612     printf(" LP: Default next_indexed_var() executed.\n");
00613   }
00614    return -1;
00615 }

void BCP_lp_user::pack_cut_algo (  const BCP_cut_algo *  cut,
BCP_buffer &  buf
)  [virtual]
 

Pack an algorithmic cut

Definition at line 175 of file BCP_lp_user.cpp. 

00176 {
00177   throw BCP_fatal_error("\
00178 BCP_lp_user::pack_cut_algo() invoked but not overridden!\n");
00179 }

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.

Parameters:
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 527 of file BCP_lp_user.cpp.

References BCP_vec< T >::begin(), BCP_lp_result::dualTolerance(), BCP_vec< T >::end(), BCP_buffer::pack(), BCP_lp_prob::pack_cut(), BCP_lp_prob::param(), BCP_lp_result::pi(), BCP_vec< T >::reserve(), select_nonzeros(), BCP_buffer::set_msgtag(), BCP_vec< T >::size(), and BCP_vec< T >::unchecked_push_back(). 

00531 {
00532   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00533     printf(" LP: Default pack_for_vg() executed.\n");
00534   }
00535 
00536   BCP_vec<int> coll;
00537 
00538   const double detol = lpres.dualTolerance();
00539   const double * pi = lpres.pi();
00540   const int cutnum = cuts.size();
00541 
00542   switch (p->param(BCP_lp_par::InfoForVG)){
00543   case BCP_DualSolution_Nonzeros:
00544     select_nonzeros(pi, pi+cutnum, detol, coll);
00545     buf.set_msgtag(BCP_Msg_ForVG_DualNonzeros);
00546     break;
00547   case BCP_DualSolution_Full:
00548     coll.reserve(cutnum);
00549     for (int i = 0; i < cutnum; ++i) {
00550       coll.unchecked_push_back(i);
00551     }
00552     buf.set_msgtag(BCP_Msg_ForVG_DualFull);
00553     break;
00554   default:
00555     throw BCP_fatal_error("Incorrect msgtag in pack_lp_solution() !\n");
00556   }
00557 
00558   const int size = coll.size();
00559   buf.pack(size);
00560   if (size > 0){
00561     BCP_vec<int>::const_iterator pos = coll.begin() - 1;
00562     const BCP_vec<int>::const_iterator last_pos = coll.end();
00563     while (++pos != last_pos) {
00564       buf.pack(pi[*pos]);
00565       p->pack_cut(BCP_ProcessType_Any, *cuts[*pos]);
00566     }
00567   }
00568 }

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.

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

Definition at line 454 of file BCP_lp_user.cpp.

References BCP_solution_generic::_values, BCP_solution_generic::_vars, BCP_buffer::pack(), BCP_lp_prob::pack_var(), BCP_lp_prob::param(), and BCP_vec< T >::size(). 

00455 {
00456   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00457     printf(" LP: Default pack_feasible_solution() executed.\n");
00458   }
00459 
00460   const BCP_solution_generic* gensol =
00461     dynamic_cast<const BCP_solution_generic*>(sol);
00462   const BCP_vec<BCP_var*> solvars = gensol->_vars;
00463   const BCP_vec<double> values = gensol->_values;
00464   const int size = solvars.size();
00465   buf.pack(size);
00466   for (int i = 0; i < size; ++i) {
00467     buf.pack(values[i]);
00468     p->pack_var(BCP_ProcessType_Any, *solvars[i]);
00469   }
00470 }

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.

Parameters:
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 476 of file BCP_lp_user.cpp.

References BCP_vec< T >::begin(), BCP_vec< T >::end(), BCP_buffer::pack(), BCP_lp_prob::pack_var(), BCP_lp_prob::param(), BCP_lp_result::primalTolerance(), BCP_vec< T >::reserve(), select_fractions(), select_nonzeros(), BCP_buffer::set_msgtag(), BCP_vec< T >::size(), BCP_vec< T >::unchecked_push_back(), and BCP_lp_result::x(). 

00480 {
00481   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00482     printf(" LP: Default pack_for_cg() executed.\n");
00483   }
00484 
00485   BCP_vec<int> coll;
00486 
00487   const double petol = lpres.primalTolerance();
00488   const double * x = lpres.x();
00489   const int varnum = vars.size();
00490 
00491   switch (p->param(BCP_lp_par::InfoForCG)){
00492   case BCP_PrimalSolution_Nonzeros:
00493     select_nonzeros(x, x + varnum, petol, coll);
00494     buf.set_msgtag(BCP_Msg_ForCG_PrimalNonzeros);
00495     break;
00496   case BCP_PrimalSolution_Fractions:
00497     select_fractions(x, x+varnum, petol, coll);
00498     buf.set_msgtag(BCP_Msg_ForCG_PrimalFractions);
00499     break;
00500   case BCP_PrimalSolution_Full:
00501     coll.reserve(varnum);
00502     for (int i = 0; i < varnum; ++i) {
00503       coll.unchecked_push_back(i);
00504     }
00505     buf.set_msgtag(BCP_Msg_ForCG_PrimalFull);
00506     break;
00507   default:
00508     throw BCP_fatal_error("Incorrect msgtag in pack_for_cg() !\n");
00509   }
00510 
00511   const int size = coll.size();
00512   buf.pack(size);
00513   if (size > 0){
00514     BCP_vec<int>::const_iterator pos = coll.begin() - 1;
00515     const BCP_vec<int>::const_iterator last_pos = coll.end();
00516     while (++pos != last_pos) {
00517       buf.pack(x[*pos]);
00518       p->pack_var(BCP_ProcessType_Any, *vars[*pos]);
00519     }
00520   }
00521 }

void BCP_lp_user::pack_user_data (  const BCP_user_data *  ud,
BCP_buffer &  buf
)  [virtual]
 

Pack an user data

Definition at line 191 of file BCP_lp_user.cpp. 

00192 {
00193   throw BCP_fatal_error("\
00194 BCP_lp_user::pack_user_data() invoked but not overridden!\n");
00195 }

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

Pack an algorithmic variable

Definition at line 159 of file BCP_lp_user.cpp. 

00160 {
00161   throw BCP_fatal_error("\
00162 BCP_lp_user::pack_var_algo() invoked but not overridden!\n");
00163 }

void BCP_lp_user::pack_warmstart (  const BCP_warmstart *  ws,
BCP_buffer &  buf
)  [virtual]
 

Pack warmstarting information

Definition at line 137 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00138 {
00139   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00140     printf(" LP: Default BCP_lp_user::pack_warmstart() executed.\n");
00141   }
00142   BCP_pack_warmstart(ws, buf);
00143 }

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

Parameters:
slack_pool the pool of slacks. (IN)
to_be_purged the indices of the cuts to be purged. (OUT)

Definition at line 1320 of file BCP_lp_user.cpp.

References current_iteration(), BCP_lp_prob::param(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), and BCP_vec< T >::unchecked_push_back(). 

01322 {
01323   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
01324     printf(" LP: Default purge_slack_pool() executed.\n");
01325   }
01326 
01327   switch (p->param(BCP_lp_par::SlackCutDiscardingStrategy)) {
01328   case BCP_DiscardSlackCutsAtNewNode:
01329     if (current_iteration() != 1)
01330       break;
01331   case BCP_DiscardSlackCutsAtNewIteration:
01332     {
01333       const int size = slack_pool.size();
01334       if (size > 0) {
01335         to_be_purged.reserve(size);
01336         for (int i = 0; i < size; ++i)
01337           to_be_purged.unchecked_push_back(i);
01338       }
01339     }
01340     break;
01341   }
01342 }

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 789 of file BCP_lp_user.cpp.

References BCP_vec< T >::begin(), BCP_vec< T >::end(), BCP_var::is_fixed(), BCP_var::lb(), BCP_lp_prob::lp_solver, BCP_vec< T >::reserve(), BCP_var::set_lb(), BCP_var::set_ub(), BCP_vec< T >::size(), BCP_var::ub(), BCP_vec< T >::unchecked_push_back(), and BCP_var::var_type(). 

00792 {
00793   newly_changed = 0;
00794   const bool atZero = get_param(BCP_lp_par::DoReducedCostFixingAtZero);
00795   const bool atAny = get_param(BCP_lp_par::DoReducedCostFixingAtAnything);
00796 
00797   if (! atZero && ! atAny)
00798      return;
00799 
00800   double petol = 0.0;
00801   p->lp_solver->getDblParam(OsiPrimalTolerance, petol);
00802 
00803   // If the gap is negative that means that we are above the limit, so
00804   // don't do anything.
00805   if (gap < 0)
00806     return;
00807 
00808   const int varnum = vars.size();
00809   BCP_vec<int> changed_indices;
00810   changed_indices.reserve(varnum);
00811   BCP_vec<double> changed_bounds;
00812   changed_bounds.reserve(2 * varnum);
00813 
00814   // Note that when this function is called, we must have a dual
00815   // feasible dual solution. Therefore we can use the lagrangean
00816   // relaxation to fix variables.
00817 
00818   // *FIXME* : If we knew that there are integral vars only, then
00819   // we could leave out the test for BCP_ContinuousVar...
00820   for (int i = 0; i < varnum; ++i) {
00821     BCP_var* var = vars[i];
00822     if (! var->is_fixed() && var->var_type() != BCP_ContinuousVar){
00823       if (dj[i] > 0) {
00824         const double lb = var->lb();
00825         const double new_ub = lb + floor(gap / dj[i]);
00826         if (new_ub < var->ub() && (atAny || CoinAbs(x[i])<petol) ) {
00827           vars[i]->set_ub(new_ub);
00828           changed_indices.unchecked_push_back(i);
00829           changed_bounds.unchecked_push_back(lb);
00830           changed_bounds.unchecked_push_back(new_ub);
00831         }
00832       } else if (dj[i] < 0) {
00833         const double ub = var->ub();
00834         const double new_lb = ub - floor(gap / (-dj[i]));
00835         if (new_lb > var->lb() && (atAny || CoinAbs(x[i])<petol) ) {
00836           vars[i]->set_lb(new_lb);
00837           changed_indices.unchecked_push_back(i);
00838           changed_bounds.unchecked_push_back(new_lb);
00839           changed_bounds.unchecked_push_back(ub);
00840         }
00841       }
00842     }
00843   }
00844   newly_changed = changed_indices.size();
00845   if (newly_changed > 0) {
00846     p->lp_solver->setColSetBounds(changed_indices.begin(),
00847                                   changed_indices.end(),
00848                                   changed_bounds.begin());
00849   }
00850 }

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.

If the MaintainIndexedVarPricingList is set to true then BCP will take care of going through the indexed variables to see if any will restore feasibility and the user has to check only the algorithmic variables. Otherwise the user has to check all variables here.

Definition at line 631 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00637 {
00638   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00639     printf(" LP: Default restore_feasibility() executed.\n");
00640   }
00641 }

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

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

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

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

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

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

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

Definition at line 856 of file BCP_lp_user.cpp.

References BCP_vec< T >::begin(), branch_close_to_half(), branch_close_to_one(), BCP_vec< T >::end(), BCP_lp_prob::param(), BCP_vec< T >::reserve(), BCP_vec< T >::size(), and BCP_vec< T >::unchecked_push_back(). 

00862 {
00863   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00864     printf(" LP: Default select_branching_candidates() executed.\n");
00865   }
00866 
00867   // *THINK* : this branching object selection is very primitive
00868   // *THINK* : should check for tail-off, could check for branching cuts, etc.
00869   if (local_var_pool.size() > 0 || local_cut_pool.size() > 0)
00870     return BCP_DoNotBranch;
00871 
00872   if (p->param(BCP_lp_par::StrongBranch_CloseToHalfNum) > 0)
00873     branch_close_to_half(lpres, vars,
00874                          p->param(BCP_lp_par::StrongBranch_CloseToHalfNum),
00875                          p->param(BCP_lp_par::IntegerTolerance),
00876                          cans);
00877   if (p->param(BCP_lp_par::StrongBranch_CloseToOneNum) > 0)
00878     branch_close_to_one(lpres, vars,
00879                         p->param(BCP_lp_par::StrongBranch_CloseToOneNum),
00880                         p->param(BCP_lp_par::IntegerTolerance),
00881                         cans);
00882   // Get rid of duplicates in cans
00883   BCP_vec<int> brvars;
00884   brvars.reserve(cans.size());
00885   for (size_t i = 0; i < cans.size(); ) {
00886      const int brvar = (*cans[i]->forced_var_pos)[0];
00887      if (std::find(brvars.begin(), brvars.end(), brvar) == brvars.end()) {
00888         brvars.unchecked_push_back(brvar);
00889         ++i;
00890      } else {
00891         std::swap(cans[i], cans.back());
00892         cans.pop_back();
00893      }
00894   }
00895   
00896   if (cans.size() == 0) {
00897     throw BCP_fatal_error("\
00898  LP : No var/cut in pool but couldn't select branching object.\n");
00899   }
00900   return BCP_DoBranch;
00901 }

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 113 of file BCP_lp_user.cpp.

References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back().

Referenced by pack_primal_solution(). 

00115                                                              {
00116   fractions.reserve(last - first);
00117   BCP_vec<double>::const_iterator current = first;
00118   for ( ; current != last; ++current)
00119     if (*current - floor(*current) >etol && ceil(*current) - *current >etol)
00120       fractions.unchecked_push_back(current - first);
00121 }

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 83 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(). 

00085                                                            {
00086   nonzeros.reserve(last - first);
00087   BCP_vec<double>::const_iterator current = first;
00088   for ( ; current != last; ++current)
00089     if (CoinAbs(*current) > etol) nonzeros.unchecked_push_back(current - first);
00090 }

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 103 of file BCP_lp_user.cpp.

References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back(). 

00105                                                              {
00106   positives.reserve(last - first);
00107   BCP_vec<double>::const_iterator current = first;
00108   for ( ; current != last; ++current)
00109     if (*current > etol) positives.unchecked_push_back(current - first);
00110 }

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 93 of file BCP_lp_user.cpp.

References BCP_vec< T >::reserve(), and BCP_vec< T >::unchecked_push_back(). 

00095                                                      {
00096   zeros.reserve(last - first);
00097   BCP_vec<double>::const_iterator current = first;
00098   for ( ; current != last; ++current)
00099     if (CoinAbs(*current) <= etol) zeros.unchecked_push_back(current - first);
00100 }

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_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?

Definition at line 1243 of file BCP_lp_user.cpp.

References BCP_presolved_lp_brobj::action(), BCP_presolved_lp_brobj::candidate(), BCP_lp_branching_object::child_num, BCP_lp_node::dive, BCP_presolved_lp_brobj::lpres(), BCP_lp_prob::node, BCP_lp_result::objval(), BCP_lp_prob::over_ub(), and BCP_lp_prob::param(). 

01244 {
01245   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
01246     printf(" LP: Default set_actions_for_children() executed.\n");
01247   }
01248 
01249   // by default every action is set to BCP_ReturnChild
01250   if (p->node->dive == BCP_DoNotDive)
01251     return;
01252    
01253   BCP_vec<BCP_child_action>& action = best->action();
01254   int i, ind;
01255 
01256   switch (p->param(BCP_lp_par::ChildPreference)){
01257   case BCP_PreferChild_LowBound:
01258     // NOTE: if the lowest objval child is fathomed then everything is
01259     for (ind = 0, i = best->candidate()->child_num - 1; i > 0; --i){
01260       if (best->lpres(i).objval() < best->lpres(ind).objval())
01261         ind = i;
01262     }
01263     break;
01264 
01265   case BCP_PreferChild_HighBound:
01266     // NOTE: this selects the highest objval child NOT FATHOMED, thus if
01267     // the highest objval child is fathomed then everything is
01268     for (ind = 0, i = best->candidate()->child_num - 1; i > 0; --i) {
01269       if (! p->over_ub(best->lpres(i).objval()) &&
01270           best->lpres(i).objval() < best->lpres(ind).objval())
01271         ind = i;
01272     }
01273     break;
01274   default:
01275     // *THINK* : fractional branching
01276     throw BCP_fatal_error("LP : Unrecognized child preference.\n");
01277   }
01278   // mark the ind-th to be kept (if not over ub)
01279   if (! p->over_ub(best->lpres(ind).objval()))
01280     action[ind] = BCP_KeepChild;
01281 }

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 1309 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

01310 {
01311   using_deprecated_set_user_data_for_children = false;
01312   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
01313     printf(" LP: Default set_user_data_for_children() executed.\n");
01314   }
01315 }

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.

Definition at line 1286 of file BCP_lp_user.cpp. 

01288 {
01289   using_deprecated_set_user_data_for_children = true;
01290   set_user_data_for_children(best);
01291   if (using_deprecated_set_user_data_for_children) {
01292      printf("\
01293 *** WARNING *** WARNING *** WARNING *** WARNING *** WARNING *** WARNING ***\n\
01294 You have overridden\n\
01295   BCP_lp_user::set_user_data_for_children(BCP_presolved_lp_brobj* best)\n\
01296 which is a deprecated virtual function. Please override\n\
01297   BCP_lp_user::set_user_data_for_children(BCP_presolved_lp_brobj* best,\n\
01298                                           const int selected)\n\
01299 instead. The old version will go away, your code will still compile, but it\n\
01300 will not do what you intend it to be doing.\n\
01301 *** WARNING *** WARNING *** WARNING *** WARNING *** WARNING *** WARNING ***\n"\
01302             );
01303   }
01304 }

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.

Definition at line 305 of file BCP_lp_user.cpp.

References BCP_solution_generic::_objective, BCP_solution_generic::add_entry(), BCP_lp_prob::param(), BCP_vec< T >::size(), BCP_lp_result::termcode(), and BCP_lp_result::x().

Referenced by test_feasibility(). 

00308 {
00309   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00310     printf(" LP: Default test_binary() executed.\n");
00311   }
00312   // Do anything only if the termination code is sensible
00313   const int tc = lpres.termcode();
00314   if (! (tc & BCP_ProvenOptimal))
00315      return 0;
00316 
00317   const double * x = lpres.x();
00318   const int varnum = vars.size();
00319   int i;
00320 
00321   for (i = 0 ; i < varnum; ++i) {
00322     const double xi = x[i];
00323     if ( (xi > etol && xi < 1 - etol) || (xi < -etol) || (xi > 1 + etol) )
00324       return(NULL);
00325   }
00326 
00327   // This solution does not own the pointers to the variables
00328   BCP_solution_generic* sol = new BCP_solution_generic(false); 
00329   double obj = 0;
00330   for (i = 0 ; i < varnum; ++i) {
00331     if (x[i] > 1 - etol) {
00332       sol->add_entry(vars[i], 1.0);
00333       obj += vars[i]->obj();
00334     }
00335   }
00336   sol->_objective = obj;
00337   return sol;
00338 }

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.

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

Definition at line 278 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(), test_binary(), test_full(), and test_integral(). 

00281 {
00282   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00283     printf(" LP: Default test_feasibility() executed.\n");
00284   }
00285 
00286   const double etol = p->param(BCP_lp_par::IntegerTolerance);
00287   BCP_feasibility_test test =
00288     static_cast<BCP_feasibility_test>(p->param(BCP_lp_par::FeasibilityTest));
00289 
00290   BCP_solution* sol = NULL;
00291   switch (test){
00292   case BCP_Binary_Feasible:   sol = test_binary(lpres, vars, etol); break;
00293   case BCP_Integral_Feasible: sol = test_integral(lpres, vars, etol); break;
00294   case BCP_FullTest_Feasible: sol = test_full(lpres, vars, etol); break;
00295   default:
00296     throw BCP_fatal_error("LP: unknown test_feasibility() rule.\n");
00297   }
00298 
00299   return sol;
00300 }

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 all variables are within their lower and upper bounds and that the integer variables are really integer.

Definition at line 383 of file BCP_lp_user.cpp.

References BCP_solution_generic::_objective, BCP_solution_generic::add_entry(), BCP_var::lb(), BCP_lp_prob::param(), BCP_vec< T >::size(), BCP_lp_result::termcode(), BCP_var::ub(), BCP_var::var_type(), and BCP_lp_result::x().

Referenced by test_feasibility(). 

00386 {
00387   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00388     printf(" LP: Default test_full() executed.\n");
00389   }
00390   // Do anything only if the termination code is sensible
00391   const int tc = lpres.termcode();
00392   if (! (tc & BCP_ProvenOptimal))
00393      return 0;
00394 
00395   const double * x = lpres.x();
00396   const int varnum = vars.size();
00397   const double etol1 = 1 - etol;
00398   int i;
00399   register double val;
00400 
00401   for (i = 0 ; i < varnum; ++i) {
00402     val = x[i];
00403     const BCP_var* vari = vars[i];
00404     if (val < vari->lb() - etol || val > vari->ub() + etol)
00405       return(NULL);
00406     switch (vari->var_type()){
00407     case BCP_BinaryVar:
00408       if (val > etol && val < etol1)
00409         return(NULL);
00410       break;
00411     case BCP_IntegerVar:
00412       val = val - floor(val);
00413       if (val > etol && val < etol1)
00414         return(NULL);
00415       break;
00416     case BCP_ContinuousVar:
00417       break;
00418     }
00419   }
00420 
00421   // This solution does not own the pointers to the variables
00422   BCP_solution_generic* sol = new BCP_solution_generic(false);
00423   double obj = 0;
00424   for (i = 0 ; i < varnum; ++i) {
00425     val = x[i];
00426     // round the integer vars
00427     if (vars[i]->var_type() == BCP_BinaryVar ||
00428         vars[i]->var_type() == BCP_IntegerVar)
00429       val = floor(x[i] + 0.5);
00430     if (val < -etol || val > etol) {
00431       sol->add_entry(vars[i], val);
00432       obj += val * vars[i]->obj();
00433     }
00434   }
00435   sol->_objective = obj;
00436   return sol;
00437 }

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 and are within their lower and upper bounds.

Definition at line 341 of file BCP_lp_user.cpp.

References BCP_solution_generic::_objective, BCP_solution_generic::add_entry(), BCP_var::lb(), BCP_lp_prob::param(), BCP_vec< T >::size(), BCP_lp_result::termcode(), BCP_var::ub(), and BCP_lp_result::x().

Referenced by test_feasibility(). 

00344 {
00345   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00346     printf(" LP: Default test_integral() executed.\n");
00347   }
00348   // Do anything only if the termination code is sensible
00349   const int tc = lpres.termcode();
00350   if (! (tc & BCP_ProvenOptimal))
00351      return 0;
00352 
00353   const double * x = lpres.x();
00354   const int varnum = vars.size();
00355   int i;
00356   register double val;
00357 
00358   for (i = 0 ; i < varnum; ++i) {
00359     val = x[i];
00360     const BCP_var* vari = vars[i];
00361     if (val < vari->lb() - etol || val > vari->ub() + etol)
00362       return(NULL);
00363     val = val - floor(val);
00364     if (val > etol && val < 1 - etol)
00365       return(NULL);
00366   }
00367   
00368   // This solution does not own the pointers to the variables
00369   BCP_solution_generic* sol = new BCP_solution_generic(false);
00370   double obj = 0;
00371   for (i = 0 ; i < varnum; ++i) {
00372     val = floor(x[i] + 0.5);
00373     if (val < -etol || val > etol) { // could test != 0.0
00374       sol->add_entry(vars[i], val);
00375       obj += val * vars[i]->obj();
00376     }
00377   }
00378   sol->_objective = obj;
00379   return sol;
00380 }

BCP_cut_algo * BCP_lp_user::unpack_cut_algo (  BCP_buffer &  buf  )  [virtual]
 

Unpack an algorithmic cut

Definition at line 183 of file BCP_lp_user.cpp. 

00184 {
00185   throw BCP_fatal_error("\
00186 BCP_lp_user::unpack_cut_algo() invoked but not overridden!\n");
00187 }

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.

Definition at line 127 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00128 {
00129   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00130     printf(" LP: Default unpack_module_data() executed.\n");
00131   }
00132 }

BCP_user_data * BCP_lp_user::unpack_user_data (  BCP_buffer &  buf  )  [virtual]
 

Unpack an user data

Definition at line 199 of file BCP_lp_user.cpp. 

00200 {
00201   throw BCP_fatal_error("\
00202 BCP_lp_user::unpack_user_data() invoked but not overridden!\n");
00203 }

BCP_var_algo * BCP_lp_user::unpack_var_algo (  BCP_buffer &  buf  )  [virtual]
 

Unpack an algorithmic variable

Definition at line 167 of file BCP_lp_user.cpp. 

00168 {
00169   throw BCP_fatal_error("\
00170 BCP_lp_user::unpack_var_algo() invoked but not overridden!\n");
00171 }

BCP_warmstart * BCP_lp_user::unpack_warmstart (  BCP_buffer &  buf  )  [virtual]
 

Unpack warmstarting information

Definition at line 148 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00149 {
00150   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00151     printf(" LP: Default BCP_lp_user::unpack_warmstart() executed.\n");
00152   }
00153   return BCP_unpack_warmstart(buf);
00154 }

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

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

Definition at line 662 of file BCP_lp_user.cpp.

References BCP_lp_prob::param(). 

00669 {
00670   if (p->param(BCP_lp_par::ReportWhenDefaultIsExecuted)) {
00671     printf(" LP: Default vars_to_cols() executed.\n");
00672   }
00673   throw BCP_fatal_error("vars_to_cols() missing.\n");
00674 }

The documentation for this class was generated from the following files:
Generated on Wed Dec 3 14:32:40 2003 for BCP by doxygen 1.3.5