Cbc  2.8.12
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
CbcTree.hpp
Go to the documentation of this file.
1 /* $Id: CbcTree.hpp 1813 2012-11-22 19:00:22Z forrest $ */
2 // Copyright (C) 2004, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef CbcTree_H
7 #define CbcTree_H
8 
9 #include <vector>
10 #include <algorithm>
11 #include <cmath>
12 
13 #include "CoinHelperFunctions.hpp"
14 #include "CbcCompare.hpp"
15 
29 //#define CBC_DUBIOUS_HEAP
30 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
31 //#define CBC_DUBIOUS_HEAP
32 #endif
33 #if 1 //ndef CBC_DUBIOUS_HEAP
34 
53 class CbcTree {
54 
55 public:
58  CbcTree ();
60 
62  CbcTree (const CbcTree &rhs);
63 
65  CbcTree & operator=(const CbcTree &rhs);
66 
68  virtual ~CbcTree();
69 
71  virtual CbcTree * clone() const;
72 
74  virtual void generateCpp(FILE *) {}
76 
79  void setComparison(CbcCompareBase &compare);
81 
83  virtual CbcNode * top() const;
84 
86  virtual void push(CbcNode *x);
87 
89  virtual void pop() ;
90 
97  virtual CbcNode * bestNode(double cutoff);
98 
100  virtual void rebuild() ;
102 
105  virtual bool empty() ;
107 
109  virtual int size() const { return static_cast<int>(nodes_.size()); }
110 
112  inline CbcNode * operator [] (int i) const { return nodes_[i]; }
113 
115  inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
116  void realpop();
118  void fixTop();
119  void realpush(CbcNode * node);
121 
130  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
131 
134 
136  virtual void endSearch() {}
137 
139  virtual double getBestPossibleObjective();
140 
142  inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
143 
145  inline int maximumNodeNumber() const { return maximumNodeNumber_; }
146 
148  inline void setNumberBranching(int value) { numberBranching_ = value; }
149 
151  inline int getNumberBranching() const { return numberBranching_; }
152 
154  inline void setMaximumBranching(int value) { maximumBranching_ = value; }
155 
157  inline int getMaximumBranching() const { return maximumBranching_; }
158 
160  inline unsigned int * branched() const { return branched_; }
161 
163  inline int * newBounds() const { return newBound_; }
164 
166  void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
167  const double * currentLower,
168  const double * currentUpper);
170  void increaseSpace();
172 
173 # if CBC_DEBUG_HEAP > 0
174 
177  void validateHeap() ;
179 # endif
180 
181 protected:
183  std::vector <CbcNode *> nodes_;
196  unsigned int * branched_;
198  int * newBound_;
199 };
200 
201 #ifdef JJF_ZERO // not used
202 
206 class CbcTreeArray : public CbcTree {
207 
208 public:
209 
210  // Default Constructor
211  CbcTreeArray ();
212 
213  // Copy constructor
214  CbcTreeArray ( const CbcTreeArray & rhs);
215  // = operator
216  CbcTreeArray & operator=(const CbcTreeArray & rhs);
217 
218  virtual ~CbcTreeArray();
219 
221  virtual CbcTree * clone() const;
223  virtual void generateCpp( FILE * ) {}
224 
227 
229  void setComparison(CbcCompareBase &compare);
230 
232  virtual void push(CbcNode * x);
233 
235  virtual CbcNode * bestNode(double cutoff);
236 
238 
240 
242  virtual bool empty() ;
243 
245 
248 
257  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
259  virtual double getBestPossibleObjective();
261 protected:
264  CbcNode * lastNode_;
266  CbcNode * lastNodePopped_;
268  int switches_;
269 
270 };
271 
273 #include "CoinSearchTree.hpp"
280 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
281 
282 public:
283 
284  // Default Constructor
285  CbcNewTree ();
286 
287  // Copy constructor
288  CbcNewTree ( const CbcNewTree & rhs);
289  // = operator
290  CbcNewTree & operator=(const CbcNewTree & rhs);
291 
292  virtual ~CbcNewTree();
293 
295  virtual CbcNewTree * clone() const;
297  virtual void generateCpp( FILE * ) {}
298 
301 
303  void setComparison(CbcCompareBase &compare);
304 
306  virtual CbcNode * top() const;
307 
309  virtual void push(CbcNode * x);
310 
312  virtual void pop() ;
314  virtual CbcNode * bestNode(double cutoff);
315 
317 
319 
321  virtual bool empty() ;
322 
324  inline int size() const {
325  return nodes_.size();
326  }
327 
329  inline CbcNode * operator [] (int i) const {
330  return nodes_[i];
331  }
332 
334  inline CbcNode * nodePointer (int i) const {
335  return nodes_[i];
336  }
337 
339 
342 
351  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
352 
355 
357  virtual void endSearch() {}
359 protected:
360 
361 
362 };
363 #endif
364 #else
365 /* CBC_DUBIOUS_HEAP is defined
366 
367  See note at top of file. This code is highly suspect.
368  -- lh, 100921 --
369 */
370 class CbcTree {
371 
372 public:
373 
374  // Default Constructor
375  CbcTree ();
376 
377  // Copy constructor
378  CbcTree ( const CbcTree & rhs);
379  // = operator
380  CbcTree & operator=(const CbcTree & rhs);
381 
382  virtual ~CbcTree();
383 
385  virtual CbcTree * clone() const;
387  virtual void generateCpp( FILE * fp) {}
388 
391 
393  void setComparison(CbcCompareBase &compare);
394 
396  virtual CbcNode * top() const;
397 
399  virtual void push(CbcNode * x);
400 
402  virtual void pop() ;
404  virtual CbcNode * bestNode(double cutoff);
405 
407 
409 
411  //virtual bool empty() ;
412 
414  inline int size() const {
415  return nodes_.size();
416  }
417 
419  inline CbcNode * operator [] (int i) const {
420  return nodes_[i];
421  }
422 
424  inline CbcNode * nodePointer (int i) const {
425  return nodes_[i];
426  }
427 
428  virtual bool empty();
429  //inline int size() const { return size_; }
430  void realpop();
432  void fixTop();
433  void realpush(CbcNode * node);
435 
438 
447  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
448 
451 
453  virtual void endSearch() {}
455  inline void resetNodeNumbers() {
456  maximumNodeNumber_ = 0;
457  }
458 
460  inline int maximumNodeNumber() const { return maximumNodeNumber_; }
462 protected:
463  std::vector <CbcNode *> nodes_;
465  int maximumNodeNumber_;
467 
468 
469 };
470 #endif
471 #endif
472 
virtual bool empty()
Test for an empty tree.
int * newBound_
New bound.
Definition: CbcTree.hpp:198
int getNumberBranching() const
Get number of branches.
Definition: CbcTree.hpp:151
CbcNode * bestAlternate()
Get best on list using alternate method.
virtual int size() const
Return size.
Definition: CbcTree.hpp:109
CbcTree()
Default Constructor.
virtual void push(CbcNode *x)
Add a node to the heap.
int maximumBranching_
Maximum size of variable list.
Definition: CbcTree.hpp:191
void fixTop()
After changing data in the top node, fix the heap.
void realpush(CbcNode *node)
unsigned int * branched_
Integer variables branched or bounded top bit set if new upper bound next bit set if a branch...
Definition: CbcTree.hpp:196
void setNumberBranching(int value)
Set number of branches.
Definition: CbcTree.hpp:148
void increaseSpace()
Increase space for data.
CbcTree & operator=(const CbcTree &rhs)
= operator
virtual void rebuild()
Rebuild the heap.
int maximumNodeNumber_
Maximum "node" number so far to split ties.
Definition: CbcTree.hpp:187
void realpop()
virtual CbcNode * bestNode(double cutoff)
Gets best node and takes off heap.
CbcNode * nodePointer(int i) const
Return a node pointer.
Definition: CbcTree.hpp:115
CbcNode * operator[](int i) const
Return a node pointer.
Definition: CbcTree.hpp:112
Using MS heap implementation.
Definition: CbcTree.hpp:53
virtual CbcTree * clone() const
Clone.
virtual void endSearch()
We may have got an intelligent tree so give it one more chance.
Definition: CbcTree.hpp:136
virtual void pop()
Remove the top node from the heap.
virtual CbcNode * top() const
Return the top node of the heap.
Information required while the node is live.
Definition: CbcNode.hpp:49
int getMaximumBranching() const
Get maximum branches.
Definition: CbcTree.hpp:157
virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
Prune the tree using an objective function cutoff.
void addBranchingInformation(const CbcModel *model, const CbcNodeInfo *nodeInfo, const double *currentLower, const double *currentUpper)
Adds branching information to complete state.
virtual void generateCpp(FILE *)
Create C++ lines to get to current state.
Definition: CbcTree.hpp:74
Information required to recreate the subproblem at this node.
Definition: CbcNodeInfo.hpp:68
std::vector< CbcNode * > nodes_
Storage vector for the heap.
Definition: CbcTree.hpp:183
void resetNodeNumbers()
Reset maximum node number.
Definition: CbcTree.hpp:142
int numberBranching_
Size of variable list.
Definition: CbcTree.hpp:189
CbcCompare comparison_
Sort predicate for heap ordering.
Definition: CbcTree.hpp:185
virtual ~CbcTree()
Destructor.
unsigned int * branched() const
Get branched variables.
Definition: CbcTree.hpp:160
void setComparison(CbcCompareBase &compare)
Set comparison function and resort heap.
int * newBounds() const
Get bounds.
Definition: CbcTree.hpp:163
int maximumNodeNumber() const
Get maximum node number.
Definition: CbcTree.hpp:145
virtual double getBestPossibleObjective()
Get best possible objective function in the tree.
Simple Branch and bound class.
Definition: CbcModel.hpp:100
void setMaximumBranching(int value)
Set maximum branches.
Definition: CbcTree.hpp:154