Changeset 724

Timestamp:

Aug 8, 2007 5:46:15 AM (12 years ago)

Author:

forrest

Message:

try and fix heap problem

Location:

trunk/Cbc/src

Files:

• CbcCompareActual.cpp (modified) (3 diffs)
• CbcCompareBase.hpp (modified) (2 diffs)
• CbcHeuristic.cpp (modified) (1 diff)
• CbcModel.cpp (modified) (7 diffs)
• CbcSolver.cpp (modified) (11 diffs)
• CbcStrategy.cpp (modified) (1 diff)
• CbcTree.cpp (modified) (4 diffs)
• CbcTree.hpp (modified) (3 diffs)

trunk/Cbc/src/CbcCompareActual.cpp

@@ -243 +243 @@
   }
 #else
-  if ((weight_==-1.0&&(y->depth()>breadthDepth_||x->depth()>breadthDepth_))||weight_==-3.0) {
+  if ((weight_==-1.0&&(y->depth()>breadthDepth_&&x->depth()>breadthDepth_))||weight_==-3.0||weight_==-2.0) {
     int adjust =  (weight_==-3.0) ? 10000 : 0;
     // before solution
@@ -265 +265 @@
     int depthX = x->depth();
     int depthY = y->depth();
+    /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
+      printf("X %x depth %d, Y %x depth %d, breadth %d\n",
+      x,depthX,y,depthY,breadthDepth_);*/
     if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
       if (depthX<=breadthDepth_&&depthY<=breadthDepth_) {
@@ -271 +274 @@
         }
       } else {
-        if (depthX!=depthY) {
-          return depthX > depthY;
-        }
+        assert (depthX!=depthY) ;
+        return depthX > depthY;
       }
     }

trunk/Cbc/src/CbcCompareBase.hpp

@@ -62 +62 @@
 
   /// Clone
-  virtual CbcCompareBase * clone() const=0;
+  virtual CbcCompareBase * clone() const
+  { abort(); return NULL;}
 
   /// This is test function
@@ -107 +108 @@
     return test_->test(x,y);
   }
+  bool compareNodes (CbcNode * x, CbcNode * y) {
+    return test_->test(x,y);
+  }
   /// This is alternate test function
   inline bool alternateTest (CbcNode * x, CbcNode * y) {return test_->alternateTest(x,y);}

trunk/Cbc/src/CbcHeuristic.cpp

@@ -189 +189 @@
       }
 #endif
+      model.setMaximumCutPassesAtRoot(CoinMin(20,model_->getMaximumCutPassesAtRoot()));
+      model.setParentModel(*model_);
       model.branchAndBound();
       if (logLevel>1)

trunk/Cbc/src/CbcModel.cpp

@@ -1577 +1577 @@
 */
     totalTime = getCurrentSeconds() ;
+    double maxSeconds = getMaximumSeconds();
+    if (parentModel_)
+      maxSeconds=CoinMin(maxSeconds,parentModel_->getMaximumSeconds());
     if (!(numberNodes_ < intParam_[CbcMaxNumNode] &&
           numberSolutions_ < intParam_[CbcMaxNumSol] &&
-          totalTime < dblParam_[CbcMaximumSeconds] &&
+          totalTime < maxSeconds &&
           !stoppedOnGap_&&!eventHappened_)) {
       // out of loop
@@ -3665 +3668 @@
   return *this;
 }
-  
 // Destructor 
 CbcModel::~CbcModel ()
@@ -4790 +4792 @@
         int numberRowCutsBefore = theseCuts.sizeRowCuts() ;
         int numberColumnCutsBefore = theseCuts.sizeColCuts() ;
+        int numberRowCutsAfter = numberRowCutsBefore;
+        int numberColumnCutsAfter = numberColumnCutsBefore;
         bool generate = generator_[i]->normal();
         // skip if not optimal and should be (maybe a cut generator has fixed variables)
@@ -4799 +4803 @@
           bool mustResolve = 
             generator_[i]->generateCuts(theseCuts,fullScan,solver_,node) ;
