/home/coin/SVN-release/Bcp-1.2.1/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_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 // ASSUMPTION
00048 // ----------
00049 // All a branching object does are:
00050 // - add cuts and/or variables
00051 // - change bounds on cuts and/or variables
00052 //#############################################################################
00053 
00054 // *THINK* : Maybe the methods should be hidden???
00055 
00056 // *THINK* : Maybe we should just use vectors instead of pointers to vectors?
00057 // *THINK* : It'd simplify things and would not be significant extra storage
00058 // *THINK* : (maybe none at all, depending pon the system operator new...)
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     // NOTE: when the desctructor `delete's vars_to_add and cuts_to_add, it
00213     // will just delete the pointers in the BCP_lp_..._sets (see the
00214     // destructors of those classes). But this is intentional, because the
00215     // vars/cuts will be actually deleted only later, when the unnecessery
00216     // ones are deleted from the formulation.
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     // this routine reorders the positions/bounds as well so that the positions
00289     // are in increasing order (the vars/cuts are already added to the problem,
00290     // no need to reorder those, too)
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     // what to do with each child
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

Generated on Thu Jan 15 03:00:58 2009 for coin-Bcp by  doxygen 1.4.7