00001
00002
00003 #ifndef _BCP_LP_BRANCH_H
00004 #define _BCP_LP_BRANCH_H
00005
00006
00007
00008 #include "BCP_math.hpp"
00009 #include "BCP_enum_branch.hpp"
00010 #include "BCP_vector.hpp"
00011 #include "BCP_lp_result.hpp"
00012 #include "BCP_USER.hpp"
00013 #include "BCP_var.hpp"
00014 #include "BCP_cut.hpp"
00015 #include "BCP_matrix.hpp"
00016
00017
00018
00019 class OsiSolverInterface;
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00045 class BCP_lp_branching_object {
00046 private:
00050 BCP_lp_branching_object(const BCP_lp_branching_object&);
00052 BCP_lp_branching_object& operator=(const BCP_lp_branching_object&);
00055 public:
00059 int child_num;
00061 BCP_vec<BCP_var*>* vars_to_add;
00063 BCP_vec<BCP_cut*>* cuts_to_add;
00064
00072 BCP_vec<int>* forced_var_pos;
00077 BCP_vec<int>* forced_cut_pos;
00082 BCP_vec<double>* forced_var_bd;
00087 BCP_vec<double>* forced_cut_bd;
00100
00101 BCP_vec<int>* implied_var_pos;
00103 BCP_vec<int>* implied_cut_pos;
00105 BCP_vec<double>* implied_var_bd;
00107 BCP_vec<double>* implied_cut_bd;
00110
00111 public:
00119 explicit BCP_lp_branching_object(const int children,
00120 BCP_vec<BCP_var*>* const new_vars,
00121 BCP_vec<BCP_cut*>* const new_cuts,
00122 const BCP_vec<int>* const fvp,
00123 const BCP_vec<int>* const fcp,
00124 const BCP_vec<double>* const fvb,
00125 const BCP_vec<double>* const fcb,
00126 const BCP_vec<int>* const ivp,
00127 const BCP_vec<int>* const icp,
00128 const BCP_vec<double>* const ivb,
00129 const BCP_vec<double>* const icb ) :
00130 child_num(children),
00131 vars_to_add(0), cuts_to_add(0),
00132 forced_var_pos(0), forced_cut_pos(0),
00133 forced_var_bd(0), forced_cut_bd(0),
00134 implied_var_pos(0), implied_cut_pos(0),
00135 implied_var_bd(0), implied_cut_bd(0)
00136 {
00137 if ( ((fvp == 0) ^ (fvb == 0)) || ((fcp == 0) ^ (fcb == 0)) ||
00138 ((ivp == 0) ^ (ivb == 0)) || ((icp == 0) ^ (icb == 0)) )
00139 throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
00140 if ( (fvp && (2 * children* fvp->size() != fvb->size())) ||
00141 (fcp && (2 * children* fcp->size() != fcb->size())) ||
00142 (ivp && (2 * children* ivp->size() != ivb->size())) ||
00143 (icp && (2 * children* icp->size() != icb->size())) )
00144 throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
00145
00146 if (new_vars) {
00147 vars_to_add = new BCP_vec<BCP_var*>(*new_vars);
00148 new_vars->clear();
00149 }
00150 if (new_cuts) {
00151 cuts_to_add = new BCP_vec<BCP_cut*>(*new_cuts);
00152 new_cuts->clear();
00153 }
00154
00155 if (fvp) forced_var_pos = new BCP_vec<int>(*fvp);
00156 if (fcp) forced_cut_pos = new BCP_vec<int>(*fcp);
00157 if (fvb) forced_var_bd = new BCP_vec<double>(*fvb);
00158 if (fcb) forced_cut_bd = new BCP_vec<double>(*fcb);
00159
00160 if (ivp) implied_var_pos = new BCP_vec<int>(*ivp);
00161 if (icp) implied_cut_pos = new BCP_vec<int>(*icp);
00162 if (ivb) implied_var_bd = new BCP_vec<double>(*ivb);
00163 if (icb) implied_cut_bd = new BCP_vec<double>(*icb);
00164 }
00165
00166
00167
00168
00169
00170
00172 ~BCP_lp_branching_object() {
00173 delete vars_to_add; delete cuts_to_add;
00174 delete forced_var_pos; delete forced_cut_pos;
00175 delete forced_var_bd; delete forced_cut_bd;
00176 delete implied_var_pos; delete implied_cut_pos;
00177 delete implied_var_bd; delete implied_cut_bd;
00178 }
00185 inline int vars_affected() const {
00186 return
00187 (forced_var_bd ? forced_var_bd->size() / (2*child_num) : 0) +
00188 (implied_var_bd ? implied_var_bd->size() / (2*child_num) : 0);
00189 }
00192 inline int cuts_affected() const {
00193 return
00194 (forced_cut_bd ? forced_cut_bd->size() / (2*child_num) : 0) +
00195 (implied_cut_bd ? implied_cut_bd->size() / (2*child_num) : 0);
00196 }
00198 inline int vars_added() const {
00199 return vars_to_add ? vars_to_add->size() : 0;
00200 }
00202 inline int cuts_added() const {
00203 return cuts_to_add ? cuts_to_add->size() : 0;
00204 }
00209 inline
00210 BCP_vec<double>::const_iterator forced_var_bd_child(const int index)const {
00211 return forced_var_bd->entry(2 * forced_var_pos->size() * index);
00212 }
00217 inline
00218 BCP_vec<double>::const_iterator forced_cut_bd_child(const int index)const {
00219 return forced_cut_bd->entry(2 * forced_cut_pos->size() * index);
00220 }
00225 inline
00226 BCP_vec<double>::const_iterator implied_var_bd_child(const int index)const{
00227 return implied_var_bd->entry(2 * implied_var_pos->size() * index);
00228 }
00233 inline
00234 BCP_vec<double>::const_iterator implied_cut_bd_child(const int index)const{
00235 return implied_cut_bd->entry(2 * implied_cut_pos->size() * index);
00236 }
00241
00242
00243
00249 void init_pos_for_added(const int added_vars_start,
00250 const int added_cuts_start);
00254 void apply_child_bd(OsiSolverInterface* lp, const int child_ind) const;
00257 void print_branching_info(const int orig_varnum,
00258 const double* x, const double * obj) const;
00260 };
00261
00262
00263
00274 class BCP_presolved_lp_brobj {
00275 private:
00279 BCP_presolved_lp_brobj(const BCP_presolved_lp_brobj&);
00281 BCP_presolved_lp_brobj& operator=(const BCP_presolved_lp_brobj&);
00284 private:
00289 BCP_lp_branching_object* _candidate;
00291 BCP_vec<BCP_lp_result*> _lpres;
00292
00296 BCP_vec<BCP_child_action> _child_action;
00300 BCP_vec<BCP_user_data*> _user_data;
00302 BCP_vec< BCP_vec<BCP_cut*> > _new_cuts;
00303 BCP_vec< BCP_vec<BCP_row*> > _new_rows;
00306 public:
00311 explicit BCP_presolved_lp_brobj(BCP_lp_branching_object* candidate) :
00312 _candidate(candidate),
00313 _lpres(),
00314 _child_action(candidate->child_num, BCP_ReturnChild),
00315 _user_data(candidate->child_num, NULL)
00316 {
00317 _lpres.reserve(candidate->child_num);
00318 for (int i = candidate->child_num; i; --i) {
00319 _lpres.unchecked_push_back(new BCP_lp_result);
00320 _new_cuts.push_back(BCP_vec<BCP_cut*>());
00321 _new_rows.push_back(BCP_vec<BCP_row*>());
00322 }
00323 }
00326 ~BCP_presolved_lp_brobj() {
00327 purge_ptr_vector(_lpres);
00328 purge_ptr_vector(_user_data);
00329 for (int i = _new_cuts.size() - 1; i >= 0; --i) {
00330 purge_ptr_vector(_new_cuts[i]);
00331 purge_ptr_vector(_new_rows[i]);
00332 }
00333 }
00341 inline BCP_lp_branching_object* candidate() {
00342 return _candidate;
00343 }
00345 inline const BCP_lp_branching_object* candidate() const {
00346 return _candidate;
00347 }
00350 inline const BCP_lp_result& lpres(const int child_ind) const {
00351 return *(_lpres[child_ind]);
00352 }
00356 inline BCP_vec<BCP_child_action>& action() {
00357 return _child_action;
00358 }
00360 inline const BCP_vec<BCP_child_action>& action() const {
00361 return _child_action;
00362 }
00363
00367 inline BCP_vec<BCP_user_data*>& user_data() {
00368 return _user_data;
00369 }
00371 inline const BCP_vec<BCP_user_data*>& user_data() const {
00372 return _user_data;
00373 }
00374
00377 const bool fathomable(const double objval_limit) const;
00380 const bool had_numerical_problems() const;
00385 inline void initialize_lower_bound(const double val) {
00386 for (int i = _candidate->child_num - 1; i >= 0; --i) {
00387 _lpres[i]->fake_objective_value(val);
00388 }
00389 }
00390 inline void keep_no_child() {
00391 for (int i = _child_action.size() - 1; i >= 0; --i) {
00392 if (_child_action[i] == BCP_KeepChild) {
00393 _child_action[i] = BCP_ReturnChild;
00394 return;
00395 }
00396 }
00397 }
00398 inline bool is_pruned() const {
00399 for (int i = _child_action.size() - 1; i >= 0; --i) {
00400 if (_child_action[i] != BCP_FathomChild)
00401 return false;
00402 }
00403 return true;
00404 }
00406 inline void get_lower_bounds(BCP_vec<double>& obj) {
00407 obj.clear();
00408 obj.reserve(_candidate->child_num);
00409 const int num_children = _lpres.size();
00410 for (int i = 0; i < num_children; ++i)
00411 obj.unchecked_push_back(_lpres[i]->objval());
00412 }
00415 inline void set_lower_bounds(const BCP_vec<double>& obj) {
00416 const int num_children = _lpres.size();
00417 for (int i = 0; i < num_children; ++i)
00418 _lpres[i]->fake_objective_value(obj[i]);
00419 }
00423 inline void get_results(OsiSolverInterface& lp, const int child_ind) {
00424 _lpres[child_ind]->get_results(lp);
00425 }
00436 void fake_objective_values(const double itlim_objval);
00437
00439 void swap(BCP_presolved_lp_brobj& rhs) {
00440 std::swap(_candidate, rhs._candidate);
00441 _lpres.swap(rhs._lpres);
00442 _child_action.swap(rhs._child_action);
00443 _user_data.swap(rhs._user_data);
00444 _new_cuts.swap(rhs._new_cuts);
00445 _new_rows.swap(rhs._new_rows);
00446 }
00447 inline BCP_vec< BCP_vec<BCP_cut*> >& get_new_cuts() { return _new_cuts; }
00448 inline BCP_vec< BCP_vec<BCP_row*> >& get_new_rows() { return _new_rows; }
00450 };
00451
00452 #endif