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

Last change on this file since 940 was 940, checked in by forrest, 12 years ago

for my experiments

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