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 
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::set_presolve_result
void set_presolve_result(const BCP_vec< double > &objval, const BCP_vec< int > &termcode)
Definition: BCP_lp_branch.hpp:206
BCP_presolved_lp_brobj::action
const BCP_vec< BCP_child_action > & action() const
Return a const reference to the actions to be taken.
Definition: BCP_lp_branch.hpp:407
BCP_vector.hpp
BCP_presolved_lp_brobj::~BCP_presolved_lp_brobj
~BCP_presolved_lp_brobj()
The destructor simply deletes every member (deletes every lpres in the vector).
Definition: BCP_lp_branch.hpp:373
BCP_lp_sos_branching_object
This class exist only so that we can extract information from OsiIntegerBranchingObject.
Definition: BCP_lp_branch.hpp:39
OsiBranchingObject.hpp
BCP_presolved_lp_brobj::initialize_lower_bound
void initialize_lower_bound(const double val)
Definition: BCP_lp_branch.hpp:432
BCP_FathomChild
@ BCP_FathomChild
This child should be fathomed.
Definition: BCP_enum_branch.hpp:131
BCP_vec::clear
void clear()
Delete every entry.
Definition: BCP_vector_general.hpp:318
purge_ptr_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_presolved_lp_brobj::fake_objective_values
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...
OsiIntegerBranchingObject::down_
double down_[2]
OsiIntegerBranchingObject::up_
double up_[2]
BCP_matrix.hpp
BCP_lp_branching_object::forced_var_bd
BCP_vec< double > * forced_var_bd
Contains the actual bounds for the variables indexed by forced_var_pos.
Definition: BCP_lp_branch.hpp:107
BCP_vec< BCP_var * >
BCP_vec::unchecked_push_back
void unchecked_push_back(const_reference x)
Append x to the end of the vector.
Definition: BCP_vector_general.hpp:308
BCP_lp_branching_object::BCP_lp_branching_object
BCP_lp_branching_object(const OsiSolverInterface *osi, const BCP_lp_sos_branching_object &o, const int *order)
BCP_lp_branching_object::forced_cut_bd
BCP_vec< double > * forced_cut_bd
Contains the actual bounds for the cuts indexed by forced_cut_pos.
Definition: BCP_lp_branch.hpp:112
BCP_vec::size
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
BCP_cut.hpp
BCP_presolved_lp_brobj::get_lower_bounds
void get_lower_bounds(BCP_vec< double > &obj)
Fill up obj with the lower bound on each child.
Definition: BCP_lp_branch.hpp:450
BCP_lp_branching_object::implied_var_pos
BCP_vec< int > * implied_var_pos
Definition: BCP_lp_branch.hpp:126
BCP_presolved_lp_brobj::candidate
const BCP_lp_branching_object * candidate() const
Return a const pointer to the candidate.
Definition: BCP_lp_branch.hpp:392
BCP_lp_branching_object::forced_cut_pos
BCP_vec< int > * forced_cut_pos
Positions of cuts whose bounds change ("forcibly", by branching) in the children.
Definition: BCP_lp_branch.hpp:102
BCP_lp_branching_object::cuts_added
int cuts_added() const
Return the number of cuts added in the branching.
Definition: BCP_lp_branch.hpp:249
BCP_lp_branching_object
This class describes a generic branching object.
Definition: BCP_lp_branch.hpp:70
BCP_lp_result
This class holds the results after solving an LP relaxation.
Definition: BCP_lp_result.hpp:39
BCP_vec::swap
void swap(BCP_vec< T > &x)
Exchange the contents of the object with that of x.
Definition: BCP_vector_general.hpp:124
BCP_math.hpp
BCP_presolved_lp_brobj::get_new_rows
BCP_vec< BCP_vec< BCP_row * > > & get_new_rows()
Definition: BCP_lp_branch.hpp:499
BCP_vec::push_back
void push_back(const_reference x)
Append x to the end of the vector.
Definition: BCP_vector_general.hpp:300
BCP_lp_branching_object::vars_to_add
BCP_vec< BCP_var * > * vars_to_add
Variables to be added to the formulation.
Definition: BCP_lp_branch.hpp:86
BCP_lp_branching_object::child_num
int child_num
The number of children for this branching object.
Definition: BCP_lp_branch.hpp:84
BCP_lp_branching_object::termcode_
BCP_vec< int > * termcode_
Definition: BCP_lp_branch.hpp:140
BCP_lp_branching_object::implied_var_bd_child
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...
Definition: BCP_lp_branch.hpp:273
BCP_presolved_lp_brobj::set_lower_bounds
void set_lower_bounds(const BCP_vec< double > &obj)
Fill up the lower bounds on the children with the content of obj.
Definition: BCP_lp_branch.hpp:459
BCP_lp_branching_object::implied_cut_bd_child
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...
Definition: BCP_lp_branch.hpp:281
BCP_presolved_lp_brobj::set_objective_values
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"...
BCP_lp_branching_object::BCP_lp_branching_object
BCP_lp_branching_object(const BCP_lp_integer_branching_object &o, const int *order)
OsiSolverInterface
BCP_presolved_lp_brobj
A presolved branching object candidate.
Definition: BCP_lp_branch.hpp:321
BCP_presolved_lp_brobj::user_data
BCP_vec< BCP_user_data * > & user_data()
Return a reference to the user data vector.
Definition: BCP_lp_branch.hpp:414
BCP_var.hpp
BCP_lp_sos_branching_object::~BCP_lp_sos_branching_object
~BCP_lp_sos_branching_object()
Definition: BCP_lp_branch.hpp:43
BCP_lp_branching_object::vars_affected
int vars_affected() const
Return the number of variables whose bounds are affected by the branching.
Definition: BCP_lp_branch.hpp:232
BCP_lp_branching_object::forced_var_pos
BCP_vec< int > * forced_var_pos
Positions of variables whose bounds change ("forcibly", by branching) in the children.
Definition: BCP_lp_branch.hpp:97
BCP_vec::reserve
void reserve(const size_t n)
Reallocate the object to make space for n entries.
Definition: BCP_vector_general.hpp:112
BCP_lp_branching_object::implied_cut_pos
BCP_vec< int > * implied_cut_pos
Definition: BCP_lp_branch.hpp:128
BCP_presolved_lp_brobj::lpres
const BCP_lp_result & lpres(const int child_ind) const
Return a const reference to the presolved results of the child_ind-th child.
Definition: BCP_lp_branch.hpp:397
BCP_lp_integer_branching_object::~BCP_lp_integer_branching_object
~BCP_lp_integer_branching_object()
Definition: BCP_lp_branch.hpp:30
BCP_presolved_lp_brobj::fathomable
bool fathomable(const double objval_limit) const
Return true if every children can be fathomed.
BCP_ReturnChild
@ BCP_ReturnChild
This child should be returned to the Tree Manager for later processing.
Definition: BCP_enum_branch.hpp:134
BCP_presolved_lp_brobj::get_new_cuts
BCP_vec< BCP_vec< BCP_cut * > > & get_new_cuts()
Definition: BCP_lp_branch.hpp:498
BCP_lp_branching_object::BCP_lp_branching_object
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.
Definition: BCP_lp_branch.hpp:153
BCP_lp_branching_object::print_branching_info
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.
BCP_lp_branching_object::~BCP_lp_branching_object
~BCP_lp_branching_object()
The destructor deletes each vector.
Definition: BCP_lp_branch.hpp:218
BCP_lp_branching_object::forced_var_bd_child
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...
Definition: BCP_lp_branch.hpp:257
BCP_lp_branching_object::cuts_to_add
BCP_vec< BCP_cut * > * cuts_to_add
Cuts to be added to the formulation.
Definition: BCP_lp_branch.hpp:88
BCP_lp_result.hpp
BCP_lp_branching_object::implied_cut_bd
BCP_vec< double > * implied_cut_bd
Definition: BCP_lp_branch.hpp:132
BCP_presolved_lp_brobj::keep_no_child
void keep_no_child()
Definition: BCP_lp_branch.hpp:437
OsiSOSBranchingObject
BCP_presolved_lp_brobj::user_data
const BCP_vec< BCP_user_data * > & user_data() const
Return a const reference to the user data vector.
Definition: BCP_lp_branch.hpp:418
BCP_lp_branching_object::init_pos_for_added
void init_pos_for_added(const int added_vars_start, const int added_cuts_start)
This method "cleans up" the positions and bounds.
BCP_lp_branching_object::objval_
BCP_vec< double > * objval_
Definition: BCP_lp_branch.hpp:139
BCP_lp_branching_object::forced_cut_bd_child
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 ...
Definition: BCP_lp_branch.hpp:265
BCP_lp_sos_branching_object::BCP_lp_sos_branching_object
BCP_lp_sos_branching_object(const OsiSOSBranchingObject *o)
Definition: BCP_lp_branch.hpp:41
BCP_USER.hpp
BCP_vec::entry
iterator entry(const int i)
Return an iterator to the i-th entry.
Definition: BCP_vector.hpp:109
BCP_lp_integer_branching_object::childBounds
const double * childBounds(int i) const
Definition: BCP_lp_branch.hpp:31
BCP_presolved_lp_brobj::action
BCP_vec< BCP_child_action > & action()
Return a reference to the actions to be taken.
Definition: BCP_lp_branch.hpp:403
BCP_presolved_lp_brobj::had_numerical_problems
bool had_numerical_problems() const
Return true if at least one child had numerical difficulties while presolving.
BCP_lp_branching_object::vars_added
int vars_added() const
Return the number of variables added in the branching.
Definition: BCP_lp_branch.hpp:245
BCP_lp_branching_object::implied_var_bd
BCP_vec< double > * implied_var_bd
Definition: BCP_lp_branch.hpp:130
OsiIntegerBranchingObject
BCP_enum_branch.hpp
BCP_lp_integer_branching_object
This class exist only so that we can extract information from OsiIntegerBranchingObject.
Definition: BCP_lp_branch.hpp:26
BCP_lp_branching_object::cuts_affected
int cuts_affected() const
Return the number of cuts whose bounds are affected by the branching.
Definition: BCP_lp_branch.hpp:239
BCP_lp_branching_object::apply_child_bd
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...
BCP_presolved_lp_brobj::get_results
void get_results(OsiSolverInterface &lp, const int child_ind)
Extract the lp results from the LP solver for the child_ind-th child.
Definition: BCP_lp_branch.hpp:467
BCP_presolved_lp_brobj::BCP_presolved_lp_brobj
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...
Definition: BCP_lp_branch.hpp:358
BCP_fatal_error
Currently there isn't any error handling in BCP.
Definition: BCP_error.hpp:20
BCP_presolved_lp_brobj::candidate
BCP_lp_branching_object * candidate()
Return a pointer to the candidate.
Definition: BCP_lp_branch.hpp:388
BCP_presolved_lp_brobj::swap
void swap(BCP_presolved_lp_brobj &rhs)
swap the two presolved branching object
Definition: BCP_lp_branch.hpp:490
BCP_lp_integer_branching_object::BCP_lp_integer_branching_object
BCP_lp_integer_branching_object(const OsiIntegerBranchingObject *o)
Definition: BCP_lp_branch.hpp:28
BCP_presolved_lp_brobj::is_pruned
bool is_pruned() const
Definition: BCP_lp_branch.hpp:442