/home/coin/Bcp-1.0.0/Bcp/src/include/BCP_lp_branch.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef _BCP_LP_BRANCH_H
00004 #define _BCP_LP_BRANCH_H
00005 
00006 // This file is fully docified.
00007 
00008 #include "BCP_enum_branch.hpp"
00009 #include "BCP_vector.hpp"
00010 #include "BCP_lp_result.hpp"
00011 #include "BCP_USER.hpp"
00012 #include "BCP_var.hpp"
00013 #include "BCP_cut.hpp"
00014 #include "BCP_matrix.hpp"
00015 
00016 //#############################################################################
00017 
00018 class OsiSolverInterface;
00019 
00020 //#############################################################################
00021 // ASSUMPTION
00022 // ----------
00023 // All a branching object does are:
00024 // - add cuts and/or variables
00025 // - change bounds on cuts and/or variables
00026 //#############################################################################
00027 
00028 // *THINK* : Maybe the methods should be hidden???
00029 
00030 // *THINK* : Maybe we should just use vectors instead of pointers to vectors?
00031 // *THINK* : It'd simplify things and would not be significant extra storage
00032 // *THINK* : (maybe none at all, depending pon the system operator new...)
00033 
00044 class BCP_lp_branching_object {
00045 private:
00049         BCP_lp_branching_object(const BCP_lp_branching_object&);
00051         BCP_lp_branching_object& operator=(const BCP_lp_branching_object&);
00054 public:
00058         int child_num;
00060         BCP_vec<BCP_var*>* vars_to_add;
00062         BCP_vec<BCP_cut*>* cuts_to_add;
00063 
00071         BCP_vec<int>* forced_var_pos;
00076         BCP_vec<int>* forced_cut_pos;
00081         BCP_vec<double>* forced_var_bd;
00086         BCP_vec<double>* forced_cut_bd;
00099 
00100         BCP_vec<int>* implied_var_pos;
00102         BCP_vec<int>* implied_cut_pos;
00104         BCP_vec<double>* implied_var_bd;
00106         BCP_vec<double>* implied_cut_bd;
00109 
00110 public:
00118         explicit BCP_lp_branching_object(const int children,
00119                                                                          BCP_vec<BCP_var*>* const new_vars,
00120                                                                          BCP_vec<BCP_cut*>* const new_cuts,
00121                                                                          const BCP_vec<int>* const fvp,
00122                                                                          const BCP_vec<int>* const fcp,
00123                                                                          const BCP_vec<double>* const fvb,
00124                                                                          const BCP_vec<double>* const fcb,
00125                                                                          const BCP_vec<int>* const ivp,
00126                                                                          const BCP_vec<int>* const icp,
00127                                                                          const BCP_vec<double>* const ivb,
00128                                                                          const BCP_vec<double>* const icb ) :
00129                 child_num(children),
00130                 vars_to_add(0), cuts_to_add(0),
00131                 forced_var_pos(0), forced_cut_pos(0),
00132                 forced_var_bd(0), forced_cut_bd(0),
00133                 implied_var_pos(0), implied_cut_pos(0),
00134                 implied_var_bd(0), implied_cut_bd(0)
00135         {
00136                 if ( ((fvp == 0) ^ (fvb == 0)) || ((fcp == 0) ^ (fcb == 0)) || 
00137                          ((ivp == 0) ^ (ivb == 0)) || ((icp == 0) ^ (icb == 0)) )
00138                         throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
00139                 if ( (fvp && (2 * children* fvp->size() != fvb->size())) ||
00140                          (fcp && (2 * children* fcp->size() != fcb->size())) ||
00141                          (ivp && (2 * children* ivp->size() != ivb->size())) ||
00142                          (icp && (2 * children* icp->size() != icb->size())) )
00143                         throw BCP_fatal_error("Bad args to BCP_lp_branching_object()\n");
00144 
00145                 if (new_vars) {
00146                         vars_to_add = new BCP_vec<BCP_var*>(*new_vars);
00147                         new_vars->clear();
00148                 }
00149                 if (new_cuts) {
00150                         cuts_to_add = new BCP_vec<BCP_cut*>(*new_cuts);
00151                         new_cuts->clear();
00152                 }
00153 
00154                 if (fvp) forced_var_pos = new BCP_vec<int>(*fvp);
00155                 if (fcp) forced_cut_pos = new BCP_vec<int>(*fcp);
00156                 if (fvb) forced_var_bd = new BCP_vec<double>(*fvb);
00157                 if (fcb) forced_cut_bd = new BCP_vec<double>(*fcb);
00158 
00159                 if (ivp) implied_var_pos = new BCP_vec<int>(*ivp);
00160                 if (icp) implied_cut_pos = new BCP_vec<int>(*icp);
00161                 if (ivb) implied_var_bd = new BCP_vec<double>(*ivb);
00162                 if (icb) implied_cut_bd = new BCP_vec<double>(*icb);
00163         }
00164 
00165         // NOTE: when the desctructor `delete's vars_to_add and cuts_to_add, it
00166         // will just delete the pointers in the BCP_lp_..._sets (see the
00167         // destructors of those classes). But this is intentional, because the
00168         // vars/cuts will be actually deleted only later, when the unnecessery
00169         // ones are deleted from the formulation.
00171         ~BCP_lp_branching_object() {
00172                 delete vars_to_add;     delete cuts_to_add;
00173                 delete forced_var_pos;  delete forced_cut_pos;
00174                 delete forced_var_bd;   delete forced_cut_bd;
00175                 delete implied_var_pos; delete implied_cut_pos;
00176                 delete implied_var_bd;  delete implied_cut_bd;
00177         }
00184         inline int vars_affected() const {
00185                 return
00186                         (forced_var_bd ? forced_var_bd->size() / (2*child_num) : 0) +
00187                         (implied_var_bd ? implied_var_bd->size() / (2*child_num) : 0);
00188         }
00191         inline int cuts_affected() const {
00192                 return
00193                         (forced_cut_bd ? forced_cut_bd->size() / (2*child_num) : 0) +
00194                         (implied_cut_bd ? implied_cut_bd->size() / (2*child_num) : 0);
00195         }
00197         inline int vars_added() const {
00198                 return vars_to_add ? vars_to_add->size() : 0;
00199         }
00201         inline int cuts_added() const {
00202                 return cuts_to_add ? cuts_to_add->size() : 0;
00203         }
00208         inline
00209         BCP_vec<double>::const_iterator forced_var_bd_child(const int index)const {
00210                 return forced_var_bd->entry(2 * forced_var_pos->size() * index);
00211         }
00216         inline
00217         BCP_vec<double>::const_iterator forced_cut_bd_child(const int index)const {
00218                 return forced_cut_bd->entry(2 * forced_cut_pos->size() * index);
00219         }
00224         inline
00225         BCP_vec<double>::const_iterator implied_var_bd_child(const int index)const{
00226                 return implied_var_bd->entry(2 * implied_var_pos->size() * index);
00227         }
00232         inline
00233         BCP_vec<double>::const_iterator implied_cut_bd_child(const int index)const{
00234                 return implied_cut_bd->entry(2 * implied_cut_pos->size() * index);
00235         }
00240         // this routine reorders the positions/bounds as well so that the positions
00241         // are in increasing order (the vars/cuts are already added to the problem,
00242         // no need to reorder those, too)
00248         void init_pos_for_added(const int added_vars_start,
00249                                                         const int added_cuts_start);
00253         void apply_child_bd(OsiSolverInterface* lp, const int child_ind) const;
00256         void print_branching_info(const int orig_varnum,
00257                                                           const double* x, const double * obj) const;
00259 };
00260 
00261 //#############################################################################
00262 
00273 class BCP_presolved_lp_brobj {
00274 private:
00278         BCP_presolved_lp_brobj(const BCP_presolved_lp_brobj&);
00280         BCP_presolved_lp_brobj& operator=(const BCP_presolved_lp_brobj&);
00283 private:
00288         BCP_lp_branching_object* _candidate;
00290         BCP_vec<BCP_lp_result*> _lpres;
00291         // what to do with each child
00295         BCP_vec<BCP_child_action> _child_action;
00299         BCP_vec<BCP_user_data*> _user_data;
00301         BCP_vec< BCP_vec<BCP_cut*> > _new_cuts;
00302         BCP_vec< BCP_vec<BCP_row*> > _new_rows;
00305 public:
00310         explicit BCP_presolved_lp_brobj(BCP_lp_branching_object* candidate) :
00311                 _candidate(candidate),
00312                 _lpres(),
00313                 _child_action(candidate->child_num, BCP_ReturnChild),
00314                 _user_data(candidate->child_num, NULL)
00315         {
00316                 _lpres.reserve(candidate->child_num);
00317                 for (int i = candidate->child_num; i; --i) {
00318                         _lpres.unchecked_push_back(new BCP_lp_result);
00319                         _new_cuts.push_back(BCP_vec<BCP_cut*>());
00320                         _new_rows.push_back(BCP_vec<BCP_row*>());
00321                 }
00322         }
00325         ~BCP_presolved_lp_brobj() {
00326                 purge_ptr_vector(_lpres);
00327                 purge_ptr_vector(_user_data);
00328                 for (int i = _new_cuts.size() - 1; i >= 0; --i) {
00329                         purge_ptr_vector(_new_cuts[i]);
00330                         purge_ptr_vector(_new_rows[i]);
00331                 }
00332         }
00340         inline BCP_lp_branching_object* candidate() {
00341                 return _candidate;
00342         }
00344         inline const BCP_lp_branching_object* candidate() const {
00345                 return _candidate;
00346         }
00349         inline const BCP_lp_result& lpres(const int child_ind) const {
00350                 return *(_lpres[child_ind]);
00351         }
00355         inline BCP_vec<BCP_child_action>& action() {
00356                 return _child_action;
00357         }
00359         inline const BCP_vec<BCP_child_action>& action() const {
00360                 return _child_action;
00361         }
00362 
00366         inline BCP_vec<BCP_user_data*>& user_data() {
00367                 return _user_data;
00368         }
00370         inline const BCP_vec<BCP_user_data*>& user_data() const {
00371                 return _user_data;
00372         }
00373 
00376         const bool fathomable(const double objval_limit) const;
00379         const bool had_numerical_problems() const; 
00384         inline void initialize_lower_bound(const double val) {
00385                 for (int i = _candidate->child_num - 1; i >= 0; --i) {
00386                         _lpres[i]->fake_objective_value(val);
00387                 }
00388         }
00389         inline void keep_no_child() {
00390                 for (int i = _child_action.size() - 1; i >= 0; --i) {
00391                         if (_child_action[i] == BCP_KeepChild) {
00392                                 _child_action[i] = BCP_ReturnChild;
00393                                 return;
00394                         }
00395                 }
00396         }
00397         inline bool is_pruned() const {
00398                 for (int i = _child_action.size() - 1; i >= 0; --i) {
00399                         if (_child_action[i] != BCP_FathomChild)
00400                                 return false;
00401                 }
00402                 return true;
00403         }
00405         inline void get_lower_bounds(BCP_vec<double>& obj) {
00406                 obj.clear();
00407                 obj.reserve(_candidate->child_num);
00408                 const int num_children = _lpres.size();
00409                 for (int i = 0; i < num_children; ++i)
00410                         obj.unchecked_push_back(_lpres[i]->objval());
00411         }
00414         inline void set_lower_bounds(const BCP_vec<double>& obj) {
00415                 const int num_children = _lpres.size();
00416                 for (int i = 0; i < num_children; ++i)
00417                         _lpres[i]->fake_objective_value(obj[i]);
00418         }
00422         inline void get_results(OsiSolverInterface& lp, const int child_ind) {
00423                 _lpres[child_ind]->get_results(lp);
00424         }
00435         void fake_objective_values(const double itlim_objval);
00436 
00438         void swap(BCP_presolved_lp_brobj& rhs) {
00439                 std::swap(_candidate, rhs._candidate);
00440                 _lpres.swap(rhs._lpres);
00441                 _child_action.swap(rhs._child_action);
00442                 _user_data.swap(rhs._user_data);
00443                 _new_cuts.swap(rhs._new_cuts);
00444                 _new_rows.swap(rhs._new_rows);
00445         }
00446         inline BCP_vec< BCP_vec<BCP_cut*> >& get_new_cuts() { return _new_cuts; }
00447         inline BCP_vec< BCP_vec<BCP_row*> >& get_new_rows() { return _new_rows; }
00449 };
00450 
00451 #endif

Generated on Wed Aug 22 03:00:53 2007 for coin-Bcp by  doxygen 1.4.7