Ignore:
Timestamp:
Mar 16, 2009 6:30:25 AM (11 years ago)
Author:
forrest
Message:

chnages to try and make faster

File:
1 edited

Legend:

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

    r1121 r1132  
    449449  return best;
    450450}
     451CbcTreeArray::CbcTreeArray()
     452  : CbcTree(),
     453    lastNode_(NULL),
     454    lastNodePopped_(NULL),
     455    switches_(0)
     456{
     457}
     458CbcTreeArray::~CbcTreeArray()
     459{
     460}
     461// Copy constructor
     462CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
     463  : CbcTree(rhs),
     464    lastNode_(rhs.lastNode_),
     465    lastNodePopped_(rhs.lastNodePopped_),
     466    switches_(rhs.switches_)
     467{
     468}
     469// Assignment operator
     470CbcTreeArray &
     471CbcTreeArray::operator=(const CbcTreeArray & rhs)
     472{
     473  if (this != &rhs) {
     474    CbcTree::operator=(rhs);
     475    lastNode_ = rhs.lastNode_;
     476    lastNodePopped_ = rhs.lastNodePopped_;
     477    switches_ = rhs.switches_;
     478  }
     479  return *this;
     480}
     481// Clone
     482CbcTree *
     483CbcTreeArray::clone() const
     484{
     485  return new CbcTreeArray(*this);
     486}
     487// Set comparison function and resort heap
     488void
     489CbcTreeArray::setComparison(CbcCompareBase  &compare)
     490{
     491  comparison_.test_ = &compare;
     492  std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
     493}
     494
     495// Add a node to the heap
     496void
     497CbcTreeArray::push(CbcNode * x) {
     498  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
     499         x->objectiveValue(),x->nodeInfo()->decrement(0),
     500         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
     501  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
     502  x->setOnTree(true);
     503  if (lastNode_) {
     504    if (lastNode_->nodeInfo()->parent()==x->nodeInfo()) {
     505      // x is parent of lastNode_ so put x on heap
     506      //#define CBCTREE_PRINT
     507#ifdef CBCTREE_PRINT
     508      printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
     509             x,x->nodeInfo(),x->depth(),x->nodeNumber(),
     510             lastNode_,lastNode_->nodeInfo(),lastNode_->depth(),lastNode_->nodeNumber());
     511#endif
     512      nodes_.push_back(x);
     513    } else {
     514      x->setNodeNumber(maximumNodeNumber_);
     515      maximumNodeNumber_++;
     516#ifdef CBCTREE_PRINT
     517      printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
     518             x,x->nodeInfo(),x->depth(),x->nodeNumber(),
     519             lastNode_,lastNode_->nodeInfo(),lastNode_->depth(),lastNode_->nodeNumber());
     520#endif
     521      nodes_.push_back(lastNode_);
     522      lastNode_ = x;
     523    }
     524    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
     525  } else {
     526    x->setNodeNumber(maximumNodeNumber_);
     527    maximumNodeNumber_++;
     528    if (x!=lastNodePopped_) {
     529      lastNode_ = x;
     530#ifdef CBCTREE_PRINT
     531      printf("pushNULL x %x (%x at depth %d n %d)\n",
     532             x,x->nodeInfo(),x->depth(),x->nodeNumber());
     533#endif
     534    } else {
     535      // means other way was infeasible
     536#ifdef CBCTREE_PRINT
     537      printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
     538             x,x->nodeInfo(),x->depth(),x->nodeNumber());
     539#endif
     540      nodes_.push_back(x);
     541      std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
     542    }
     543  }
     544}
     545
     546// Test if empty *** note may be overridden
     547bool
     548CbcTreeArray::empty()
     549{
     550  return nodes_.empty()&&(lastNode_==NULL);
     551}
     552// Gets best node and takes off heap
     553CbcNode *
     554CbcTreeArray::bestNode(double cutoff)
     555{
     556  CbcNode * best = NULL;
     557  // See if we want last node or best on heap
     558  if (lastNode_) {
     559#ifdef CBCTREE_PRINT
     560    printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
     561           lastNode_,lastNode_->nodeInfo(),lastNode_->depth(),
     562           lastNode_->nodeNumber(),lastNode_->objectiveValue());
     563#endif
     564    assert (lastNode_->onTree());
     565    int nodeNumber = lastNode_->nodeNumber();
     566    bool useLastNode=false;
     567    if (nodeNumber+1==maximumNodeNumber_) {
     568      // diving - look further
     569      CbcCompareDefault * compareDefault
     570        = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
     571      assert (compareDefault);
     572      double bestPossible = compareDefault->getBestPossible();
     573      double cutoff = compareDefault->getCutoff();
     574      double objValue = lastNode_->objectiveValue();
     575      if (cutoff<1.0e20) {
     576        if (objValue-bestPossible<0.999*(cutoff-bestPossible))
     577          useLastNode=true;
     578      } else {
     579        useLastNode=true;
     580      }
     581    }
     582    if (useLastNode) {
     583      lastNode_->setOnTree(false);
     584      best = lastNode_;
     585      lastNode_=NULL;
     586      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
     587      if (best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
     588        assert (best->nodeInfo()->numberBranchesLeft());
     589      if (best->objectiveValue()>=cutoff) {
     590        // double check in case node can change its mind!
     591        best->checkIsCutoff(cutoff);
     592      }
     593      lastNodePopped_=best;
     594      return best;
     595    } else {
     596      // put on tree
     597      nodes_.push_back(lastNode_);
     598      lastNode_->setNodeNumber(maximumNodeNumber_);
     599      maximumNodeNumber_++;
     600      lastNode_ = NULL;
     601      std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
     602    }
     603  }
     604  while (!best&&nodes_.size()) {
     605    best = nodes_.front();
     606    if (best)
     607      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
     608    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
     609      assert (best->nodeInfo()->numberBranchesLeft());
     610    if (best&&best->objectiveValue()>=cutoff) {
     611      // double check in case node can change its mind!
     612      best->checkIsCutoff(cutoff);
     613    }
     614    if (!best||best->objectiveValue()>=cutoff) {
     615      // let code get rid of it
     616      assert (best);
     617    }
     618  }
     619  lastNodePopped_=best;
     620#ifdef CBCTREE_PRINT
     621  if (best)
     622    printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
     623           best,best->nodeInfo(),best->depth(),
     624           best->nodeNumber(),best->objectiveValue());
     625  else
     626    printf("Heap returning Null\n");
     627#endif
     628  if (best) {
     629    // take off
     630    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     631    nodes_.pop_back();
     632  }
     633#ifdef DEBUG_CBC_HEAP
     634  if (best) {
     635    int n=nodes_.size();
     636    bool good=true;
     637    for (int i=0;i<n;i++) {
     638      // temp
     639      assert (nodes_[i]);
     640      if (!comparison_.compareNodes(nodes_[i],best)) {
     641        good=false;
     642        CbcNode * x = nodes_[i];
     643        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
     644               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
     645               best->numberUnsatisfied(),best->depth(),best->objectiveValue());
     646      }
     647    }
     648    if (!good) {
     649      // compare best to all
     650      int i;
     651      for (i=0;i<n;i++) {
     652        CbcNode * x = nodes_[i];
     653        printf("i=%d x is nun %d depth %d obj %g",i,
     654               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
     655        if (!comparison_.compareNodes(x,best)) {
     656          printf(" - best is worse!\n");
     657        } else {
     658          printf("\n");
     659        }
     660      }
     661      // Now compare amongst rest
     662      for (i=0;i<n;i++) {
     663        CbcNode * x = nodes_[i];
     664        printf("For i=%d ",i);
     665        for (int j=i+1;j<n;j++) {
     666          CbcNode * y = nodes_[j];
     667          if (!comparison_.compareNodes(x,y)) {
     668            printf(" b %d",j);
     669          } else {
     670            printf(" w %d",j);
     671          }
     672        }
     673        printf("\n");
     674      }
     675      assert(good);
     676    }
     677  }
     678#endif
     679  if (best)
     680    best->setOnTree(false);
     681  return best;
     682}
     683
     684double
     685CbcTreeArray::getBestPossibleObjective(){
     686  double bestPossibleObjective = 1e100;
     687  for(int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++){
     688    if(nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective){
     689      bestPossibleObjective = nodes_[i]->objectiveValue();
     690    }
     691  }
     692  if (lastNode_) {
     693    bestPossibleObjective = CoinMin(bestPossibleObjective,lastNode_->objectiveValue());
     694  }
     695  CbcCompareDefault * compareDefault
     696    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
     697  assert (compareDefault);
     698  compareDefault->setBestPossible(bestPossibleObjective);
     699  return bestPossibleObjective;
     700}
     701/*! \brief Prune the tree using an objective function cutoff
     702
     703  This routine removes all nodes with objective worst than the
     704  specified cutoff value.
     705*/
     706
     707void
     708CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
     709{
     710  int j;
     711  int nNodes = size();
     712  int lastNode = nNodes+1;
     713  CbcNode ** nodeArray = new CbcNode * [lastNode];
     714  int * depth = new int [lastNode];
     715  int k=0;
     716  int kDelete=lastNode;
     717  bestPossibleObjective = 1.0e100 ;
     718/*
     719    Destructively scan the heap. Nodes to be retained go into the front of
     720    nodeArray, nodes to be deleted into the back. Store the depth in a
     721    correlated array for nodes to be deleted.
     722*/
     723  for (j=0;j<nNodes;j++) {
     724    CbcNode * node = nodes_.front();
     725    nodes_.front()->setOnTree(false);
     726    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
     727    nodes_.pop_back();
     728    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
     729    if (node&&value>=cutoff) {
     730      // double check in case node can change its mind!
     731      value=node->checkIsCutoff(cutoff);
     732    }
     733    if (value >= cutoff||!node->active()) {
     734      if (node) {
     735        nodeArray[--kDelete] = node;
     736        depth[kDelete] = node->depth();
     737      }
     738    } else {
     739      bestPossibleObjective = CoinMin(bestPossibleObjective,value);
     740      nodeArray[k++]=node;
     741    }
     742  }
     743  if (lastNode_) {
     744    double value = lastNode_->objectiveValue();
     745    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
     746    if (value >= cutoff||!lastNode_->active()) {
     747      nodeArray[--kDelete] = lastNode_;
     748      depth[kDelete] = lastNode_->depth();
     749      lastNode_=NULL;
     750    }
     751  }
     752  CbcCompareDefault * compareDefault
     753    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
     754  assert (compareDefault);
     755  compareDefault->setBestPossible(bestPossibleObjective);
     756  compareDefault->setCutoff(cutoff);
     757/*
     758  Rebuild the heap using the retained nodes.
     759*/
     760  for (j=0;j<k;j++) {
     761    CbcNode * node = nodeArray[j];
     762    node->setOnTree(true);
     763    nodes_.push_back(node);
     764    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
     765  }
     766/*
     767  Sort the list of nodes to be deleted, nondecreasing.
     768*/
     769  CoinSort_2(depth+kDelete,depth+lastNode,nodeArray+kDelete);
     770/*
     771  Work back from deepest to shallowest. In spite of the name, addCuts1 is
     772  just a preparatory step. When it returns, the following will be true:
     773    * all cuts are removed from the solver's copy of the constraint system;
     774    * lastws will be a basis appropriate for the specified node;
     775    * variable bounds will be adjusted to be appropriate for the specified
     776      node;
     777    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
     778      should be added to the constraint system at this node (but they have
     779      not actually been added).
     780  Then we scan the cut list for the node. Decrement the reference count
     781  for the cut, and if it's gone to 0, really delete it.
     782
     783  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
     784  are necessary. When reconstructing a node, these checks are used to skip
     785  over loose cuts, excluding them from the reconstituted basis. But here
     786  we're just interested in correcting the reference count. Tight/loose should
     787  make no difference.
     788
     789  Arguably a separate routine should be used in place of addCuts1. It's doing
     790  more work than needed, modifying the model to match a subproblem at a node
     791  that will be discarded.  Then again, we seem to need the basis.
     792*/
     793  for (j=lastNode-1;j >= kDelete;j--) {
     794    CbcNode * node = nodeArray[j];
     795    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
     796   
     797    model->addCuts1(node,lastws);
     798    // Decrement cut counts
     799    assert (node);
     800    //assert (node->nodeInfo());
     801    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
     802    int i;
     803    for (i=0;i<model->currentNumberCuts();i++) {
     804      // take off node
     805      CoinWarmStartBasis::Status status =
     806        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
     807      if (status != CoinWarmStartBasis::basic&&
     808          model->addedCuts()[i]) {
     809        if (!model->addedCuts()[i]->decrement(numberLeft))
     810          delete model->addedCuts()[i];
     811      }
     812    }
     813    // node should not have anything pointing to it
     814    if (node->nodeInfo())   
     815      node->nodeInfo()->throwAway();
     816    delete node ;
     817    delete lastws ;
     818  }
     819  delete [] nodeArray;
     820  delete [] depth;
     821}
    451822#else
    452823// Set comparison function and resort heap
Note: See TracChangeset for help on using the changeset viewer.