-          int numberRowCutsAfter = theseCuts.sizeRowCuts() ;
+          numberRowCutsAfter = theseCuts.sizeRowCuts() ;
           if(numberRowCutsBefore < numberRowCutsAfter &&
              generator_[i]->mustCallAgain())
@@ -4848 +4852 @@
           }
         }
-        int numberRowCutsAfter = theseCuts.sizeRowCuts() ;
-        int numberColumnCutsAfter = theseCuts.sizeColCuts() ;
+        numberRowCutsAfter = theseCuts.sizeRowCuts() ;
+        numberColumnCutsAfter = theseCuts.sizeColCuts() ;
         
         if ((specialOptions_&1)!=0) {
@@ -4942 +4946 @@
       // Add in any violated saved cuts
       if (!theseCuts.sizeRowCuts()&&!theseCuts.sizeColCuts()) {
-        int numberOld = theseCuts.sizeRowCuts();
+        int numberOld = theseCuts.sizeRowCuts()+lastNumberCuts;
         int numberCuts = slackCuts.sizeRowCuts() ;
         int i;
@@ -5176 +5180 @@
       // Add in any violated saved cuts
       if (!theseCuts.sizeRowCuts()&&!theseCuts.sizeColCuts()) {
-        int numberOld = theseCuts.sizeRowCuts();
+        int numberOld = theseCuts.sizeRowCuts()+lastNumberCuts;
         int numberCuts = slackCuts.sizeRowCuts() ;
         int i;

trunk/Cbc/src/CbcSolver.cpp

@@ -163 +163 @@
    static void signal_handler(int whichSignal)
    {
-      if (currentBranchModel!=NULL) 
-         currentBranchModel->setMaximumNodes(0); // stop at next node
-      return;
+     if (currentBranchModel!=NULL) {
+       currentBranchModel->setMaximumNodes(0); // stop at next node
+       currentBranchModel->setMaximumSeconds(0.0); // stop 
+     }
+     return;
    }
 }
@@ -2035 +2037 @@
                 break;
               default:
-                abort();
+                break;
               }
             }
@@ -2923 +2925 @@
                       heuristicFPump.setHeuristicName("feasibility pump");
                       heuristicFPump.setInitialWeight(1);
+                      heuristicFPump.setFractionSmall(0.6);
                       cbcModel->addHeuristic(&heuristicFPump);
                       
@@ -2932 +2935 @@
                       heuristicLocal.setHeuristicName("combine solutions");
                       heuristicLocal.setSearchType(1);
+                      heuristicLocal.setFractionSmall(0.6);
                       cbcModel->addHeuristic(&heuristicLocal);
                       
@@ -3503 +3507 @@
               // FPump done first as it only works if no solution
               CbcHeuristicFPump heuristic4(*babModel);
