Bcp 1.4.4
Loading...
Searching...
No Matches
BCP_tm_node.hpp
Go to the documentation of this file.
1// Copyright (C) 2000, International Business Machines
2// Corporation and others. All Rights Reserved.
3#ifndef _BCP_TM_NODE
4#define _BCP_TM_NODE
5
6//#include <cfloat>
7
8#include <map>
9
10#include "CoinSearchTree.hpp"
11#include "CoinSmartPtr.hpp"
12
13#include "BCP_math.hpp"
14#include "BCP_vector.hpp"
15
16#include "BCP_message_tag.hpp"
17#include "BCP_obj_change.hpp"
18#include "BCP_node_change.hpp"
19#include "BCP_USER.hpp"
20
43
44//#############################################################################
45
46class BCP_tm_node;
47class BCP_tm_prob;
48
49//#############################################################################
50
57
58//=============================================================================
59
60class BCP_tm_node : public CoinTreeNode {
61private:
67 BCP_tm_node& operator=(const BCP_tm_node&);
70 // NOTE: deleting a tree_node deletes the whole subtree below!
71public:
73 static int num_local_nodes;
74 static int num_remote_nodes;
75 // *FIXME* break into groups
80 int _index;
83
89 int lp, cg, cp, vg, vp;
98
103
105 // Exactly one of the next two is always irrelevant */
108
111public:
115 BCP_tm_node(int level, BCP_node_change* desc);
116
118// BCP_tm_node(int level, BCP_node_change* desc,
119// BCP_tm_node* parent, int index);
122 {
123 if (_locally_stored) {
125 } else {
127 }
128 }
134 inline int index() const { return _index; }
136 inline int child_num() const { return _children.size(); }
138 inline int birth_index() const { return _birth_index; }
139
141 // inline BCP_user_data* user_data() { return _data._user; }
143 inline BCP_tm_node* child(int ind) { return _children[ind]; }
145 inline BCP_tm_node* parent() { return _parent; }
146
148 // inline const BCP_user_data* user_data() const { return _data._user; }
150 inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
152 inline const BCP_tm_node* parent() const { return _parent; }
159 // Marking the descendants for deletion means that their _index fields are
160 // set to -1. The reason is that some book-keeping must be one with the CP,
161 // VP processes; with the next phase list, with the priority queue of the
162 // current phase (and maybe sthing else?). So this function only marks, and
163 // the data will be deleted later.
168 inline void reserve_child_num(int num) { _children.reserve(num); }
170 inline void new_child(BCP_tm_node* node) { _children.push_back(node); }
172};
173
174//#############################################################################
175
178class BCP_tree {
179private:
183 int maxdepth_;
184 int processed_;
185
186public:
190 BCP_tree() : _tree(), maxdepth_(0), processed_(0) {}
193 for (int i = _tree.size() - 1; i >= 0; --i) {
194 delete _tree[i];
195 }
196 }
202 inline BCP_vec<BCP_tm_node*>::iterator begin() { return _tree.begin(); }
204 inline BCP_vec<BCP_tm_node*>::iterator end() { return _tree.end(); }
205
207 inline BCP_tm_node* root() { return _tree.front(); }
209 inline BCP_tm_node* operator[](int index) { return _tree[index]; }
211 inline size_t size() const { return _tree.size(); }
213 inline int maxdepth() const { return maxdepth_; }
215 inline int processed() const { return processed_; }
216 inline void increase_processed() { ++processed_; }
222 double true_lower_bound(const BCP_tm_node* node) const;
224 void enumerate_leaves(BCP_tm_node* node, const double obj_limit);
226 inline void insert(BCP_tm_node* node) {
227 node->_index = _tree.size();
228 _tree.push_back(node);
229 if (node->getDepth() > maxdepth_)
230 maxdepth_ = node->getDepth();
231 }
232 inline void remove(int index) {
233 _tree[index] = 0;
234 }
236};
237
238//#############################################################################
240
242{
243public:
244 static std::map<int, BCP_tm_node_to_send*> waiting;
245
246private:
247 BCP_tm_prob& p;
248
250 BCP_message_tag msgtag;
251
254 const int ID;
255
256 const BCP_tm_node* node;
259 const BCP_tm_node** root_path;
261 int* child_index;
264 BCP_tm_node_data* node_data_on_root_path;
265
267 int level;
268
270 int explicit_core_level;
271 int explicit_var_level;
272 int explicit_cut_level;
273 int explicit_ws_level;
274 int explicit_all_level;
275
277 int missing_desc_num;
279 int missing_var_num;
281 int missing_cut_num;
282
286 BCP_obj_set_change var_set;
287 BCP_obj_set_change cut_set;
292
293public:
294
296 const BCP_message_tag tag);
298
301 bool send();
302
315};
316
317#endif
BCP_message_tag
This enumerative constant describes the message tags different processes of BCP understand.
BCP_tm_node_status
Node status in the Tree Manager.
@ BCP_NextPhaseNode_OverUB
@ BCP_ActiveNode
@ BCP_CandidateNode
@ BCP_PrunedNode_Infeas
@ BCP_PrunedNode_Discarded
@ BCP_DefaultNode
@ BCP_PrunedNode_OverUB
@ BCP_NextPhaseNode_Infeas
@ BCP_ProcessedNode
This class describes the message buffer used for all processes of BCP.
This class stores data about how an object set (set of vars or set of cuts) changes.
Coin::SmartPtr< BCP_node_change > _desc
Coin::SmartPtr< BCP_user_data > _user
BCP_tm_node_data(BCP_node_change *d=NULL)
BCP_tm_node_to_send(BCP_tm_prob &p, const BCP_tm_node *node, const BCP_message_tag tag)
bool receive_vars(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
bool receive_node_desc(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
bool receive_cuts(BCP_buffer &buf)
return true if has everything to send the thing off to the LP.
bool send()
return true or false depending on whether the node was really sent out or it's still waiting for some...
static std::map< int, BCP_tm_node_to_send * > waiting
int _processed_leaf_num
void remove_child(BCP_tm_node *node)
int birth_index() const
int mark_descendants_for_deletion()
static int num_remote_nodes
BCP_tm_node * parent()
const BCP_tm_node * parent() const
void reserve_child_num(int num)
int child_num() const
void new_child(BCP_tm_node *node)
int _tobepriced_leaf_num
int index() const
BCP_tm_node_status status
BCP_tm_node * child(int ind)
BCP_vec< BCP_tm_node * > _children
BCP_tm_node(int level, BCP_node_change *desc)
BCP_tm_node * _parent
BCP_tm_node_data _data
static int num_local_nodes
const BCP_tm_node * child(int ind) const
NO OLD DOC.
Definition BCP_tm.hpp:136
NO OLD DOC.
BCP_tm_node * operator[](int index)
int maxdepth() const
BCP_vec< BCP_tm_node * >::iterator begin()
BCP_tm_node * root()
void increase_processed()
BCP_vec< BCP_tm_node * >::iterator end()
void insert(BCP_tm_node *node)
size_t size() const
int processed() const
void remove(int index)
void enumerate_leaves(BCP_tm_node *node, const double obj_limit)
double true_lower_bound(const BCP_tm_node *node) const
Return the worst true lower bound in the search tree.
The class BCP_vec serves the same purpose as the vector class in the standard template library.
void push_back(const_reference x)
Append x to the end of the vector.
iterator end()
Return an iterator to the end of the object.
size_t size() const
Return the current number of entries.
iterator begin()
Return an iterator to the beginning of the object.
reference front()
Return a reference to the first entry.
void reserve(const size_t n)
Reallocate the object to make space for n entries.
int getDepth() const