/home/coin/SVN-release/OS-2.4.0/Bcp/src/TM/BCP_tm_node.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include "BCP_math.hpp"
00004 #include "BCP_USER.hpp"
00005 #include "BCP_tm.hpp"
00006 #include "BCP_tm_user.hpp"
00007 #include "BCP_tm_node.hpp"
00008 #include "BCP_node_change.hpp"
00009 
00010 
00011 int BCP_tm_node::num_local_nodes = 0;
00012 int BCP_tm_node::num_remote_nodes = 0;
00013 
00014 //#############################################################################
00015 
00016 BCP_tm_node::BCP_tm_node(int level, BCP_node_change* desc) :
00017   CoinTreeNode(level),
00018   status(BCP_DefaultNode),
00019   _index(0),
00020   _parent(0),
00021   _birth_index(-1),
00022   _children(),
00023   lp(-1), cg(-1), cp(-1), vg(-1), vp(-1),
00024   _processed_leaf_num(0),
00025   _pruned_leaf_num(0),
00026   _tobepriced_leaf_num(0),
00027   _leaf_num(0),
00028   _core_storage(-1),
00029   _var_storage(-1),
00030   _cut_storage(-1),
00031   _ws_storage(-1),
00032   _locally_stored(true),
00033   _data_location(-1),
00034   _data(desc)
00035 {
00036   ++num_local_nodes;
00037 }
00038 
00039 //#############################################################################
00040 
00041 // BCP_tm_node::BCP_tm_node(int level, BCP_node_change* desc,
00042 //                       BCP_tm_node* parent, int index) :
00043 //   CoinTreeNode(level),
00044 //   status(BCP_DefaultNode),
00045 //   _index(0),
00046 //   _parent(0),
00047 //   _birth_index(-1),
00048 //   _children(),
00049 //   lp(-1), cg(-1), cp(-1), vg(-1), vp(-1),
00050 //   _processed_leaf_num(0),
00051 //   _pruned_leaf_num(0),
00052 //   _tobepriced_leaf_num(0),
00053 //   _leaf_num(0),
00054 //   _locally_stored(1),
00055 //   _data_location(-1),
00056 //   _data(desc) {}
00057 
00058 //#############################################################################
00059 
00060 int
00061 BCP_tm_node::mark_descendants_for_deletion() {
00062     int del_num = child_num();
00063     if (del_num > 0) {
00064         BCP_vec<BCP_tm_node*>::iterator child = _children.begin();
00065         BCP_vec<BCP_tm_node*>::const_iterator lastchild = _children.end();
00066         while (child != lastchild) {
00067             del_num += (*child)->mark_descendants_for_deletion();
00068             (*child)->_index = -1;
00069             ++child;
00070         }
00071         _children.clear();
00072     }
00073     return del_num;
00074 }
00075 
00076 //#############################################################################
00077 
00078 void
00079 BCP_tm_node::remove_child(BCP_tm_node* node)
00080 {
00081     const int num_children = child_num();
00082     int i;
00083     for (i = num_children - 1; i >= 0; --i) {
00084         if (_children[i] == node)
00085             break;
00086     }
00087     if (i < 0) {
00088         throw BCP_fatal_error("BCP_tm_node::remove_child : \
00089 Trying to remove nonexistent child.\n");
00090     }
00091     _children[i] = _children[num_children-1];
00092     _children.pop_back();
00093 }
00094 
00095 //#############################################################################
00096 // This member function counts for every serch tree node the number of
00097 // descendants and that how many of them are pruned already / currently being
00098 // processed. (This includes the node itself.)
00099 
00100 void
00101 BCP_tree::enumerate_leaves(BCP_tm_node* node, const double obj_limit)
00102 {
00103     if (node->child_num() == 0) {
00104         const BCP_tm_node_status st = node->status;
00105         node->_leaf_num = 1;
00106         node->_processed_leaf_num = st == BCP_ActiveNode ? 1 : 0;
00107         const bool is_pruned = ( st == BCP_PrunedNode_OverUB ||
00108                                  st == BCP_PrunedNode_Infeas ||
00109                                  st == BCP_PrunedNode_Discarded );
00110         node->_pruned_leaf_num = is_pruned ? 1 : 0;
00111         const bool is_next_phase = ( st == BCP_NextPhaseNode_OverUB ||
00112                                      st == BCP_NextPhaseNode_Infeas );
00113         node->_tobepriced_leaf_num =
00114             ( ((st & (BCP_ProcessedNode|BCP_ActiveNode|BCP_CandidateNode)) &&
00115                node->getTrueLB() > obj_limit) ||
00116               is_next_phase ) ? 1 : 0;
00117     } else {
00118         node->_leaf_num = 0;
00119         node->_processed_leaf_num = 0;
00120         node->_pruned_leaf_num = 0;
00121         node->_tobepriced_leaf_num = 0;
00122         BCP_vec<BCP_tm_node*>::iterator child;
00123         BCP_vec<BCP_tm_node*>::const_iterator lastchild =
00124             node->_children.end();
00125         for (child = node->_children.begin(); child != lastchild; ++child) {
00126             this->enumerate_leaves(*child, obj_limit);
00127             node->_processed_leaf_num += (*child)->_processed_leaf_num;
00128             node->_pruned_leaf_num += (*child)->_pruned_leaf_num;
00129             node->_tobepriced_leaf_num += (*child)->_tobepriced_leaf_num;
00130             node->_leaf_num += (*child)->_leaf_num;
00131         }
00132     }
00133 }
00134 
00135 //#############################################################################
00136 // Find the best lower bound
00137 double
00138 BCP_tree::true_lower_bound(const BCP_tm_node* node) const
00139 {
00140     double worstlb = BCP_DBL_MAX;
00141     if (node->child_num() == 0) {
00142         const BCP_tm_node_status st = node->status;
00143         if (st == BCP_ActiveNode || st == BCP_CandidateNode)
00144             worstlb = node->getTrueLB();
00145     } else {
00146         BCP_vec<BCP_tm_node*>::const_iterator child;
00147         BCP_vec<BCP_tm_node*>::const_iterator lastchild = node->_children.end();
00148         for (child = node->_children.begin(); child != lastchild; ++child) {
00149             const double childlb = true_lower_bound(*child);
00150             if (childlb < worstlb)
00151                 worstlb = childlb;
00152         }
00153     }
00154     return worstlb;
00155 }

Generated on Thu Sep 22 03:05:53 2011 by  doxygen 1.4.7