Bcp  1.4.4
BCP_lp_branch.hpp
Go to the documentation of this file.
1 // Copyright (C) 2000, International Business Machines
2 // Corporation and others. All Rights Reserved.
3 #ifndef _BCP_LP_BRANCH_H
4 #define _BCP_LP_BRANCH_H
5 
6 // This file is fully docified.
7 
8 #include "BCP_math.hpp"
9 #include "BCP_enum_branch.hpp"
10 #include "BCP_vector.hpp"
11 #include "BCP_lp_result.hpp"
12 #include "BCP_USER.hpp"
13 #include "BCP_var.hpp"
14 #include "BCP_cut.hpp"
15 #include "BCP_matrix.hpp"
16 
17 #include "OsiBranchingObject.hpp"
18 
19 class OsiSolverInterface;
20 
21 //#############################################################################
22 
26 {
27 public:
31  inline const double* childBounds(int i) const { return i==0 ? down_:up_; }
32 };
33 
34 //-----------------------------------------------------------------------------
35 
39 {
40 public:
44 };
45 
46 //#############################################################################
47 // ASSUMPTION
48 // ----------
49 // All a branching object does are:
50 // - add cuts and/or variables
51 // - change bounds on cuts and/or variables
52 //#############################################################################
53 
54 // *THINK* : Maybe the methods should be hidden???
55 
56 // *THINK* : Maybe we should just use vectors instead of pointers to vectors?
57 // *THINK* : It'd simplify things and would not be significant extra storage
58 // *THINK* : (maybe none at all, depending pon the system operator new...)
59 
71 private:
80 public:
84  int child_num;
89 
144 
145 public:
153  explicit BCP_lp_branching_object(const int children,
154  BCP_vec<BCP_var*>* const new_vars,
155  BCP_vec<BCP_cut*>* const new_cuts,
156  const BCP_vec<int>* const fvp,
157  const BCP_vec<int>* const fcp,
158  const BCP_vec<double>* const fvb,
159  const BCP_vec<double>* const fcb,
160  const BCP_vec<int>* const ivp,
161  const BCP_vec<int>* const icp,
162  const BCP_vec<double>* const ivb,
163  const BCP_vec<double>* const icb ) :
164  child_num(children),
165  vars_to_add(0), cuts_to_add(0),
170  objval_(0), termcode_(0)
171  {
172  if ( ((fvp == 0) ^ (fvb == 0)) || ((fcp == 0) ^ (fcb == 0)) ||
173  ((ivp == 0) ^ (ivb == 0)) || ((icp == 0) ^ (icb == 0)) )
174  throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
175  if ( (fvp && (2 * children* fvp->size() != fvb->size())) ||
176  (fcp && (2 * children* fcp->size() != fcb->size())) ||
177  (ivp && (2 * children* ivp->size() != ivb->size())) ||
178  (icp && (2 * children* icp->size() != icb->size())) )
179  throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
180 
181  if (new_vars) {
182  vars_to_add = new BCP_vec<BCP_var*>(*new_vars);
183  new_vars->clear();
184  }
185  if (new_cuts) {
186  cuts_to_add = new BCP_vec<BCP_cut*>(*new_cuts);
187  new_cuts->clear();
188  }
189 
190  if (fvp) forced_var_pos = new BCP_vec<int>(*fvp);
191  if (fcp) forced_cut_pos = new BCP_vec<int>(*fcp);
192  if (fvb) forced_var_bd = new BCP_vec<double>(*fvb);
193  if (fcb) forced_cut_bd = new BCP_vec<double>(*fcb);
194 
195  if (ivp) implied_var_pos = new BCP_vec<int>(*ivp);
196  if (icp) implied_cut_pos = new BCP_vec<int>(*icp);
197  if (ivb) implied_var_bd = new BCP_vec<double>(*ivb);
198  if (icb) implied_cut_bd = new BCP_vec<double>(*icb);
199  }
201  const int* order);
204  const int* order);
205 
206  inline void set_presolve_result(const BCP_vec<double>& objval,
207  const BCP_vec<int>& termcode) {
208  objval_ = new BCP_vec<double>(objval);
209  termcode_ = new BCP_vec<int>(termcode);
210  }
211 
212  // NOTE: when the desctructor `delete's vars_to_add and cuts_to_add, it
213  // will just delete the pointers in the BCP_lp_..._sets (see the
214  // destructors of those classes). But this is intentional, because the
215  // vars/cuts will be actually deleted only later, when the unnecessery
216  // ones are deleted from the formulation.
219  delete vars_to_add; delete cuts_to_add;
220  delete forced_var_pos; delete forced_cut_pos;
221  delete forced_var_bd; delete forced_cut_bd;
222  delete implied_var_pos; delete implied_cut_pos;
223  delete implied_var_bd; delete implied_cut_bd;
224  delete objval_; delete termcode_;
225  }
232  inline int vars_affected() const {
233  return
234  (forced_var_bd ? forced_var_bd->size() / (2*child_num) : 0) +
235  (implied_var_bd ? implied_var_bd->size() / (2*child_num) : 0);
236  }
239  inline int cuts_affected() const {
240  return
241  (forced_cut_bd ? forced_cut_bd->size() / (2*child_num) : 0) +
242  (implied_cut_bd ? implied_cut_bd->size() / (2*child_num) : 0);
243  }
245  inline int vars_added() const {
246  return vars_to_add ? vars_to_add->size() : 0;
247  }
249  inline int cuts_added() const {
250  return cuts_to_add ? cuts_to_add->size() : 0;
251  }
256  inline
258  return forced_var_bd->entry(2 * forced_var_pos->size() * index);
259  }
264  inline
266  return forced_cut_bd->entry(2 * forced_cut_pos->size() * index);
267  }
272  inline
274  return implied_var_bd->entry(2 * implied_var_pos->size() * index);
275  }
280  inline
282  return implied_cut_bd->entry(2 * implied_cut_pos->size() * index);
283  }
288  // this routine reorders the positions/bounds as well so that the positions
289  // are in increasing order (the vars/cuts are already added to the problem,
290  // no need to reorder those, too)
296  void init_pos_for_added(const int added_vars_start,
297  const int added_cuts_start);
301  void apply_child_bd(OsiSolverInterface* lp, const int child_ind) const;
304  void print_branching_info(const int orig_varnum,
305  const double* x, const double * obj) const;
307 };
308 
309 //#############################################################################
310 
322 private:
331 private:
336  BCP_lp_branching_object* _candidate;
339  // what to do with each child
343  BCP_vec<BCP_child_action> _child_action;
347  BCP_vec<BCP_user_data*> _user_data;
349  BCP_vec< BCP_vec<BCP_cut*> > _new_cuts;
350  BCP_vec< BCP_vec<BCP_row*> > _new_rows;
353 public:
359  _candidate(candidate),
360  _lpres(),
361  _child_action(candidate->child_num, BCP_ReturnChild),
362  _user_data(candidate->child_num, NULL)
363  {
364  _lpres.reserve(candidate->child_num);
365  for (int i = candidate->child_num; i; --i) {
367  _new_cuts.push_back(BCP_vec<BCP_cut*>());
368  _new_rows.push_back(BCP_vec<BCP_row*>());
369  }
370  }
374  purge_ptr_vector(_lpres);
375  purge_ptr_vector(_user_data);
376  for (int i = _new_cuts.size() - 1; i >= 0; --i) {
377  purge_ptr_vector(_new_cuts[i]);
378  purge_ptr_vector(_new_rows[i]);
379  }
380  }
389  return _candidate;
390  }
392  inline const BCP_lp_branching_object* candidate() const {
393  return _candidate;
394  }
397  inline const BCP_lp_result& lpres(const int child_ind) const {
398  return *(_lpres[child_ind]);
399  }
404  return _child_action;
405  }
407  inline const BCP_vec<BCP_child_action>& action() const {
408  return _child_action;
409  }
410 
415  return _user_data;
416  }
418  inline const BCP_vec<BCP_user_data*>& user_data() const {
419  return _user_data;
420  }
421 
424  bool fathomable(const double objval_limit) const;
427  bool had_numerical_problems() const;
432  inline void initialize_lower_bound(const double val) {
433  for (int i = _candidate->child_num - 1; i >= 0; --i) {
434  _lpres[i]->fake_objective_value(val);
435  }
436  }
437  inline void keep_no_child() {
438  for (int i = _child_action.size() - 1; i >= 0; --i) {
439  _child_action[i] = BCP_ReturnChild;
440  }
441  }
442  inline bool is_pruned() const {
443  for (int i = _child_action.size() - 1; i >= 0; --i) {
444  if (_child_action[i] != BCP_FathomChild)
445  return false;
446  }
447  return true;
448  }
450  inline void get_lower_bounds(BCP_vec<double>& obj) {
451  obj.clear();
452  obj.reserve(_candidate->child_num);
453  const int num_children = _lpres.size();
454  for (int i = 0; i < num_children; ++i)
455  obj.unchecked_push_back(_lpres[i]->objval());
456  }
459  inline void set_lower_bounds(const BCP_vec<double>& obj) {
460  const int num_children = _lpres.size();
461  for (int i = 0; i < num_children; ++i)
462  _lpres[i]->fake_objective_value(obj[i]);
463  }
467  inline void get_results(OsiSolverInterface& lp, const int child_ind) {
468  _lpres[child_ind]->get_results(lp);
469  }
480  void fake_objective_values(const double itlim_objval);
481 
485  void set_objective_values(const BCP_vec<double>& obj,
486  const BCP_vec<int>& termcode,
487  const double itlim_objval);
488 
491  std::swap(_candidate, rhs._candidate);
492  _lpres.swap(rhs._lpres);
493  _child_action.swap(rhs._child_action);
494  _user_data.swap(rhs._user_data);
495  _new_cuts.swap(rhs._new_cuts);
496  _new_rows.swap(rhs._new_rows);
497  }
498  inline BCP_vec< BCP_vec<BCP_cut*> >& get_new_cuts() { return _new_cuts; }
499  inline BCP_vec< BCP_vec<BCP_row*> >& get_new_rows() { return _new_rows; }
501 };
502 
503 #endif
~BCP_lp_branching_object()
The destructor deletes each vector.
void purge_ptr_vector(BCP_vec< T * > &pvec, typename BCP_vec< T * >::iterator first, typename BCP_vec< T * >::iterator last)
This function purges the entries [first,last) from the vector of pointers pvec.
Definition: BCP_vector.hpp:266
BCP_vec< double > * forced_cut_bd
Contains the actual bounds for the cuts indexed by forced_cut_pos.
BCP_lp_integer_branching_object(const OsiIntegerBranchingObject *o)
const BCP_vec< BCP_user_data * > & user_data() const
Return a const reference to the user data vector.
int vars_added() const
Return the number of variables added in the branching.
iterator entry(const int i)
Return an iterator to the i-th entry.
Definition: BCP_vector.hpp:109
BCP_vec< int > * implied_var_pos
void get_results(OsiSolverInterface &lp, const int child_ind)
Extract the lp results from the LP solver for the child_ind-th child.
BCP_vec< double > * forced_var_bd
Contains the actual bounds for the variables indexed by forced_var_pos.
~BCP_presolved_lp_brobj()
The destructor simply deletes every member (deletes every lpres in the vector).
This child should be returned to the Tree Manager for later processing.
Currently there isn't any error handling in BCP.
Definition: BCP_error.hpp:20
const BCP_lp_result & lpres(const int child_ind) const
Return a const reference to the presolved results of the child_ind-th child.
BCP_vec< BCP_child_action > & action()
Return a reference to the actions to be taken.
void clear()
Delete every entry.
void push_back(const_reference x)
Append x to the end of the vector.
BCP_lp_sos_branching_object(const OsiSOSBranchingObject *o)
const BCP_vec< BCP_child_action > & action() const
Return a const reference to the actions to be taken.
BCP_vec< BCP_var * > * vars_to_add
Variables to be added to the formulation.
BCP_presolved_lp_brobj(BCP_lp_branching_object *candidate)
The only one way to construct a presolved branching object is to create it from a regular branching o...
bool fathomable(const double objval_limit) const
Return true if every children can be fathomed.
void swap(BCP_vec< T > &x)
Exchange the contents of the object with that of x.
This class holds the results after solving an LP relaxation.
const BCP_lp_branching_object * candidate() const
Return a const pointer to the candidate.
int cuts_added() const
Return the number of cuts added in the branching.
A presolved branching object candidate.
This child should be fathomed.
BCP_vec< BCP_user_data * > & user_data()
Return a reference to the user data vector.
void print_branching_info(const int orig_varnum, const double *x, const double *obj) const
This method prints out some information about the branching object.
int child_num
The number of children for this branching object.
BCP_vec< int > * termcode_
void swap(BCP_presolved_lp_brobj &rhs)
swap the two presolved branching object
void unchecked_push_back(const_reference x)
Append x to the end of the vector.
BCP_vec< double >::const_iterator implied_var_bd_child(const int index) const
Return a const iterator to the position in the implied variable bound changes where the new bounds fo...
void set_objective_values(const BCP_vec< double > &obj, const BCP_vec< int > &termcode, const double itlim_objval)
Set the appropriate fields of all _lpres to the given termcode and objval if the termcode is "normal"...
void reserve(const size_t n)
Reallocate the object to make space for n entries.
BCP_vec< int > * forced_cut_pos
Positions of cuts whose bounds change ("forcibly", by branching) in the children.
BCP_vec< int > * forced_var_pos
Positions of variables whose bounds change ("forcibly", by branching) in the children.
BCP_vec< BCP_cut * > * cuts_to_add
Cuts to be added to the formulation.
BCP_vec< double > * implied_var_bd
BCP_vec< int > * implied_cut_pos
BCP_vec< double > * implied_cut_bd
void initialize_lower_bound(const double val)
void set_presolve_result(const BCP_vec< double > &objval, const BCP_vec< int > &termcode)
bool had_numerical_problems() const
Return true if at least one child had numerical difficulties while presolving.
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
BCP_vec< double >::const_iterator implied_cut_bd_child(const int index) const
Return a const iterator to the position in the implied cut bound changes where the new bounds for the...
BCP_vec< BCP_vec< BCP_row * > > & get_new_rows()
This class exist only so that we can extract information from OsiIntegerBranchingObject.
void fake_objective_values(const double itlim_objval)
Examine the termination codes for the children and for those that do not have a valid lower bound fak...
int cuts_affected() const
Return the number of cuts whose bounds are affected by the branching.
const double * childBounds(int i) const
BCP_vec< double > * objval_
void get_lower_bounds(BCP_vec< double > &obj)
Fill up obj with the lower bound on each child.
int vars_affected() const
Return the number of variables whose bounds are affected by the branching.
BCP_lp_branching_object(const int children, BCP_vec< BCP_var * > *const new_vars, BCP_vec< BCP_cut * > *const new_cuts, const BCP_vec< int > *const fvp, const BCP_vec< int > *const fcp, const BCP_vec< double > *const fvb, const BCP_vec< double > *const fcb, const BCP_vec< int > *const ivp, const BCP_vec< int > *const icp, const BCP_vec< double > *const ivb, const BCP_vec< double > *const icb)
The constructor makes a copy of each vector passed to it.
void apply_child_bd(OsiSolverInterface *lp, const int child_ind) const
This method invokes the appropriate methods of lp to apply the forced and implied bound changes of th...
This class exist only so that we can extract information from OsiIntegerBranchingObject.
BCP_vec< double >::const_iterator forced_var_bd_child(const int index) const
Return a const iterator to the position in the forced variable bound changes where the new bounds for...
BCP_vec< double >::const_iterator forced_cut_bd_child(const int index) const
Return a const iterator to the position in the forced cut bound changes where the new bounds for the ...
BCP_vec< BCP_vec< BCP_cut * > > & get_new_cuts()
BCP_lp_branching_object * candidate()
Return a pointer to the candidate.
void set_lower_bounds(const BCP_vec< double > &obj)
Fill up the lower bounds on the children with the content of obj.
This class describes a generic branching object.
void init_pos_for_added(const int added_vars_start, const int added_cuts_start)
This method "cleans up" the positions and bounds.