+              heuristic4.setFractionSmall(0.6);
               if (useFpump) {
                 heuristic4.setMaximumPasses(parameters[whichParam(FPUMPITS,numberParameters,parameters)].intValue());
@@ -3544 +3549 @@
                     babModel->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
                     cutoff = CoinMin(cutoff,value + 0.1*fabs(value)*c);
+                    double dextra1 = parameters[whichParam(DEXTRA1,numberParameters,parameters)].doubleValue();
+                    if (dextra1)
+                      cutoff=dextra1;
                     heuristic4.setFakeCutoff(cutoff);
                     if (logLevel>1)
@@ -3550 +3558 @@
                   if (i||r) {
                     // also set increment
-                    heuristic4.setAbsoluteIncrement((0.01*i+0.005)*(fabs(value)+1.0e-12));
+                    double increment = (0.01*i+0.005)*(fabs(value)+1.0e-12);
+                    double dextra2 = parameters[whichParam(DEXTRA2,numberParameters,parameters)].doubleValue();
+                    if (dextra2)
+                      increment = dextra2;
+                    heuristic4.setAbsoluteIncrement(increment);
                     heuristic4.setAccumulate(accumulate);
                     heuristic4.setMaximumRetries(r+1);
@@ -3578 +3590 @@
                 CbcHeuristicLocal heuristic2(*babModel);
                 heuristic2.setHeuristicName("combine solutions");
+                heuristic2.setFractionSmall(0.6);
                 heuristic2.setSearchType(1);
                 if (useCombine)
@@ -3596 +3609 @@
               CbcHeuristicRINS heuristic5(*babModel);
               heuristic5.setHeuristicName("RINS");
+              heuristic5.setFractionSmall(0.6);
               if (useRINS)
                 babModel->addHeuristic(&heuristic5) ;
@@ -4285 +4299 @@
                 if (nodeStrategy) {
                   // change default
-                  if (nodeStrategy>1) {
+                  if (nodeStrategy>2) {
                     // up or down
-                    int way = ((nodeStrategy%1)==1) ? -1 : +1;
+                    int way = (((nodeStrategy-1)%1)==1) ? -1 : +1;
                     babModel->setPreferredWay(way);
 #if 0
@@ -4300 +4314 @@
 #endif
                   }
-                  if (nodeStrategy==1||nodeStrategy>3) {
+                  if (nodeStrategy==2||nodeStrategy>4) {
                     // depth
                     CbcCompareDefault compare;
                     compare.setWeight(-3.0);
+                    babModel->setNodeComparison(compare);
+                  } else if (nodeStrategy==0) {
+                    // hybrid was default i.e. mixture of low depth and infeasibility
+                  } else if (nodeStrategy==1) {
+                    // real fewest
+                    CbcCompareDefault compare;
+                    compare.setWeight(-2.0);
                     babModel->setNodeComparison(compare);
                   }

trunk/Cbc/src/CbcStrategy.cpp

@@ -616 +616 @@
       }
     }
-    if (!found)
+    if (!found) 
       model.addCutGenerator(&generator1,setting,"Probing");
   }

trunk/Cbc/src/CbcTree.cpp

@@ -6 +6 @@
 #include "CbcTree.hpp"
 #include "CbcCountRowCut.hpp"
+#include "CbcCompareActual.hpp"
 
 CbcTree::CbcTree()
@@ -33 +34 @@
   return new CbcTree(*this);
 }
+//#define CBC_DEBUG_HEAP
+#ifndef CBC_DUBIOUS_HEAP 
 // Set comparison function and resort heap
 void 
@@ -127 +130 @@
     nodes_.pop_back();
   }
+#ifdef DEBUG_CBC_HEAP
+  if (best) {
+    int n=nodes_.size();
+    bool good=true;
+    for (int i=0;i<n;i++) {
+      // temp
+      assert (nodes_[i]);
+      if (!comparison_.compareNodes(nodes_[i],best)) {
+        good=false;
+        CbcNode * x = nodes_[i];
+        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
+               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
+               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
+      }
+    }
+    if (!good) {
+      // compare best to all
+      int i;
+      for (i=0;i<n;i++) {
+        CbcNode * x = nodes_[i];
+        printf("i=%d x is nun %d depth %d obj %g",i,
+               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
+        if (!comparison_.compareNodes(x,best)) {
+          printf(" - best is worse!\n");
+        } else {
+          printf("\n");
+        }
+      }
+      // Now compare amongst rest
+      for (i=0;i<n;i++) {
+        CbcNode * x = nodes_[i];
+        printf("For i=%d ",i);
+        for (int j=i+1;j<n;j++) {
+          CbcNode * y = nodes_[j];
+          if (!comparison_.compareNodes(x,y)) {
+            printf(" b %d",j);
+          } else {
+            printf(" w %d",j);
+          }
+        }
+        printf("\n");
+      }
+      assert(good);
+    }
+  }
+#endif
   return best;
 }
@@ -241 +290 @@
   return best;
 }
