00001
00002
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
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
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
00097
00098
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
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 }