source: trunk/Cbc/src/CbcTree.cpp @ 1121

Last change on this file since 1121 was 1121, checked in by forrest, 11 years ago

compiler warnings, deterministic parallel and stability

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 21.9 KB
Line 
1// Copyright (C) 2004, International Business Machines
2// Corporation and others.  All Rights Reserved.
3
4#include "CbcModel.hpp"
5#include "CbcNode.hpp"
6#include "CbcTree.hpp"
7#include "CbcCountRowCut.hpp"
8#include "CbcCompareActual.hpp"
9#include "CbcBranchActual.hpp"
10
11CbcTree::CbcTree()
12{
13  maximumNodeNumber_=0;
14  numberBranching_=0;
15  maximumBranching_=0;
16  branched_=NULL;
17  newBound_=NULL;
18}
19CbcTree::~CbcTree()
20{
21  delete [] branched_;
22  delete [] newBound_;
23}
24// Copy constructor
25CbcTree::CbcTree ( const CbcTree & rhs)
26{
27  nodes_=rhs.nodes_;
28  maximumNodeNumber_=rhs.maximumNodeNumber_;
29  numberBranching_=rhs.numberBranching_;
30  maximumBranching_=rhs.maximumBranching_;
31  if (maximumBranching_>0) {
32    branched_=CoinCopyOfArray(rhs.branched_,maximumBranching_);
33    newBound_=CoinCopyOfArray(rhs.newBound_,maximumBranching_);
34  } else {
35    branched_=NULL;
36    newBound_=NULL;
37  }
38}
39// Assignment operator
40CbcTree &
41CbcTree::operator=(const CbcTree & rhs)
42{
43  if (this != &rhs) {
44    nodes_=rhs.nodes_;
45    maximumNodeNumber_=rhs.maximumNodeNumber_;
46    delete [] branched_;
47    delete [] newBound_;
48    numberBranching_=rhs.numberBranching_;
49    maximumBranching_=rhs.maximumBranching_;
50    if (maximumBranching_>0) {
51      branched_=CoinCopyOfArray(rhs.branched_,maximumBranching_);
52      newBound_=CoinCopyOfArray(rhs.newBound_,maximumBranching_);
53    } else {
54      branched_=NULL;
55      newBound_=NULL;
56    }
57  }
58  return *this;
59}
60// Adds branching information to complete state
61void 
62CbcTree::addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
63                                 const double * currentLower,
64                                 const double * currentUpper)
65{
66  const OsiBranchingObject * objA  = nodeInfo->owner()->branchingObject();
67  const CbcIntegerBranchingObject * objBranch  = dynamic_cast<const CbcIntegerBranchingObject *> (objA);
68  if (objBranch) {
69    const CbcObject * objB = objBranch->object();
70    const CbcSimpleInteger * obj = dynamic_cast<const CbcSimpleInteger *> (objB);
71    assert (obj);
72    int iColumn = obj->columnNumber();
73    const double * down = objBranch->downBounds();
74    const double * up = objBranch->upBounds();
75    assert (currentLower[iColumn]==down[0]);
76    assert (currentUpper[iColumn]==up[1]);
77    if (dynamic_cast<const CbcPartialNodeInfo *> (nodeInfo)) {
78      const CbcPartialNodeInfo * info = dynamic_cast<const CbcPartialNodeInfo *> (nodeInfo);
79      const double * newBounds = info->newBounds();
80      const int * variables = info->variables();
81      int numberChanged = info->numberChangedBounds();
82      for (int i=0;i<numberChanged;i++) {
83        int jColumn = variables[i];
84        int kColumn = jColumn&(~0x80000000);
85        if (iColumn==kColumn) {
86          jColumn |= 0x40000000;
87#ifndef NDEBUG
88          double value = newBounds[i];
89          if ((jColumn&0x80000000)==0) {
90            assert (value==up[0]);
91          } else {
92            assert (value==down[1]);
93          }
94#endif
95        }
96        if (numberBranching_==maximumBranching_)
97          increaseSpace();
98        newBound_[numberBranching_]=static_cast<int> (newBounds[i]);
99        branched_[numberBranching_++]=jColumn;
100      }
101    } else {
102      const CbcFullNodeInfo * info = dynamic_cast<const CbcFullNodeInfo *> (nodeInfo);
103      int numberIntegers = model->numberIntegers();
104      const int * which = model->integerVariable();
105      const double * newLower = info->lower();
106      const double * newUpper = info->upper();
107      if (numberBranching_==maximumBranching_)
108        increaseSpace();
109      assert (newLower[iColumn]==up[0]||
110              newUpper[iColumn]==down[1]);
111      int jColumn=iColumn|0x40000000;
112      if (newLower[iColumn]==up[0]) {
113        newBound_[numberBranching_]=static_cast<int> (up[0]);
114      } else {
115        newBound_[numberBranching_]=static_cast<int> (down[1]);
116        jColumn|= 0x80000000;
117      }
118      branched_[numberBranching_++]=jColumn;
119      for (int i=0;i<numberIntegers;i++) {
120        int jColumn=which[i];
121        assert (currentLower[jColumn]==newLower[jColumn]||
122                currentUpper[jColumn]==newUpper[jColumn]);
123        if (jColumn!=iColumn) {
124          bool changed=false;
125          double value;
126          if (newLower[jColumn]>currentLower[jColumn]) {
127            value=newLower[jColumn];
128            changed=true;
129          } else if (newUpper[jColumn]<currentUpper[jColumn]) {
130            value=newUpper[jColumn];
131            jColumn|= 0x80000000;
132            changed=true;
133          }
134          if (changed) {
135            if (numberBranching_==maximumBranching_)
136              increaseSpace();
137            newBound_[numberBranching_]=static_cast<int> (value);
138            branched_[numberBranching_++]=jColumn;
139          }
140        }
141      }
142    }
143  } else {
144    // switch off
145    delete [] branched_;
146    delete [] newBound_;
147    maximumBranching_=-1;
148    branched_=NULL;
149    newBound_=NULL;
150  }
151}
152// Increase space for data
153void 
154CbcTree::increaseSpace()
155{
156  assert (numberBranching_==maximumBranching_);
157  maximumBranching_ = (3*maximumBranching_+10)>>1;
158  unsigned int * temp1 = CoinCopyOfArrayPartial(branched_,maximumBranching_,numberBranching_);
159  delete [] branched_;
160  branched_ = temp1;
161  int * temp2 = CoinCopyOfArrayPartial(newBound_,maximumBranching_,numberBranching_);
162  delete [] newBound_;
163  newBound_ = temp2;
164}
165// Clone
166CbcTree *
167CbcTree::clone() const
168{
169  return new CbcTree(*this);
170}
171//#define CBC_DEBUG_HEAP
172#ifndef CBC_DUBIOUS_HEAP
173// Set comparison function and resort heap
174void 
175CbcTree::setComparison(CbcCompareBase  &compare)
176{
177  comparison_.test_ = &compare;
178  std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
179}
180
181// Return the top node of the heap
182CbcNode * 
183CbcTree::top() const
184{
185  return nodes_.front();
186}
187
188// Add a node to the heap
189void 
190CbcTree::push(CbcNode * x) {
191  x->setNodeNumber(maximumNodeNumber_);
192  maximumNodeNumber_++;
193  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
194         x->objectiveValue(),x->nodeInfo()->decrement(0),
195         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
196  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
197  x->setOnTree(true);
198  nodes_.push_back(x);
199  std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
200}
201
202// Remove the top node from the heap
203void 
204CbcTree::pop() {
205  nodes_.front()->setOnTree(false);
206  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
207  nodes_.pop_back();
208}
209
210// Test if empty *** note may be overridden
211bool 
212CbcTree::empty() 
213{ 
214  return nodes_.empty();
215}
216// Gets best node and takes off heap
217CbcNode * 
218CbcTree::bestNode(double cutoff)
219{
220  CbcNode * best = NULL;
221  while (!best&&nodes_.size()) {
222    best = nodes_.front();
223    if (best)
224      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
225    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
226      assert (best->nodeInfo()->numberBranchesLeft());
227    if (best&&best->objectiveValue()>=cutoff) {
228      // double check in case node can change its mind!
229      best->checkIsCutoff(cutoff);
230    }
231    if (!best||best->objectiveValue()>=cutoff) {
232#if 0
233      // take off
234      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
235      nodes_.pop_back();
236      delete best;
237      best=NULL;
238#else
239      // let code get rid of it
240      assert (best);
241#endif
242    }
243  }
244  // switched off for now
245  if (best&&comparison_.test_->fullScan()&&false) {
246    CbcNode * saveBest=best;
247    int n=nodes_.size();
248    int iBest=-1;
249    for (int i=0;i<n;i++) {
250      // temp
251      assert (nodes_[i]);
252      assert (nodes_[i]->nodeInfo());
253      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
254        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
255      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
256          &&comparison_.alternateTest(best,nodes_[i])) {
257        best=nodes_[i];
258        iBest=i;
259      }
260    }
261    if (best==saveBest) {
262      // can pop
263      // take off
264      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
265      nodes_.pop_back();
266    } else {
267      // make impossible
268      nodes_[iBest]=NULL;
269    }
270  } else if (best) {
271    // take off
272    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
273    nodes_.pop_back();
274  }
275#ifdef DEBUG_CBC_HEAP
276  if (best) {
277    int n=nodes_.size();
278    bool good=true;
279    for (int i=0;i<n;i++) {
280      // temp
281      assert (nodes_[i]);
282      if (!comparison_.compareNodes(nodes_[i],best)) {
283        good=false;
284        CbcNode * x = nodes_[i];
285        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
286               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
287               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
288      }
289    }
290    if (!good) {
291      // compare best to all
292      int i;
293      for (i=0;i<n;i++) {
294        CbcNode * x = nodes_[i];
295        printf("i=%d x is nun %d depth %d obj %g",i,
296               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
297        if (!comparison_.compareNodes(x,best)) {
298          printf(" - best is worse!\n");
299        } else {
300          printf("\n");
301        }
302      }
303      // Now compare amongst rest
304      for (i=0;i<n;i++) {
305        CbcNode * x = nodes_[i];
306        printf("For i=%d ",i);
307        for (int j=i+1;j<n;j++) {
308          CbcNode * y = nodes_[j];
309          if (!comparison_.compareNodes(x,y)) {
310            printf(" b %d",j);
311          } else {
312            printf(" w %d",j);
313          }
314        }
315        printf("\n");
316      }
317      assert(good);
318    }
319  }
320#endif
321  if (best)
322    best->setOnTree(false);
323  return best;
324}
325
326double
327CbcTree::getBestPossibleObjective(){
328  double r_val = 1e100;
329  for(int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++){
330    if(nodes_[i] && nodes_[i]->objectiveValue() < r_val){
331      r_val = nodes_[i]->objectiveValue();
332    }
333  }
334  return r_val;
335}
336/*! \brief Prune the tree using an objective function cutoff
337
338  This routine removes all nodes with objective worst than the
339  specified cutoff value.
340*/
341
342void 
343CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
344{
345  int j;
346  int nNodes = size();
347  CbcNode ** nodeArray = new CbcNode * [nNodes];
348  int * depth = new int [nNodes];
349  int k=0;
350  int kDelete=nNodes;
351  bestPossibleObjective = 1.0e100 ;
352/*
353    Destructively scan the heap. Nodes to be retained go into the front of
354    nodeArray, nodes to be deleted into the back. Store the depth in a
355    correlated array for nodes to be deleted.
356*/
357  for (j=0;j<nNodes;j++) {
358    CbcNode * node = top();
359    pop();
360    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
361    if (node&&value>=cutoff) {
362      // double check in case node can change its mind!
363      value=node->checkIsCutoff(cutoff);
364    }
365    if (value >= cutoff||!node->active()) {
366      if (node) {
367        nodeArray[--kDelete] = node;
368        depth[kDelete] = node->depth();
369      }
370    } else {
371      bestPossibleObjective = CoinMin(bestPossibleObjective,value);
372      nodeArray[k++]=node;
373    }
374  }
375/*
376  Rebuild the heap using the retained nodes.
377*/
378  for (j=0;j<k;j++) { push(nodeArray[j]); }
379/*
380  Sort the list of nodes to be deleted, nondecreasing.
381*/
382  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
383/*
384  Work back from deepest to shallowest. In spite of the name, addCuts1 is
385  just a preparatory step. When it returns, the following will be true:
386    * all cuts are removed from the solver's copy of the constraint system;
387    * lastws will be a basis appropriate for the specified node;
388    * variable bounds will be adjusted to be appropriate for the specified
389      node;
390    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
391      should be added to the constraint system at this node (but they have
392      not actually been added).
393  Then we scan the cut list for the node. Decrement the reference count
394  for the cut, and if it's gone to 0, really delete it.
395
396  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
397  are necessary. When reconstructing a node, these checks are used to skip
398  over loose cuts, excluding them from the reconstituted basis. But here
399  we're just interested in correcting the reference count. Tight/loose should
400  make no difference.
401
402  Arguably a separate routine should be used in place of addCuts1. It's doing
403  more work than needed, modifying the model to match a subproblem at a node
404  that will be discarded.  Then again, we seem to need the basis.
405*/
406  for (j=nNodes-1;j >= kDelete;j--) {
407    CbcNode * node = nodeArray[j];
408    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
409   
410    model->addCuts1(node,lastws);
411    // Decrement cut counts
412    assert (node);
413    //assert (node->nodeInfo());
414    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
415    int i;
416    for (i=0;i<model->currentNumberCuts();i++) {
417      // take off node
418      CoinWarmStartBasis::Status status = 
419        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
420      if (status != CoinWarmStartBasis::basic&&
421          model->addedCuts()[i]) {
422        if (!model->addedCuts()[i]->decrement(numberLeft))
423          delete model->addedCuts()[i];
424      }
425    }
426    // node should not have anything pointing to it
427    if (node->nodeInfo())   
428      node->nodeInfo()->throwAway();
429    delete node ;
430    delete lastws ;
431  }
432  delete [] nodeArray;
433  delete [] depth;
434}
435
436// Return the best node of the heap using alternate criterion
437CbcNode * 
438CbcTree::bestAlternate() {
439  int n=nodes_.size();
440  CbcNode * best=NULL;
441  if (n) {
442    best = nodes_[0];
443    for (int i=1;i<n;i++) {
444      if (comparison_.alternateTest(best,nodes_[i])) {
445        best=nodes_[i];
446      }
447    }
448  }
449  return best;
450}
451#else
452// Set comparison function and resort heap
453void 
454CbcTree::setComparison(CbcCompareBase  &compare)
455{
456  comparison_.test_ = &compare;
457  std::vector <CbcNode *> newNodes=nodes_;
458  nodes_.resize(0);
459  while (newNodes.size()>0) {
460    push( newNodes.back());
461    newNodes.pop_back();
462  }
463}
464
465// Return the top node of the heap
466CbcNode * 
467CbcTree::top() const
468{
469  return nodes_.front();
470}
471
472// Add a node to the heap
473void 
474CbcTree::push(CbcNode * x) {
475  x->setNodeNumber(maximumNodeNumber_);
476  maximumNodeNumber_++;
477  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
478         x->objectiveValue(),x->nodeInfo()->decrement(0),
479         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
480  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
481#if 0
482  nodes_.push_back(x);
483  push_heap(nodes_.begin(), nodes_.end(), comparison_);
484#else
485  realpush(x);
486#endif
487}
488
489// Remove the top node from the heap
490void 
491CbcTree::pop() {
492#if 0
493  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
494  nodes_.pop_back();
495#else
496  if (nodes_.size()) {
497    //CbcNode* s = nodes_.front();
498    realpop();
499    //delete s;
500  }
501  assert (nodes_.size()>=0);
502#endif
503}
504
505// Test if empty *** note may be overridden
506bool 
507CbcTree::empty() 
508{ 
509  return nodes_.empty();
510}
511// Gets best node and takes off heap
512CbcNode * 
513CbcTree::bestNode(double cutoff)
514{
515  CbcNode * best = NULL;
516  while (!best&&nodes_.size()) {
517    best = nodes_.front();
518    if (best)
519      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
520    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
521      assert (best->nodeInfo()->numberBranchesLeft());
522    if (best&&best->objectiveValue()>=cutoff) {
523      // double check in case node can change its mind!
524      best->checkIsCutoff(cutoff);
525    }
526    if (!best||best->objectiveValue()>=cutoff) {
527#if 0
528      // take off
529      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
530      nodes_.pop_back();
531      delete best;
532      best=NULL;
533#else
534      // let code get rid of it
535      assert (best);
536#endif
537    }
538  }
539  // switched off for now
540  if (best&&comparison_.test_->fullScan()&&false) {
541    CbcNode * saveBest=best;
542    int n=nodes_.size();
543    int iBest=-1;
544    for (int i=0;i<n;i++) {
545      // temp
546      assert (nodes_[i]);
547      assert (nodes_[i]->nodeInfo());
548      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
549        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
550      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
551          &&comparison_.alternateTest(best,nodes_[i])) {
552        best=nodes_[i];
553        iBest=i;
554      }
555    }
556    if (best==saveBest) {
557      // can pop
558      // take off
559      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
560      nodes_.pop_back();
561    } else {
562      // make impossible
563      nodes_[iBest]=NULL;
564    }
565  } else if (best) {
566    // take off
567#if 0
568    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
569    nodes_.pop_back();
570#else
571    realpop();
572#endif
573  }
574#ifdef DEBUG_CBC_HEAP
575  if (best) {
576    int n=nodes_.size();
577    bool good=true;
578    for (int i=0;i<n;i++) {
579      // temp
580      assert (nodes_[i]);
581      if (!comparison_.compareNodes(nodes_[i],best)) {
582        good=false;
583        CbcNode * x = nodes_[i];
584        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
585               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
586               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
587      }
588    }
589    if (!good) {
590      // compare best to all
591      int i;
592      for (i=0;i<n;i++) {
593        CbcNode * x = nodes_[i];
594        printf("i=%d x is nun %d depth %d obj %g",i,
595               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
596        if (!comparison_.compareNodes(x,best)) {
597          printf(" - best is worse!\n");
598        } else {
599          printf("\n");
600        }
601      }
602      // Now compare amongst rest
603      for (i=0;i<n;i++) {
604        CbcNode * x = nodes_[i];
605        printf("For i=%d ",i);
606        for (int j=i+1;j<n;j++) {
607          CbcNode * y = nodes_[j];
608          if (!comparison_.compareNodes(x,y)) {
609            printf(" b %d",j);
610          } else {
611            printf(" w %d",j);
612          }
613        }
614        printf("\n");
615      }
616      assert(good);
617    }
618  }
619#endif
620  if (best)
621    best->setOnTree(false);
622  return best;
623}
624
625/*! \brief Prune the tree using an objective function cutoff
626
627  This routine removes all nodes with objective worst than the
628  specified cutoff value.
629*/
630
631void 
632CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
633{
634  int j;
635  int nNodes = nodes_.size();
636  CbcNode ** nodeArray = new CbcNode * [nNodes];
637  int * depth = new int [nNodes];
638  int k=0;
639  int kDelete=nNodes;
640  bestPossibleObjective = 1.0e100 ;
641/*
642    Destructively scan the heap. Nodes to be retained go into the front of
643    nodeArray, nodes to be deleted into the back. Store the depth in a
644    correlated array for nodes to be deleted.
645*/
646  for (j=0;j<nNodes;j++) {
647    CbcNode * node = top();
648    pop();
649    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
650    if (node&&value>=cutoff) {
651      // double check in case node can change its mind!
652      value=node->checkIsCutoff(cutoff);
653    }
654    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
655    if (value >= cutoff) {
656      if (node) {
657        nodeArray[--kDelete] = node;
658        depth[kDelete] = node->depth();
659      }
660    } else {
661      nodeArray[k++]=node;
662    }
663  }
664/*
665  Rebuild the heap using the retained nodes.
666*/
667  for (j=0;j<k;j++) { push(nodeArray[j]); }
668/*
669  Sort the list of nodes to be deleted, nondecreasing.
670*/
671  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
672/*
673  Work back from deepest to shallowest. In spite of the name, addCuts1 is
674  just a preparatory step. When it returns, the following will be true:
675    * all cuts are removed from the solver's copy of the constraint system;
676    * lastws will be a basis appropriate for the specified node;
677    * variable bounds will be adjusted to be appropriate for the specified
678      node;
679    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
680      should be added to the constraint system at this node (but they have
681      not actually been added).
682  Then we scan the cut list for the node. Decrement the reference count
683  for the cut, and if it's gone to 0, really delete it.
684
685  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
686  are necessary. When reconstructing a node, these checks are used to skip
687  over loose cuts, excluding them from the reconstituted basis. But here
688  we're just interested in correcting the reference count. Tight/loose should
689  make no difference.
690
691  Arguably a separate routine should be used in place of addCuts1. It's doing
692  more work than needed, modifying the model to match a subproblem at a node
693  that will be discarded.  Then again, we seem to need the basis.
694*/
695  for (j=nNodes-1;j >= kDelete;j--) {
696    CbcNode * node = nodeArray[j];
697    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
698   
699    model->addCuts1(node,lastws);
700    // Decrement cut counts
701    assert (node);
702    //assert (node->nodeInfo());
703    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
704    int i;
705    for (i=0;i<model->currentNumberCuts();i++) {
706      // take off node
707      CoinWarmStartBasis::Status status = 
708        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
709      if (status != CoinWarmStartBasis::basic&&
710          model->addedCuts()[i]) {
711        if (!model->addedCuts()[i]->decrement(numberLeft))
712          delete model->addedCuts()[i];
713      }
714    }
715    // node should not have anything pointing to it
716    if (node->nodeInfo())   
717      node->nodeInfo()->throwAway();
718    delete node ;
719    delete lastws ;
720  }
721  delete [] nodeArray;
722  delete [] depth;
723}
724
725// Return the best node of the heap using alternate criterion
726CbcNode * 
727CbcTree::bestAlternate() {
728  int n=nodes_.size();
729  CbcNode * best=NULL;
730  if (n) {
731    best = nodes_[0];
732    for (int i=1;i<n;i++) {
733      if (comparison_.alternateTest(best,nodes_[i])) {
734        best=nodes_[i];
735      }
736    }
737  }
738  return best;
739}
740void 
741CbcTree::realpop() {
742  if (nodes_.size()>0) {
743    nodes_[0] = nodes_.back();
744    nodes_.pop_back();
745    fixTop();
746  }
747  assert (nodes_.size()>=0);
748}
749/* After changing data in the top node, fix the heap */
750void 
751CbcTree::fixTop() {
752  const int size = nodes_.size();
753  if (size > 1) {
754    CbcNode** candidates = &nodes_[0];
755    CbcNode* s = candidates[0];
756    --candidates;
757    int pos = 1;
758    int ch;
759    for (ch = 2; ch < size; pos = ch, ch *= 2) {
760      if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
761        ++ch;
762      if (!comparison_.compareNodes(s, candidates[ch]))
763        break;
764      candidates[pos] = candidates[ch];
765    }
766    if (ch == size) {
767      if (!comparison_.compareNodes(candidates[ch], s)) {
768        candidates[pos] = candidates[ch];
769        pos = ch;
770      }
771    }
772    candidates[pos] = s;
773  }
774}
775void 
776CbcTree::realpush(CbcNode * node) {
777  node->setOnTree(true);
778  nodes_.push_back(node);
779  CbcNode** candidates = &nodes_[0];
780  --candidates;
781  int pos = nodes_.size();
782  int ch;
783  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
784    if (!comparison_.compareNodes(candidates[ch], node))
785      break;
786    candidates[pos] = candidates[ch];
787  }
788  candidates[pos] = node;
789}
790#endif
Note: See TracBrowser for help on using the repository browser.