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 #include "OsiBranchingObject.hpp"
00018
00019 class OsiSolverInterface;
00020
00021
00022
00025 class BCP_lp_integer_branching_object : public OsiIntegerBranchingObject
00026 {
00027 public:
00028 BCP_lp_integer_branching_object(const OsiIntegerBranchingObject* o) :
00029 OsiIntegerBranchingObject(*o) {}
00030 ~BCP_lp_integer_branching_object() {}
00031 inline const double* childBounds(int i) const { return i==0 ? down_:up_; }
00032 };
00033
00034
00035
00038 class BCP_lp_sos_branching_object : public OsiSOSBranchingObject
00039 {
00040 public:
00041 BCP_lp_sos_branching_object(const OsiSOSBranchingObject* o) :
00042 OsiSOSBranchingObject(*o) {}
00043 ~BCP_lp_sos_branching_object() {}
00044 };
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00070 class BCP_lp_branching_object {
00071 private:
00075 BCP_lp_branching_object(const BCP_lp_branching_object&);
00077 BCP_lp_branching_object& operator=(const BCP_lp_branching_object&);
00080 public:
00084 int child_num;
00086 BCP_vec<BCP_var*>* vars_to_add;
00088 BCP_vec<BCP_cut*>* cuts_to_add;
00089
00097 BCP_vec<int>* forced_var_pos;
00102 BCP_vec<int>* forced_cut_pos;
00107 BCP_vec<double>* forced_var_bd;
00112 BCP_vec<double>* forced_cut_bd;
00125
00126 BCP_vec<int>* implied_var_pos;
00128 BCP_vec<int>* implied_cut_pos;
00130 BCP_vec<double>* implied_var_bd;
00132 BCP_vec<double>* implied_cut_bd;
00139 BCP_vec<double>* objval_;
00140 BCP_vec<int>* termcode_;
00144
00145 public:
00153 explicit BCP_lp_branching_object(const int children,
00154 BCP_vec<BCP_var*>* const new_vars,
00155 BCP_vec<BCP_cut*>* const new_cuts,
00156 const BCP_vec<int>* const fvp,
00157 const BCP_vec<int>* const fcp,
00158 const BCP_vec<double>* const fvb,
00159 const BCP_vec<double>* const fcb,
00160 const BCP_vec<int>* const ivp,
00161 const BCP_vec<int>* const icp,
00162 const BCP_vec<double>* const ivb,
00163 const BCP_vec<double>* const icb ) :
00164 child_num(children),
00165 vars_to_add(0), cuts_to_add(0),
00166 forced_var_pos(0), forced_cut_pos(0),
00167 forced_var_bd(0), forced_cut_bd(0),
00168 implied_var_pos(0), implied_cut_pos(0),
00169 implied_var_bd(0), implied_cut_bd(0),
00170 objval_(0), termcode_(0)
00171 {
00172 if ( ((fvp == 0) ^ (fvb == 0)) || ((fcp == 0) ^ (fcb == 0)) ||
00173 ((ivp == 0) ^ (ivb == 0)) || ((icp == 0) ^ (icb == 0)) )
00174 throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
00175 if ( (fvp && (2 * children* fvp->size() != fvb->size())) ||
00176 (fcp && (2 * children* fcp->size() != fcb->size())) ||
00177 (ivp && (2 * children* ivp->size() != ivb->size())) ||
00178 (icp && (2 * children* icp->size() != icb->size())) )
00179 throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
00180
00181 if (new_vars) {
00182 vars_to_add = new BCP_vec<BCP_var*>(*new_vars);
00183 new_vars->clear();
00184 }
00185 if (new_cuts) {
00186 cuts_to_add = new BCP_vec<BCP_cut*>(*new_cuts);
00187 new_cuts->clear();
00188 }
00189
00190 if (fvp) forced_var_pos = new BCP_vec<int>(*fvp);
00191 if (fcp) forced_cut_pos = new BCP_vec<int>(*fcp);
00192 if (fvb) forced_var_bd = new BCP_vec<double>(*fvb);
00193 if (fcb) forced_cut_bd = new BCP_vec<double>(*fcb);
00194
00195 if (ivp) implied_var_pos = new BCP_vec<int>(*ivp);
00196 if (icp) implied_cut_pos = new BCP_vec<int>(*icp);
00197 if (ivb) implied_var_bd = new BCP_vec<double>(*ivb);
00198 if (icb) implied_cut_bd = new BCP_vec<double>(*icb);
00199 }
00200 BCP_lp_branching_object(const BCP_lp_integer_branching_object& o,
00201 const int* order);
00202 BCP_lp_branching_object(const OsiSolverInterface* osi,
00203 const BCP_lp_sos_branching_object& o,
00204 const int* order);
00205
00206 inline void set_presolve_result(const BCP_vec<double>& objval,
00207 const BCP_vec<int>& termcode) {
00208 objval_ = new BCP_vec<double>(objval);
00209 termcode_ = new BCP_vec<int>(termcode);
00210 }
00211
00212
00213
00214
00215
00216
00218 ~BCP_lp_branching_object() {
00219 delete vars_to_add; delete cuts_to_add;
00220 delete forced_var_pos; delete forced_cut_pos;
00221 delete forced_var_bd; delete forced_cut_bd;
00222 delete implied_var_pos; delete implied_cut_pos;
00223 delete implied_var_bd; delete implied_cut_bd;
00224 delete objval_; delete termcode_;
00225 }
00232 inline int vars_affected() const {
00233 return
00234 (forced_var_bd ? forced_var_bd->size() / (2*child_num) : 0) +
00235 (implied_var_bd ? implied_var_bd->size() / (2*child_num) : 0);
00236 }
00239 inline int cuts_affected() const {
00240 return
00241 (forced_cut_bd ? forced_cut_bd->size() / (2*child_num) : 0) +
00242 (implied_cut_bd ? implied_cut_bd->size() / (2*child_num) : 0);
00243 }
00245 inline int vars_added() const {
00246 return vars_to_add ? vars_to_add->size() : 0;
00247 }
00249 inline int cuts_added() const {
00250 return cuts_to_add ? cuts_to_add->size() : 0;
00251 }
00256 inline
00257 BCP_vec<double>::const_iterator forced_var_bd_child(const int index)const {
00258 return forced_var_bd->entry(2 * forced_var_pos->size() * index);
00259 }
00264 inline
00265 BCP_vec<double>::const_iterator forced_cut_bd_child(const int index)const {
00266 return forced_cut_bd->entry(2 * forced_cut_pos->size() * index);
00267 }
00272 inline
00273 BCP_vec<double>::const_iterator implied_var_bd_child(const int index)const{
00274 return implied_var_bd->entry(2 * implied_var_pos->size() * index);
00275 }
00280 inline
00281 BCP_vec<double>::const_iterator implied_cut_bd_child(const int index)const{
00282 return implied_cut_bd->entry(2 * implied_cut_pos->size() * index);
00283 }
00288
00289
00290
00296 void init_pos_for_added(const int added_vars_start,
00297 const int added_cuts_start);
00301 void apply_child_bd(OsiSolverInterface* lp, const int child_ind) const;
00304 void print_branching_info(const int orig_varnum,
00305 const double* x, const double * obj) const;
00307 };
00308
00309
00310
00321 class BCP_presolved_lp_brobj {
00322 private:
00326 BCP_presolved_lp_brobj(const BCP_presolved_lp_brobj&);
00328 BCP_presolved_lp_brobj& operator=(const BCP_presolved_lp_brobj&);
00331 private:
00336 BCP_lp_branching_object* _candidate;
00338 BCP_vec<BCP_lp_result*> _lpres;
00339
00343 BCP_vec<BCP_child_action> _child_action;
00347 BCP_vec<BCP_user_data*> _user_data;
00349 BCP_vec< BCP_vec<BCP_cut*> > _new_cuts;
00350 BCP_vec< BCP_vec<BCP_row*> > _new_rows;
00353 public:
00358 explicit BCP_presolved_lp_brobj(BCP_lp_branching_object* candidate) :
00359 _candidate(candidate),
00360 _lpres(),
00361 _child_action(candidate->child_num, BCP_ReturnChild),
00362 _user_data(candidate->child_num, NULL)
00363 {
00364 _lpres.reserve(candidate->child_num);
00365 for (int i = candidate->child_num; i; --i) {
00366 _lpres.unchecked_push_back(new BCP_lp_result);
00367 _new_cuts.push_back(BCP_vec<BCP_cut*>());
00368 _new_rows.push_back(BCP_vec<BCP_row*>());
00369 }
00370 }
00373 ~BCP_presolved_lp_brobj() {
00374 purge_ptr_vector(_lpres);
00375 purge_ptr_vector(_user_data);
00376 for (int i = _new_cuts.size() - 1; i >= 0; --i) {
00377 purge_ptr_vector(_new_cuts[i]);
00378 purge_ptr_vector(_new_rows[i]);
00379 }
00380 }
00388 inline BCP_lp_branching_object* candidate() {
00389 return _candidate;
00390 }
00392 inline const BCP_lp_branching_object* candidate() const {
00393 return _candidate;
00394 }
00397 inline const BCP_lp_result& lpres(const int child_ind) const {
00398 return *(_lpres[child_ind]);
00399 }
00403 inline BCP_vec<BCP_child_action>& action() {
00404 return _child_action;
00405 }
00407 inline const BCP_vec<BCP_child_action>& action() const {
00408 return _child_action;
00409 }
00410
00414 inline BCP_vec<BCP_user_data*>& user_data() {
00415 return _user_data;
00416 }
00418 inline const BCP_vec<BCP_user_data*>& user_data() const {
00419 return _user_data;
00420 }
00421
00424 bool fathomable(const double objval_limit) const;
00427 bool had_numerical_problems() const;
00432 inline void initialize_lower_bound(const double val) {
00433 for (int i = _candidate->child_num - 1; i >= 0; --i) {
00434 _lpres[i]->fake_objective_value(val);
00435 }
00436 }
00437 inline void keep_no_child() {
00438 for (int i = _child_action.size() - 1; i >= 0; --i) {
00439 _child_action[i] = BCP_ReturnChild;
00440 }
00441 }
00442 inline bool is_pruned() const {
00443 for (int i = _child_action.size() - 1; i >= 0; --i) {
00444 if (_child_action[i] != BCP_FathomChild)
00445 return false;
00446 }
00447 return true;
00448 }
00450 inline void get_lower_bounds(BCP_vec<double>& obj) {
00451 obj.clear();
00452 obj.reserve(_candidate->child_num);
00453 const int num_children = _lpres.size();
00454 for (int i = 0; i < num_children; ++i)
00455 obj.unchecked_push_back(_lpres[i]->objval());
00456 }
00459 inline void set_lower_bounds(const BCP_vec<double>& obj) {
00460 const int num_children = _lpres.size();
00461 for (int i = 0; i < num_children; ++i)
00462 _lpres[i]->fake_objective_value(obj[i]);
00463 }
00467 inline void get_results(OsiSolverInterface& lp, const int child_ind) {
00468 _lpres[child_ind]->get_results(lp);
00469 }
00480 void fake_objective_values(const double itlim_objval);
00481
00485 void set_objective_values(const BCP_vec<double>& obj,
00486 const BCP_vec<int>& termcode,
00487 const double itlim_objval);
00488
00490 void swap(BCP_presolved_lp_brobj& rhs) {
00491 std::swap(_candidate, rhs._candidate);
00492 _lpres.swap(rhs._lpres);
00493 _child_action.swap(rhs._child_action);
00494 _user_data.swap(rhs._user_data);
00495 _new_cuts.swap(rhs._new_cuts);
00496 _new_rows.swap(rhs._new_rows);
00497 }
00498 inline BCP_vec< BCP_vec<BCP_cut*> >& get_new_cuts() { return _new_cuts; }
00499 inline BCP_vec< BCP_vec<BCP_row*> >& get_new_rows() { return _new_rows; }
00501 };
00502
00503 #endif