-
+#else
+// Set comparison function and resort heap
+void 
+CbcTree::setComparison(CbcCompareBase  &compare)
+{
+  comparison_.test_ = &compare;
+  std::vector <CbcNode *> newNodes=nodes_;
+  nodes_.resize(0);
+  while (newNodes.size()>0) {
+    push( newNodes.back());
+    newNodes.pop_back();
+  }
+}
+
+// Return the top node of the heap 
+CbcNode * 
+CbcTree::top() const
+{
+  return nodes_.front();
+}
+
+// Add a node to the heap
+void 
+CbcTree::push(CbcNode * x) {
+  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
+         x->objectiveValue(),x->nodeInfo()->decrement(0),
+         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
+  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
+#if 0
+  nodes_.push_back(x);
+  push_heap(nodes_.begin(), nodes_.end(), comparison_);
+#else
+  realpush(x);
+#endif
+}
+
+// Remove the top node from the heap
+void 
+CbcTree::pop() {
+#if 0
+  pop_heap(nodes_.begin(), nodes_.end(), comparison_);
+  nodes_.pop_back();
+#else
+  if (nodes_.size()) {
+    //CbcNode* s = nodes_.front();
+    realpop();
+    //delete s;
+  }
+  assert (nodes_.size()>=0);
+#endif
+}
+
+// Test if empty *** note may be overridden
+bool 
+CbcTree::empty() 
+{ 
+  return nodes_.empty();
+}
+// Gets best node and takes off heap
+CbcNode * 
+CbcTree::bestNode(double cutoff)
+{
+  CbcNode * best = NULL;
+  while (!best&&nodes_.size()) {
+    best = nodes_.front();
+    if (best)
+      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
+    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
+      assert (best->nodeInfo()->numberBranchesLeft());
+    if (!best||best->objectiveValue()>=cutoff) {
+#if 0
+      // take off
+      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
+      nodes_.pop_back();
+      delete best;
+      best=NULL;
+#else
+      // let code get rid of it
+      assert (best);
+#endif
+    }
+  }
+  // switched off for now
+  if (best&&comparison_.test_->fullScan()&&false) {
+    CbcNode * saveBest=best;
+    int n=nodes_.size();
+    int iBest=-1;
+    for (int i=0;i<n;i++) {
+      // temp
+      assert (nodes_[i]);
+      assert (nodes_[i]->nodeInfo());
+      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
+        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
+      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
+          &&comparison_.alternateTest(best,nodes_[i])) {
+        best=nodes_[i];
+        iBest=i;
+      }
+    }
+    if (best==saveBest) {
+      // can pop
+      // take off
+      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
+      nodes_.pop_back();
+    } else {
+      // make impossible
+      nodes_[iBest]=NULL;
+    }
+  } else if (best) {
+    // take off
+#if 0
+    pop_heap(nodes_.begin(), nodes_.end(), comparison_);
+    nodes_.pop_back();
+#else
+    realpop();
+#endif
+  }
+#ifdef DEBUG_CBC_HEAP
+  if (best) {
+    int n=nodes_.size();
+    bool good=true;
+    for (int i=0;i<n;i++) {
+      // temp
+      assert (nodes_[i]);
+      if (!comparison_.compareNodes(nodes_[i],best)) {
+        good=false;
+        CbcNode * x = nodes_[i];
+        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
+               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
+               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
+      }
+    }
+    if (!good) {
+      // compare best to all
+      int i;
+      for (i=0;i<n;i++) {
+        CbcNode * x = nodes_[i];
+        printf("i=%d x is nun %d depth %d obj %g",i,
+               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
+        if (!comparison_.compareNodes(x,best)) {
+          printf(" - best is worse!\n");
+        } else {
+          printf("\n");
+        }
+      }
+      // Now compare amongst rest
+      for (i=0;i<n;i++) {
+        CbcNode * x = nodes_[i];
+        printf("For i=%d ",i);
+        for (int j=i+1;j<n;j++) {
+          CbcNode * y = nodes_[j];
+          if (!comparison_.compareNodes(x,y)) {
+            printf(" b %d",j);
+          } else {
+            printf(" w %d",j);
+          }
+        }
+        printf("\n");
+      }
+      assert(good);
+    }
+  }
+#endif
+  return best;
+}
+
+/*! \brief Prune the tree using an objective function cutoff
+
+  This routine removes all nodes with objective worst than the
+  specified cutoff value.
+*/
+
+void 
+CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
+{
+  int j;
+  int nNodes = nodes_.size();
+  CbcNode ** nodeArray = new CbcNode * [nNodes];
+  int * depth = new int [nNodes];
+  int k=0;
+  int kDelete=nNodes;
+  bestPossibleObjective = 1.0e100 ;
+/*
+    Destructively scan the heap. Nodes to be retained go into the front of
+    nodeArray, nodes to be deleted into the back. Store the depth in a
+    correlated array for nodes to be deleted.
+*/
+  for (j=0;j<nNodes;j++) {
+    CbcNode * node = top();
+    pop();
+    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
+    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
+    if (value >= cutoff) {
+      if (node) {
+        nodeArray[--kDelete] = node;
+        depth[kDelete] = node->depth();
+      }
+    } else {
+      nodeArray[k++]=node;
+    }
+  }
+/*
+  Rebuild the heap using the retained nodes.
+*/
+  for (j=0;j<k;j++) { push(nodeArray[j]); }
+/*
+  Sort the list of nodes to be deleted, nondecreasing.
+*/
+  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
+/*
+  Work back from deepest to shallowest. In spite of the name, addCuts1 is
+  just a preparatory step. When it returns, the following will be true:
+    * all cuts are removed from the solver's copy of the constraint system;
+    * lastws will be a basis appropriate for the specified node;
+    * variable bounds will be adjusted to be appropriate for the specified
+      node;
+    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
+      should be added to the constraint system at this node (but they have
+      not actually been added).
+  Then we scan the cut list for the node. Decrement the reference count
+  for the cut, and if it's gone to 0, really delete it.
+
+  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
+  are necessary. When reconstructing a node, these checks are used to skip
+  over loose cuts, excluding them from the reconstituted basis. But here
+  we're just interested in correcting the reference count. Tight/loose should
+  make no difference.
+
+  Arguably a separate routine should be used in place of addCuts1. It's doing
+  more work than needed, modifying the model to match a subproblem at a node
+  that will be discarded.  Then again, we seem to need the basis.
+*/
+  for (j=nNodes-1;j >= kDelete;j--) {
+    CbcNode * node = nodeArray[j];
+    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
+    
+    model->addCuts1(node,lastws);
+    // Decrement cut counts 
+    assert (node);
+    //assert (node->nodeInfo());
+    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
+    int i;
+    for (i=0;i<model->currentNumberCuts();i++) {
+      // take off node
+      CoinWarmStartBasis::Status status = 
+        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
+      if (status != CoinWarmStartBasis::basic&&
+          model->addedCuts()[i]) {
+        if (!model->addedCuts()[i]->decrement(numberLeft))
+          delete model->addedCuts()[i];
+      }
+    }
+    // node should not have anything pointing to it
+    if (node->nodeInfo())   
+      node->nodeInfo()->throwAway();
+    delete node ;
+    delete lastws ;
+  }
+  delete [] nodeArray;
+  delete [] depth;
+}
+
+// Return the best node of the heap using alternate criterion
+CbcNode * 
+CbcTree::bestAlternate() {
+  int n=nodes_.size();
+  CbcNode * best=NULL;
+  if (n) {
+    best = nodes_[0];
+    for (int i=1;i<n;i++) {
+      if (comparison_.alternateTest(best,nodes_[i])) {
+        best=nodes_[i];
+      }
+    }
+  }
+  return best;
+}
+void 
+CbcTree::realpop() {
+  if (nodes_.size()>0) {
+    nodes_[0] = nodes_.back();
+    nodes_.pop_back();
+    fixTop();
+  }
+  assert (nodes_.size()>=0);
+}
+/* After changing data in the top node, fix the heap */
+void 
+CbcTree::fixTop() {
+  const int size = nodes_.size();
+  if (size > 1) {
+    CbcNode** candidates = &nodes_[0];
+    CbcNode* s = candidates[0];
+    --candidates;
+    int pos = 1;
+    int ch;
+    for (ch = 2; ch < size; pos = ch, ch *= 2) {
+      if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
+        ++ch;
+      if (!comparison_.compareNodes(s, candidates[ch]))
+        break;
+      candidates[pos] = candidates[ch];
+    }
+    if (ch == size) {
+      if (!comparison_.compareNodes(candidates[ch], s)) {
+        candidates[pos] = candidates[ch];
+        pos = ch;
+      }
+    }
+    candidates[pos] = s;
+  }
+}
+void 
+CbcTree::realpush(CbcNode * node) {
+  nodes_.push_back(node);
+  CbcNode** candidates = &nodes_[0];
+  --candidates;
+  int pos = nodes_.size();
+  int ch;
+  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
+    if (!comparison_.compareNodes(candidates[ch], node))
+      break;
+    candidates[pos] = candidates[ch];
+  }
+  candidates[pos] = node;
+}
+#endif

