Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CbcTree.hpp
Go to the documentation of this file.
1 /* $Id: CbcTree.hpp 1943 2013-07-21 09:05:45Z 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  inline double lastObjective() const {
167  return lastObjective_;
168  }
170  inline int lastDepth() const {
171  return lastDepth_;
172  }
174  inline int lastUnsatisfied() const {
175  return lastUnsatisfied_;
176  }
178  void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
179  const double * currentLower,
180  const double * currentUpper);
182  void increaseSpace();
184 
185 # if CBC_DEBUG_HEAP > 0
186 
189  void validateHeap() ;
191 # endif
192 
193 protected:
195  std::vector <CbcNode *> nodes_;
214  unsigned int * branched_;
216  int * newBound_;
217 };
218 
219 #ifdef JJF_ZERO // not used
220 
224 class CbcTreeArray : public CbcTree {
225 
226 public:
227 
228  // Default Constructor
229  CbcTreeArray ();
230 
231  // Copy constructor
232  CbcTreeArray ( const CbcTreeArray & rhs);
233  // = operator
234  CbcTreeArray & operator=(const CbcTreeArray & rhs);
235 
236  virtual ~CbcTreeArray();
237 
239  virtual CbcTree * clone() const;
241  virtual void generateCpp( FILE * ) {}
242 
245 
247  void setComparison(CbcCompareBase &compare);
248 
250  virtual void push(CbcNode * x);
251 
253  virtual CbcNode * bestNode(double cutoff);
254 
256 
258 
260  virtual bool empty() ;
261 
263 
266 
275  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
277  virtual double getBestPossibleObjective();
279 protected:
282  CbcNode * lastNode_;
284  CbcNode * lastNodePopped_;
286  int switches_;
287 
288 };
289 
291 #include "CoinSearchTree.hpp"
298 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
299 
300 public:
301 
302  // Default Constructor
303  CbcNewTree ();
304 
305  // Copy constructor
306  CbcNewTree ( const CbcNewTree & rhs);
307  // = operator
308  CbcNewTree & operator=(const CbcNewTree & rhs);
309 
310  virtual ~CbcNewTree();
311 
313  virtual CbcNewTree * clone() const;
315  virtual void generateCpp( FILE * ) {}
316 
319 
321  void setComparison(CbcCompareBase &compare);
322 
324  virtual CbcNode * top() const;
325 
327  virtual void push(CbcNode * x);
328 
330  virtual void pop() ;
332  virtual CbcNode * bestNode(double cutoff);
333 
335 
337 
339  virtual bool empty() ;
340 
342  inline int size() const {
343  return nodes_.size();
344  }
345 
347  inline CbcNode * operator [] (int i) const {
348  return nodes_[i];
349  }
350 
352  inline CbcNode * nodePointer (int i) const {
353  return nodes_[i];
354  }
355 
357 
360 
369  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
370 
373 
375  virtual void endSearch() {}
377 protected:
378 
379 
380 };
381 #endif
382 #else
383 /* CBC_DUBIOUS_HEAP is defined
384 
385  See note at top of file. This code is highly suspect.
386  -- lh, 100921 --
387 */
388 class CbcTree {
389 
390 public:
391 
392  // Default Constructor
393  CbcTree ();
394 
395  // Copy constructor
396  CbcTree ( const CbcTree & rhs);
397  // = operator
398  CbcTree & operator=(const CbcTree & rhs);
399 
400  virtual ~CbcTree();
401 
403  virtual CbcTree * clone() const;
405  virtual void generateCpp( FILE * fp) {}
406 
409 
411  void setComparison(CbcCompareBase &compare);
412 
414  virtual CbcNode * top() const;
415 
417  virtual void push(CbcNode * x);
418 
420  virtual void pop() ;
422  virtual CbcNode * bestNode(double cutoff);
423 
425 
427 
429  //virtual bool empty() ;
430 
432  inline int size() const {
433  return nodes_.size();
434  }
435 
437  inline CbcNode * operator [] (int i) const {
438  return nodes_[i];
439  }
440 
442  inline CbcNode * nodePointer (int i) const {
443  return nodes_[i];
444  }
445 
446  virtual bool empty();
447  //inline int size() const { return size_; }
448  void realpop();
450  void fixTop();
451  void realpush(CbcNode * node);
453 
456 
465  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
466 
469 
471  virtual void endSearch() {}
473  inline void resetNodeNumbers() {
474  maximumNodeNumber_ = 0;
475  }
476 
478  inline int maximumNodeNumber() const { return maximumNodeNumber_; }
480 protected:
481  std::vector <CbcNode *> nodes_;
483  int maximumNodeNumber_;
485 
486 
487 };
488 #endif
489 #endif
490 
virtual bool empty()
Test for an empty tree.
int * newBound_
New bound.
Definition: CbcTree.hpp:216
int getNumberBranching() const
Get number of branches.
Definition: CbcTree.hpp:151
CbcNode * bestAlternate()
Get best on list using alternate method.
double lastObjective_
Objective of last node pushed on tree.
Definition: CbcTree.hpp:205
virtual int size() const
Return size.
Definition: CbcTree.hpp:109
CbcTree()
Default Constructor.
virtual void push(CbcNode *x)
Add a node to the heap.
double lastObjective() const
Last objective in branch-and-cut search tree.
Definition: CbcTree.hpp:166
int maximumBranching_
Maximum size of variable list.
Definition: CbcTree.hpp:203
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:214
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 &quot;node&quot; number so far to split ties.
Definition: CbcTree.hpp:199
void realpop()
virtual CbcNode * bestNode(double cutoff)
Gets best node and takes off heap.
int lastDepth_
Depth of last node pushed on tree.
Definition: CbcTree.hpp:207
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.
int lastUnsatisfied_
Number unsatisfied of last node pushed on tree.
Definition: CbcTree.hpp:209
int lastUnsatisfied() const
Last number of objects unsatisfied.
Definition: CbcTree.hpp:174
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:195
void resetNodeNumbers()
Reset maximum node number.
Definition: CbcTree.hpp:142
int numberBranching_
Size of variable list.
Definition: CbcTree.hpp:201
CbcCompare comparison_
Sort predicate for heap ordering.
Definition: CbcTree.hpp:197
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:101
void setMaximumBranching(int value)
Set maximum branches.
Definition: CbcTree.hpp:154
int lastDepth() const
Last depth in branch-and-cut search tree.
Definition: CbcTree.hpp:170