Changeset 724 for trunk


Ignore:
Timestamp:
Aug 8, 2007 5:46:15 AM (12 years ago)
Author:
forrest
Message:

try and fix heap problem

Location:
trunk/Cbc/src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcCompareActual.cpp

    r640 r724  
    243243  }
    244244#else
    245   if ((weight_==-1.0&&(y->depth()>breadthDepth_||x->depth()>breadthDepth_))||weight_==-3.0) {
     245  if ((weight_==-1.0&&(y->depth()>breadthDepth_&&x->depth()>breadthDepth_))||weight_==-3.0||weight_==-2.0) {
    246246    int adjust =  (weight_==-3.0) ? 10000 : 0;
    247247    // before solution
     
    265265    int depthX = x->depth();
    266266    int depthY = y->depth();
     267    /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
     268      printf("X %x depth %d, Y %x depth %d, breadth %d\n",
     269      x,depthX,y,depthY,breadthDepth_);*/
    267270    if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
    268271      if (depthX<=breadthDepth_&&depthY<=breadthDepth_) {
     
    271274        }
    272275      } else {
    273         if (depthX!=depthY) {
    274           return depthX > depthY;
    275         }
     276        assert (depthX!=depthY) ;
     277        return depthX > depthY;
    276278      }
    277279    }
  • trunk/Cbc/src/CbcCompareBase.hpp

    r706 r724  
    6262
    6363  /// Clone
    64   virtual CbcCompareBase * clone() const=0;
     64  virtual CbcCompareBase * clone() const
     65  { abort(); return NULL;}
    6566
    6667  /// This is test function
     
    107108    return test_->test(x,y);
    108109  }
     110  bool compareNodes (CbcNode * x, CbcNode * y) {
     111    return test_->test(x,y);
     112  }
    109113  /// This is alternate test function
    110114  inline bool alternateTest (CbcNode * x, CbcNode * y) {return test_->alternateTest(x,y);}
  • trunk/Cbc/src/CbcHeuristic.cpp

    r715 r724  
    189189      }
    190190#endif
     191      model.setMaximumCutPassesAtRoot(CoinMin(20,model_->getMaximumCutPassesAtRoot()));
     192      model.setParentModel(*model_);
    191193      model.branchAndBound();
    192194      if (logLevel>1)
  • trunk/Cbc/src/CbcModel.cpp

    r722 r724  
    15771577*/
    15781578    totalTime = getCurrentSeconds() ;
     1579    double maxSeconds = getMaximumSeconds();
     1580    if (parentModel_)
     1581      maxSeconds=CoinMin(maxSeconds,parentModel_->getMaximumSeconds());
    15791582    if (!(numberNodes_ < intParam_[CbcMaxNumNode] &&
    15801583          numberSolutions_ < intParam_[CbcMaxNumSol] &&
    1581           totalTime < dblParam_[CbcMaximumSeconds] &&
     1584          totalTime < maxSeconds &&
    15821585          !stoppedOnGap_&&!eventHappened_)) {
    15831586      // out of loop
     
    36653668  return *this;
    36663669}
    3667  
    36683670// Destructor
    36693671CbcModel::~CbcModel ()
     
    47904792        int numberRowCutsBefore = theseCuts.sizeRowCuts() ;
    47914793        int numberColumnCutsBefore = theseCuts.sizeColCuts() ;
     4794        int numberRowCutsAfter = numberRowCutsBefore;
     4795        int numberColumnCutsAfter = numberColumnCutsBefore;
    47924796        bool generate = generator_[i]->normal();
    47934797        // skip if not optimal and should be (maybe a cut generator has fixed variables)
     
    47994803          bool mustResolve =
    48004804            generator_[i]->generateCuts(theseCuts,fullScan,solver_,node) ;
    4801           int numberRowCutsAfter = theseCuts.sizeRowCuts() ;
     4805          numberRowCutsAfter = theseCuts.sizeRowCuts() ;
    48024806          if(numberRowCutsBefore < numberRowCutsAfter &&
    48034807             generator_[i]->mustCallAgain())
     
    48484852          }
    48494853        }
    4850         int numberRowCutsAfter = theseCuts.sizeRowCuts() ;
    4851         int numberColumnCutsAfter = theseCuts.sizeColCuts() ;
     4854        numberRowCutsAfter = theseCuts.sizeRowCuts() ;
     4855        numberColumnCutsAfter = theseCuts.sizeColCuts() ;
    48524856       
    48534857        if ((specialOptions_&1)!=0) {
     
    49424946      // Add in any violated saved cuts
    49434947      if (!theseCuts.sizeRowCuts()&&!theseCuts.sizeColCuts()) {
    4944         int numberOld = theseCuts.sizeRowCuts();
     4948        int numberOld = theseCuts.sizeRowCuts()+lastNumberCuts;
    49454949        int numberCuts = slackCuts.sizeRowCuts() ;
    49464950        int i;
     
    51765180      // Add in any violated saved cuts
    51775181      if (!theseCuts.sizeRowCuts()&&!theseCuts.sizeColCuts()) {
    5178         int numberOld = theseCuts.sizeRowCuts();
     5182        int numberOld = theseCuts.sizeRowCuts()+lastNumberCuts;
    51795183        int numberCuts = slackCuts.sizeRowCuts() ;
    51805184        int i;
  • trunk/Cbc/src/CbcSolver.cpp

    r723 r724  
    163163   static void signal_handler(int whichSignal)
    164164   {
    165       if (currentBranchModel!=NULL)
    166          currentBranchModel->setMaximumNodes(0); // stop at next node
    167       return;
     165     if (currentBranchModel!=NULL) {
     166       currentBranchModel->setMaximumNodes(0); // stop at next node
     167       currentBranchModel->setMaximumSeconds(0.0); // stop
     168     }
     169     return;
    168170   }
    169171}
     
    20352037                break;
    20362038              default:
    2037                 abort();
     2039                break;
    20382040              }
    20392041            }
     
    29232925                      heuristicFPump.setHeuristicName("feasibility pump");
    29242926                      heuristicFPump.setInitialWeight(1);
     2927                      heuristicFPump.setFractionSmall(0.6);
    29252928                      cbcModel->addHeuristic(&heuristicFPump);
    29262929                     
     
    29322935                      heuristicLocal.setHeuristicName("combine solutions");
    29332936                      heuristicLocal.setSearchType(1);
     2937                      heuristicLocal.setFractionSmall(0.6);
    29342938                      cbcModel->addHeuristic(&heuristicLocal);
    29352939                     
     
    35033507              // FPump done first as it only works if no solution
    35043508              CbcHeuristicFPump heuristic4(*babModel);
     3509              heuristic4.setFractionSmall(0.6);
    35053510              if (useFpump) {
    35063511                heuristic4.setMaximumPasses(parameters[whichParam(FPUMPITS,numberParameters,parameters)].intValue());
     
    35443549                    babModel->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
    35453550                    cutoff = CoinMin(cutoff,value + 0.1*fabs(value)*c);
     3551                    double dextra1 = parameters[whichParam(DEXTRA1,numberParameters,parameters)].doubleValue();
     3552                    if (dextra1)
     3553                      cutoff=dextra1;
    35463554                    heuristic4.setFakeCutoff(cutoff);
    35473555                    if (logLevel>1)
     
    35503558                  if (i||r) {
    35513559                    // also set increment
    3552                     heuristic4.setAbsoluteIncrement((0.01*i+0.005)*(fabs(value)+1.0e-12));
     3560                    double increment = (0.01*i+0.005)*(fabs(value)+1.0e-12);
     3561                    double dextra2 = parameters[whichParam(DEXTRA2,numberParameters,parameters)].doubleValue();
     3562                    if (dextra2)
     3563                      increment = dextra2;
     3564                    heuristic4.setAbsoluteIncrement(increment);
    35533565                    heuristic4.setAccumulate(accumulate);
    35543566                    heuristic4.setMaximumRetries(r+1);
     
    35783590                CbcHeuristicLocal heuristic2(*babModel);
    35793591                heuristic2.setHeuristicName("combine solutions");
     3592                heuristic2.setFractionSmall(0.6);
    35803593                heuristic2.setSearchType(1);
    35813594                if (useCombine)
     
    35963609              CbcHeuristicRINS heuristic5(*babModel);
    35973610              heuristic5.setHeuristicName("RINS");
     3611              heuristic5.setFractionSmall(0.6);
    35983612              if (useRINS)
    35993613                babModel->addHeuristic(&heuristic5) ;
     
    42854299                if (nodeStrategy) {
    42864300                  // change default
    4287                   if (nodeStrategy>1) {
     4301                  if (nodeStrategy>2) {
    42884302                    // up or down
    4289                     int way = ((nodeStrategy%1)==1) ? -1 : +1;
     4303                    int way = (((nodeStrategy-1)%1)==1) ? -1 : +1;
    42904304                    babModel->setPreferredWay(way);
    42914305#if 0
     
    43004314#endif
    43014315                  }
    4302                   if (nodeStrategy==1||nodeStrategy>3) {
     4316                  if (nodeStrategy==2||nodeStrategy>4) {
    43034317                    // depth
    43044318                    CbcCompareDefault compare;
    43054319                    compare.setWeight(-3.0);
     4320                    babModel->setNodeComparison(compare);
     4321                  } else if (nodeStrategy==0) {
     4322                    // hybrid was default i.e. mixture of low depth and infeasibility
     4323                  } else if (nodeStrategy==1) {
     4324                    // real fewest
     4325                    CbcCompareDefault compare;
     4326                    compare.setWeight(-2.0);
    43064327                    babModel->setNodeComparison(compare);
    43074328                  }
  • trunk/Cbc/src/CbcStrategy.cpp

    r640 r724  
    616616      }
    617617    }
    618     if (!found)
     618    if (!found) 
    619619      model.addCutGenerator(&generator1,setting,"Probing");
    620620  }
  • trunk/Cbc/src/CbcTree.cpp

    r687 r724  
    66#include "CbcTree.hpp"
    77#include "CbcCountRowCut.hpp"
     8#include "CbcCompareActual.hpp"
    89
    910CbcTree::CbcTree()
     
    3334  return new CbcTree(*this);
    3435}
     36//#define CBC_DEBUG_HEAP
     37#ifndef CBC_DUBIOUS_HEAP
    3538// Set comparison function and resort heap
    3639void
     
    127130    nodes_.pop_back();
    128131  }
     132#ifdef DEBUG_CBC_HEAP
     133  if (best) {
     134    int n=nodes_.size();
     135    bool good=true;
     136    for (int i=0;i<n;i++) {
     137      // temp
     138      assert (nodes_[i]);
     139      if (!comparison_.compareNodes(nodes_[i],best)) {
     140        good=false;
     141        CbcNode * x = nodes_[i];
     142        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
     143               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
     144               best->numberUnsatisfied(),best->depth(),best->objectiveValue());
     145      }
     146    }
     147    if (!good) {
     148      // compare best to all
     149      int i;
     150      for (i=0;i<n;i++) {
     151        CbcNode * x = nodes_[i];
     152        printf("i=%d x is nun %d depth %d obj %g",i,
     153               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
     154        if (!comparison_.compareNodes(x,best)) {
     155          printf(" - best is worse!\n");
     156        } else {
     157          printf("\n");
     158        }
     159      }
     160      // Now compare amongst rest
     161      for (i=0;i<n;i++) {
     162        CbcNode * x = nodes_[i];
     163        printf("For i=%d ",i);
     164        for (int j=i+1;j<n;j++) {
     165          CbcNode * y = nodes_[j];
     166          if (!comparison_.compareNodes(x,y)) {
     167            printf(" b %d",j);
     168          } else {
     169            printf(" w %d",j);
     170          }
     171        }
     172        printf("\n");
     173      }
     174      assert(good);
     175    }
     176  }
     177#endif
    129178  return best;
    130179}
     
    241290  return best;
    242291}
    243 
     292#else
     293// Set comparison function and resort heap
     294void
     295CbcTree::setComparison(CbcCompareBase  &compare)
     296{
     297  comparison_.test_ = &compare;
     298  std::vector <CbcNode *> newNodes=nodes_;
     299  nodes_.resize(0);
     300  while (newNodes.size()>0) {
     301    push( newNodes.back());
     302    newNodes.pop_back();
     303  }
     304}
     305
     306// Return the top node of the heap
     307CbcNode *
     308CbcTree::top() const
     309{
     310  return nodes_.front();
     311}
     312
     313// Add a node to the heap
     314void
     315CbcTree::push(CbcNode * x) {
     316  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
     317         x->objectiveValue(),x->nodeInfo()->decrement(0),
     318         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
     319  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
     320#if 0
     321  nodes_.push_back(x);
     322  push_heap(nodes_.begin(), nodes_.end(), comparison_);
     323#else
     324  realpush(x);
     325#endif
     326}
     327
     328// Remove the top node from the heap
     329void
     330CbcTree::pop() {
     331#if 0
     332  pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     333  nodes_.pop_back();
     334#else
     335  if (nodes_.size()) {
     336    //CbcNode* s = nodes_.front();
     337    realpop();
     338    //delete s;
     339  }
     340  assert (nodes_.size()>=0);
     341#endif
     342}
     343
     344// Test if empty *** note may be overridden
     345bool
     346CbcTree::empty()
     347{
     348  return nodes_.empty();
     349}
     350// Gets best node and takes off heap
     351CbcNode *
     352CbcTree::bestNode(double cutoff)
     353{
     354  CbcNode * best = NULL;
     355  while (!best&&nodes_.size()) {
     356    best = nodes_.front();
     357    if (best)
     358      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
     359    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
     360      assert (best->nodeInfo()->numberBranchesLeft());
     361    if (!best||best->objectiveValue()>=cutoff) {
     362#if 0
     363      // take off
     364      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     365      nodes_.pop_back();
     366      delete best;
     367      best=NULL;
     368#else
     369      // let code get rid of it
     370      assert (best);
     371#endif
     372    }
     373  }
     374  // switched off for now
     375  if (best&&comparison_.test_->fullScan()&&false) {
     376    CbcNode * saveBest=best;
     377    int n=nodes_.size();
     378    int iBest=-1;
     379    for (int i=0;i<n;i++) {
     380      // temp
     381      assert (nodes_[i]);
     382      assert (nodes_[i]->nodeInfo());
     383      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
     384        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
     385      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
     386          &&comparison_.alternateTest(best,nodes_[i])) {
     387        best=nodes_[i];
     388        iBest=i;
     389      }
     390    }
     391    if (best==saveBest) {
     392      // can pop
     393      // take off
     394      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     395      nodes_.pop_back();
     396    } else {
     397      // make impossible
     398      nodes_[iBest]=NULL;
     399    }
     400  } else if (best) {
     401    // take off
     402#if 0
     403    pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     404    nodes_.pop_back();
     405#else
     406    realpop();
     407#endif
     408  }
     409#ifdef DEBUG_CBC_HEAP
     410  if (best) {
     411    int n=nodes_.size();
     412    bool good=true;
     413    for (int i=0;i<n;i++) {
     414      // temp
     415      assert (nodes_[i]);
     416      if (!comparison_.compareNodes(nodes_[i],best)) {
     417        good=false;
     418        CbcNode * x = nodes_[i];
     419        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
     420               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
     421               best->numberUnsatisfied(),best->depth(),best->objectiveValue());
     422      }
     423    }
     424    if (!good) {
     425      // compare best to all
     426      int i;
     427      for (i=0;i<n;i++) {
     428        CbcNode * x = nodes_[i];
     429        printf("i=%d x is nun %d depth %d obj %g",i,
     430               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
     431        if (!comparison_.compareNodes(x,best)) {
     432          printf(" - best is worse!\n");
     433        } else {
     434          printf("\n");
     435        }
     436      }
     437      // Now compare amongst rest
     438      for (i=0;i<n;i++) {
     439        CbcNode * x = nodes_[i];
     440        printf("For i=%d ",i);
     441        for (int j=i+1;j<n;j++) {
     442          CbcNode * y = nodes_[j];
     443          if (!comparison_.compareNodes(x,y)) {
     444            printf(" b %d",j);
     445          } else {
     446            printf(" w %d",j);
     447          }
     448        }
     449        printf("\n");
     450      }
     451      assert(good);
     452    }
     453  }
     454#endif
     455  return best;
     456}
     457
     458/*! \brief Prune the tree using an objective function cutoff
     459
     460  This routine removes all nodes with objective worst than the
     461  specified cutoff value.
     462*/
     463
     464void
     465CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
     466{
     467  int j;
     468  int nNodes = nodes_.size();
     469  CbcNode ** nodeArray = new CbcNode * [nNodes];
     470  int * depth = new int [nNodes];
     471  int k=0;
     472  int kDelete=nNodes;
     473  bestPossibleObjective = 1.0e100 ;
     474/*
     475    Destructively scan the heap. Nodes to be retained go into the front of
     476    nodeArray, nodes to be deleted into the back. Store the depth in a
     477    correlated array for nodes to be deleted.
     478*/
     479  for (j=0;j<nNodes;j++) {
     480    CbcNode * node = top();
     481    pop();
     482    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
     483    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
     484    if (value >= cutoff) {
     485      if (node) {
     486        nodeArray[--kDelete] = node;
     487        depth[kDelete] = node->depth();
     488      }
     489    } else {
     490      nodeArray[k++]=node;
     491    }
     492  }
     493/*
     494  Rebuild the heap using the retained nodes.
     495*/
     496  for (j=0;j<k;j++) { push(nodeArray[j]); }
     497/*
     498  Sort the list of nodes to be deleted, nondecreasing.
     499*/
     500  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
     501/*
     502  Work back from deepest to shallowest. In spite of the name, addCuts1 is
     503  just a preparatory step. When it returns, the following will be true:
     504    * all cuts are removed from the solver's copy of the constraint system;
     505    * lastws will be a basis appropriate for the specified node;
     506    * variable bounds will be adjusted to be appropriate for the specified
     507      node;
     508    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
     509      should be added to the constraint system at this node (but they have
     510      not actually been added).
     511  Then we scan the cut list for the node. Decrement the reference count
     512  for the cut, and if it's gone to 0, really delete it.
     513
     514  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
     515  are necessary. When reconstructing a node, these checks are used to skip
     516  over loose cuts, excluding them from the reconstituted basis. But here
     517  we're just interested in correcting the reference count. Tight/loose should
     518  make no difference.
     519
     520  Arguably a separate routine should be used in place of addCuts1. It's doing
     521  more work than needed, modifying the model to match a subproblem at a node
     522  that will be discarded.  Then again, we seem to need the basis.
     523*/
     524  for (j=nNodes-1;j >= kDelete;j--) {
     525    CbcNode * node = nodeArray[j];
     526    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
     527   
     528    model->addCuts1(node,lastws);
     529    // Decrement cut counts
     530    assert (node);
     531    //assert (node->nodeInfo());
     532    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
     533    int i;
     534    for (i=0;i<model->currentNumberCuts();i++) {
     535      // take off node
     536      CoinWarmStartBasis::Status status =
     537        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
     538      if (status != CoinWarmStartBasis::basic&&
     539          model->addedCuts()[i]) {
     540        if (!model->addedCuts()[i]->decrement(numberLeft))
     541          delete model->addedCuts()[i];
     542      }
     543    }
     544    // node should not have anything pointing to it
     545    if (node->nodeInfo())   
     546      node->nodeInfo()->throwAway();
     547    delete node ;
     548    delete lastws ;
     549  }
     550  delete [] nodeArray;
     551  delete [] depth;
     552}
     553
     554// Return the best node of the heap using alternate criterion
     555CbcNode *
     556CbcTree::bestAlternate() {
     557  int n=nodes_.size();
     558  CbcNode * best=NULL;
     559  if (n) {
     560    best = nodes_[0];
     561    for (int i=1;i<n;i++) {
     562      if (comparison_.alternateTest(best,nodes_[i])) {
     563        best=nodes_[i];
     564      }
     565    }
     566  }
     567  return best;
     568}
     569void
     570CbcTree::realpop() {
     571  if (nodes_.size()>0) {
     572    nodes_[0] = nodes_.back();
     573    nodes_.pop_back();
     574    fixTop();
     575  }
     576  assert (nodes_.size()>=0);
     577}
     578/* After changing data in the top node, fix the heap */
     579void
     580CbcTree::fixTop() {
     581  const int size = nodes_.size();
     582  if (size > 1) {
     583    CbcNode** candidates = &nodes_[0];
     584    CbcNode* s = candidates[0];
     585    --candidates;
     586    int pos = 1;
     587    int ch;
     588    for (ch = 2; ch < size; pos = ch, ch *= 2) {
     589      if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
     590        ++ch;
     591      if (!comparison_.compareNodes(s, candidates[ch]))
     592        break;
     593      candidates[pos] = candidates[ch];
     594    }
     595    if (ch == size) {
     596      if (!comparison_.compareNodes(candidates[ch], s)) {
     597        candidates[pos] = candidates[ch];
     598        pos = ch;
     599      }
     600    }
     601    candidates[pos] = s;
     602  }
     603}
     604void
     605CbcTree::realpush(CbcNode * node) {
     606  nodes_.push_back(node);
     607  CbcNode** candidates = &nodes_[0];
     608  --candidates;
     609  int pos = nodes_.size();
     610  int ch;
     611  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
     612    if (!comparison_.compareNodes(candidates[ch], node))
     613      break;
     614    candidates[pos] = candidates[ch];
     615  }
     616  candidates[pos] = node;
     617}
     618#endif
  • trunk/Cbc/src/CbcTree.hpp

    r706 r724  
    77
    88#include <vector>
     9#include <algorithm>
     10#include <cmath>
     11
     12#include "CoinFinite.hpp"
     13#include "CoinHelperFunctions.hpp"
    914
    1015/*! \class tree
     
    1318    This class is used to hold the set of live nodes in the search tree.
    1419*/
    15 
     20//#define CBC_DUBIOUS_HEAP
     21#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
     22//#define CBC_DUBIOUS_HEAP
     23#endif
     24#ifndef CBC_DUBIOUS_HEAP
    1625class CbcTree {
    1726
     
    185194
    186195};
     196#else
     197class CbcTree {
     198
     199public:
     200
     201  // Default Constructor
     202  CbcTree ();
     203
     204  // Copy constructor
     205  CbcTree ( const CbcTree & rhs);
     206  // = operator
     207  CbcTree & operator=(const CbcTree & rhs);
     208   
     209  virtual ~CbcTree();
     210
     211  /// Clone
     212  virtual CbcTree * clone() const;
     213  /// Create C++ lines to get to current state
     214  virtual void generateCpp( FILE * fp) {}
     215
     216/*! \name Heap access and maintenance methods */
     217//@{
     218
     219  /// Set comparison function and resort heap
     220  void setComparison(CbcCompareBase  &compare);
     221
     222  /// Return the top node of the heap
     223  virtual CbcNode * top() const;
     224
     225  /// Add a node to the heap
     226  virtual void push(CbcNode * x);
     227
     228  /// Remove the top node from the heap
     229  virtual void pop() ;
     230  /// Gets best node and takes off heap
     231  virtual CbcNode * bestNode(double cutoff);
     232
     233//@}
     234/*! \name vector methods */
     235//@{
     236
     237  /// Test if empty *** note may be overridden
     238  //virtual bool empty() ;
     239
     240  /// Return size
     241  inline int size() const
     242  { return nodes_.size();}
     243
     244  /// [] operator
     245  inline CbcNode * operator [] (int i) const
     246  { return nodes_[i];}
     247
     248  /// Return a node pointer
     249  inline CbcNode * nodePointer (int i) const
     250  { return nodes_[i];}
     251 
     252  virtual bool empty();
     253  //inline int size() const { return size_; }
     254  void realpop();
     255  /** After changing data in the top node, fix the heap */
     256  void fixTop();
     257  void realpush(CbcNode * node);
     258//@}
     259
     260/*! \name Search tree maintenance */
     261//@{
     262
     263/*! \brief Prune the tree using an objective function cutoff
     264
     265  This routine removes all nodes with objective worst than the
     266  specified cutoff value.
     267  It also sets bestPossibleObjective to best
     268  of all on tree before deleting.
     269*/
     270
     271  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
     272
     273  /// Get best on list using alternate method
     274  CbcNode * bestAlternate();
     275
     276  /// We may have got an intelligent tree so give it one more chance
     277  virtual void endSearch() {}
     278//@}
     279protected:
     280  std::vector <CbcNode *> nodes_;
     281  CbcCompare comparison_;       ///> Sort function for heap ordering.
     282
     283
     284};
    187285#endif
    188 
     286#endif
     287
Note: See TracChangeset for help on using the changeset viewer.