trunk/Cbc/src/CbcTree.hpp

@@ -7 +7 @@
 
 #include <vector>
+#include <algorithm>
+#include <cmath>
+
+#include "CoinFinite.hpp"
+#include "CoinHelperFunctions.hpp"
 
 /*! \class tree
@@ -13 +18 @@
     This class is used to hold the set of live nodes in the search tree.
 */
-
+//#define CBC_DUBIOUS_HEAP
+#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
+//#define CBC_DUBIOUS_HEAP
+#endif
+#ifndef CBC_DUBIOUS_HEAP 
 class CbcTree {
 
@@ -185 +194 @@
 
 };
+#else
+class CbcTree {
+
+public:
+
+  // Default Constructor 
+  CbcTree ();
+
+  // Copy constructor 
+  CbcTree ( const CbcTree & rhs);
+  // = operator
+  CbcTree & operator=(const CbcTree & rhs);
+   
+  virtual ~CbcTree();
+
+  /// Clone
+  virtual CbcTree * clone() const;
+  /// Create C++ lines to get to current state
+  virtual void generateCpp( FILE * fp) {}
+
+/*! \name Heap access and maintenance methods */
+//@{
+
+  /// Set comparison function and resort heap
+  void setComparison(CbcCompareBase  &compare);
+
+  /// Return the top node of the heap 
+  virtual CbcNode * top() const;
+
+  /// Add a node to the heap
+  virtual void push(CbcNode * x);
+
+  /// Remove the top node from the heap
+  virtual void pop() ;
+  /// Gets best node and takes off heap
+  virtual CbcNode * bestNode(double cutoff);
+
+//@}
+/*! \name vector methods */
+//@{
+
+  /// Test if empty *** note may be overridden
+  //virtual bool empty() ;
+
+  /// Return size
+  inline int size() const
+  { return nodes_.size();}
+
+  /// [] operator
+  inline CbcNode * operator [] (int i) const
+  { return nodes_[i];}
+
+  /// Return a node pointer
+  inline CbcNode * nodePointer (int i) const
+  { return nodes_[i];}
+  
+  virtual bool empty();
+  //inline int size() const { return size_; }
+  void realpop();
+  /** After changing data in the top node, fix the heap */
+  void fixTop();
+  void realpush(CbcNode * node);
+//@}
+
+/*! \name Search tree maintenance */
+//@{
+
+/*! \brief Prune the tree using an objective function cutoff
+
+  This routine removes all nodes with objective worst than the
+  specified cutoff value.
+  It also sets bestPossibleObjective to best
+  of all on tree before deleting.
+*/
+
+  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
+
+  /// Get best on list using alternate method
+  CbcNode * bestAlternate();
+
+  /// We may have got an intelligent tree so give it one more chance
+  virtual void endSearch() {}
+//@}
+protected:
+  std::vector <CbcNode *> nodes_;
+  CbcCompare comparison_;       ///> Sort function for heap ordering.
+
+
+};
 #endif
-
+#endif
+