00001
00002
00003 #include <cstdio>
00004 #include "BCP_tm.hpp"
00005 #include "BCP_tm_functions.hpp"
00006
00007 static int BCP_tm_trim_tree(BCP_tm_prob& p, BCP_tm_node* node,
00008 const bool between_phases);
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 void BCP_tm_trim_tree_wrapper(BCP_tm_prob& p, const bool between_phases)
00019 {
00020 BCP_tree& tree = p.search_tree;
00021 BCP_tm_node* root = tree.root();
00022 tree.enumerate_leaves(root, p.ub() - p.granularity());
00023 const int trimmed =
00024 BCP_tm_trim_tree(p, root, true );
00025 if (p.param(BCP_tm_par::TmVerb_TrimmedNum)) {
00026 printf("\
00027 TM: before starting the new phase, \n\
00028 %i nodes were trimmed from the tree.\n", trimmed);
00029 }
00030
00031 BCP_vec<BCP_tm_node*>::iterator nodep;
00032 BCP_vec<BCP_tm_node*>::const_iterator lastnodep;
00033 BCP_tm_node * node;
00034
00035
00036 nodep = p.next_phase_nodes.begin();
00037 lastnodep = p.next_phase_nodes.end();
00038 while (nodep != lastnodep) {
00039 if ((*nodep)->index() == -1) {
00040 *nodep = *--lastnodep;
00041 p.next_phase_nodes.pop_back();
00042 } else {
00043 ++nodep;
00044 }
00045 }
00046
00047
00048
00049 if (! p.candidate_list.empty()) {
00050 BCP_vec<BCP_tm_node*> cands;
00051 while (! p.candidate_list.empty()) {
00052 CoinTreeNode* coinnode = p.candidate_list.top();
00053 node = dynamic_cast<BCP_tm_node*>(coinnode);
00054 if (node->index() != -1)
00055 cands.push_back(node);
00056 p.candidate_list.pop();
00057 }
00058 lastnodep = cands.end();
00059 for (nodep = cands.begin(); nodep != lastnodep; ++nodep)
00060 p.candidate_list.push(*nodep);
00061 }
00062
00063
00064 nodep = p.search_tree.begin();
00065 lastnodep = p.search_tree.end();
00066 while (nodep != lastnodep) {
00067 node = *nodep;
00068 if (node->index() == -1) {
00069
00070 #ifdef BCP_DEBUG
00071 if (node->lp != -1 || node->cg != -1 || node->vg != -1)
00072 throw BCP_fatal_error("\
00073 TM: At least on of lp/cg/vg of a trimmed node is non-0.\n");
00074 #endif
00075 if (node->cp != -1 && node->child_num() == 0) {
00076 BCP_vec< std::pair<int, int> >::iterator proc =
00077 BCP_tm_identify_process(p.leaves_per_cp, node->cp);
00078 #ifdef BCP_DEBUG
00079 if (proc == p.leaves_per_cp.end())
00080 throw BCP_fatal_error("\
00081 TM: non-existing CP is assigned to a leaf.\n");
00082 #endif
00083 --proc->second;
00084 }
00085 if (node->vp != -1 && node->child_num() == 0) {
00086 BCP_vec< std::pair<int, int> >::iterator proc =
00087 BCP_tm_identify_process(p.leaves_per_vp, node->vp);
00088 #ifdef BCP_DEBUG
00089 if (proc == p.leaves_per_vp.end())
00090 throw BCP_fatal_error("\
00091 TM: non-existing VP is assigned to a leaf.\n");
00092 #endif
00093 --proc->second;
00094 }
00095 delete node;
00096 *nodep = 0;
00097 }
00098 ++nodep;
00099 }
00100
00101 #if ! defined(BCP_ONLY_LP_PROCESS_HANDLING_WORKS)
00102
00103 BCP_vec< std::pair<int, int> >::iterator proc;
00104 BCP_vec< std::pair<int, int> >::iterator lastproc;
00105
00106 lastproc = p.leaves_per_cp.end();
00107 for (proc = p.leaves_per_cp.begin(); proc != lastproc; ++proc)
00108 if (proc->second == 0)
00109 p.slaves.cp->set_proc_free(proc->first);
00110
00111 lastproc = p.leaves_per_vp.end();
00112 for (proc = p.leaves_per_vp.begin(); proc != lastproc; ++proc)
00113 if (proc->second == 0)
00114 p.slaves.vp->set_proc_free(proc->first);
00115 #endif
00116 }
00117
00118
00119
00120
00121 int BCP_tm_trim_tree(BCP_tm_prob& p, BCP_tm_node* node,
00122 const bool between_phases)
00123 {
00124 bool trim = true;
00125 int trimmed = 0;
00126
00127 if (node->_processed_leaf_num > 0) {
00128
00129
00130 trim = false;
00131 } else if (node->child_num() == 0) {
00132
00133 trim = false;
00134 } else if (node->_leaf_num - node->_pruned_leaf_num <= 2) {
00135
00136
00137 trim = false;
00138 } else if (node->getTrueLB() < p.ub() - p.granularity()) {
00139
00140 trim = false;
00141 }
00142
00143 if (trim) {
00144 trimmed = node->mark_descendants_for_deletion();
00145 if (node->cp != -1) {
00146 BCP_vec< std::pair<int, int> >::iterator proc =
00147 BCP_tm_identify_process(p.leaves_per_cp, node->cp);
00148 #ifdef BCP_DEBUG
00149 if (proc == p.leaves_per_cp.end())
00150 throw BCP_fatal_error("\
00151 TM: An internal node is assigned to a non-existing CP.\n");
00152 #endif
00153 ++proc->second;
00154 }
00155 if (node->vp != -1) {
00156 BCP_vec< std::pair<int, int> >::iterator proc =
00157 BCP_tm_identify_process(p.leaves_per_vp, node->vp);
00158 #ifdef BCP_DEBUG
00159 if (proc == p.leaves_per_vp.end())
00160 throw BCP_fatal_error("\
00161 TM: An internal node is assigned to a non-existing VP.\n");
00162 #endif
00163 ++proc->second;
00164 }
00165 } else {
00166
00167 BCP_vec<BCP_tm_node*>::iterator child;
00168 BCP_vec<BCP_tm_node*>::const_iterator lastchild =
00169 node->_children.end();
00170 for (child = node->_children.begin(); child != lastchild; ++child)
00171 trimmed += BCP_tm_trim_tree(p, *child, between_phases);
00172 }
00173
00174 return trimmed;
00175 }
00176
00177
00178
00179
00180 void BCP_tm_remove_explored(BCP_tm_prob& p, BCP_tm_node* node)
00181 {
00182 if (! p.param(BCP_tm_par::RemoveExploredBranches))
00183 return;
00184
00185 if (node->child_num() == 0) {
00186 BCP_tm_node* parent = node->parent();
00187 p.search_tree.remove(node->index());
00188 delete node;
00189
00190 if (parent) {
00191 parent->remove_child(node);
00192 BCP_tm_remove_explored(p, parent);
00193 }
00194 }
00195 }
00196
00197