source: stable/2.4/Cbc/src/CbcTree.cpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 33.4 KB
Line 
1/* $Id: CbcTree.cpp 1271 2009-11-05 15:57:25Z forrest $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4
5#include "CbcModel.hpp"
6#include "CbcNode.hpp"
7#include "CbcTree.hpp"
8#include "CbcCountRowCut.hpp"
9#include "CbcCompareActual.hpp"
10#include "CbcBranchActual.hpp"
11
12CbcTree::CbcTree()
13{
14  maximumNodeNumber_=0;
15  numberBranching_=0;
16  maximumBranching_=0;
17  branched_=NULL;
18  newBound_=NULL;
19}
20CbcTree::~CbcTree()
21{
22  delete [] branched_;
23  delete [] newBound_;
24}
25// Copy constructor
26CbcTree::CbcTree ( const CbcTree & rhs)
27{
28  nodes_=rhs.nodes_;
29  maximumNodeNumber_=rhs.maximumNodeNumber_;
30  numberBranching_=rhs.numberBranching_;
31  maximumBranching_=rhs.maximumBranching_;
32  if (maximumBranching_>0) {
33    branched_=CoinCopyOfArray(rhs.branched_,maximumBranching_);
34    newBound_=CoinCopyOfArray(rhs.newBound_,maximumBranching_);
35  } else {
36    branched_=NULL;
37    newBound_=NULL;
38  }
39}
40// Assignment operator
41CbcTree &
42CbcTree::operator=(const CbcTree & rhs)
43{
44  if (this != &rhs) {
45    nodes_=rhs.nodes_;
46    maximumNodeNumber_=rhs.maximumNodeNumber_;
47    delete [] branched_;
48    delete [] newBound_;
49    numberBranching_=rhs.numberBranching_;
50    maximumBranching_=rhs.maximumBranching_;
51    if (maximumBranching_>0) {
52      branched_=CoinCopyOfArray(rhs.branched_,maximumBranching_);
53      newBound_=CoinCopyOfArray(rhs.newBound_,maximumBranching_);
54    } else {
55      branched_=NULL;
56      newBound_=NULL;
57    }
58  }
59  return *this;
60}
61// Adds branching information to complete state
62void 
63CbcTree::addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
64                                 const double * currentLower,
65                                 const double * currentUpper)
66{
67  const OsiBranchingObject * objA  = nodeInfo->owner()->branchingObject();
68  const CbcIntegerBranchingObject * objBranch  = dynamic_cast<const CbcIntegerBranchingObject *> (objA);
69  if (objBranch) {
70    const CbcObject * objB = objBranch->object();
71    const CbcSimpleInteger * obj = dynamic_cast<const CbcSimpleInteger *> (objB);
72    assert (obj);
73    int iColumn = obj->columnNumber();
74    const double * down = objBranch->downBounds();
75    const double * up = objBranch->upBounds();
76    assert (currentLower[iColumn]==down[0]);
77    assert (currentUpper[iColumn]==up[1]);
78    if (dynamic_cast<const CbcPartialNodeInfo *> (nodeInfo)) {
79      const CbcPartialNodeInfo * info = dynamic_cast<const CbcPartialNodeInfo *> (nodeInfo);
80      const double * newBounds = info->newBounds();
81      const int * variables = info->variables();
82      int numberChanged = info->numberChangedBounds();
83      for (int i=0;i<numberChanged;i++) {
84        int jColumn = variables[i];
85        int kColumn = jColumn&(~0x80000000);
86        if (iColumn==kColumn) {
87          jColumn |= 0x40000000;
88#ifndef NDEBUG
89          double value = newBounds[i];
90          if ((jColumn&0x80000000)==0) {
91            assert (value==up[0]);
92          } else {
93            assert (value==down[1]);
94          }
95#endif
96        }
97        if (numberBranching_==maximumBranching_)
98          increaseSpace();
99        newBound_[numberBranching_]=static_cast<int> (newBounds[i]);
100        branched_[numberBranching_++]=jColumn;
101      }
102    } else {
103      const CbcFullNodeInfo * info = dynamic_cast<const CbcFullNodeInfo *> (nodeInfo);
104      int numberIntegers = model->numberIntegers();
105      const int * which = model->integerVariable();
106      const double * newLower = info->lower();
107      const double * newUpper = info->upper();
108      if (numberBranching_==maximumBranching_)
109        increaseSpace();
110      assert (newLower[iColumn]==up[0]||
111              newUpper[iColumn]==down[1]);
112      int jColumn=iColumn|0x40000000;
113      if (newLower[iColumn]==up[0]) {
114        newBound_[numberBranching_]=static_cast<int> (up[0]);
115      } else {
116        newBound_[numberBranching_]=static_cast<int> (down[1]);
117        jColumn|= 0x80000000;
118      }
119      branched_[numberBranching_++]=jColumn;
120      for (int i=0;i<numberIntegers;i++) {
121        int jColumn=which[i];
122        assert (currentLower[jColumn]==newLower[jColumn]||
123                currentUpper[jColumn]==newUpper[jColumn]);
124        if (jColumn!=iColumn) {
125          bool changed=false;
126          double value;
127          if (newLower[jColumn]>currentLower[jColumn]) {
128            value=newLower[jColumn];
129            changed=true;
130          } else if (newUpper[jColumn]<currentUpper[jColumn]) {
131            value=newUpper[jColumn];
132            jColumn|= 0x80000000;
133            changed=true;
134          }
135          if (changed) {
136            if (numberBranching_==maximumBranching_)
137              increaseSpace();
138            newBound_[numberBranching_]=static_cast<int> (value);
139            branched_[numberBranching_++]=jColumn;
140          }
141        }
142      }
143    }
144  } else {
145    // switch off
146    delete [] branched_;
147    delete [] newBound_;
148    maximumBranching_=-1;
149    branched_=NULL;
150    newBound_=NULL;
151  }
152}
153// Increase space for data
154void 
155CbcTree::increaseSpace()
156{
157  assert (numberBranching_==maximumBranching_);
158  maximumBranching_ = (3*maximumBranching_+10)>>1;
159  unsigned int * temp1 = CoinCopyOfArrayPartial(branched_,maximumBranching_,numberBranching_);
160  delete [] branched_;
161  branched_ = temp1;
162  int * temp2 = CoinCopyOfArrayPartial(newBound_,maximumBranching_,numberBranching_);
163  delete [] newBound_;
164  newBound_ = temp2;
165}
166// Clone
167CbcTree *
168CbcTree::clone() const
169{
170  return new CbcTree(*this);
171}
172//#define CBC_DEBUG_HEAP
173#ifndef CBC_DUBIOUS_HEAP
174// Set comparison function and resort heap
175void 
176CbcTree::setComparison(CbcCompareBase  &compare)
177{
178  comparison_.test_ = &compare;
179  std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
180}
181
182// Return the top node of the heap
183CbcNode * 
184CbcTree::top() const
185{
186  return nodes_.front();
187}
188
189// Add a node to the heap
190void 
191CbcTree::push(CbcNode * x) {
192  x->setNodeNumber(maximumNodeNumber_);
193  maximumNodeNumber_++;
194  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
195         x->objectiveValue(),x->nodeInfo()->decrement(0),
196         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
197  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
198  x->setOnTree(true);
199  nodes_.push_back(x);
200  std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
201}
202
203// Remove the top node from the heap
204void 
205CbcTree::pop() {
206  nodes_.front()->setOnTree(false);
207  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
208  nodes_.pop_back();
209}
210
211// Test if empty *** note may be overridden
212bool 
213CbcTree::empty() 
214{ 
215  return nodes_.empty();
216}
217// Gets best node and takes off heap
218CbcNode * 
219CbcTree::bestNode(double cutoff)
220{
221  CbcNode * best = NULL;
222  while (!best&&nodes_.size()) {
223    best = nodes_.front();
224    if (best)
225      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
226    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
227      assert (best->nodeInfo()->numberBranchesLeft());
228    if (best&&best->objectiveValue()>=cutoff) {
229      // double check in case node can change its mind!
230      best->checkIsCutoff(cutoff);
231    }
232    if (!best||best->objectiveValue()>=cutoff) {
233#if 0
234      // take off
235      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
236      nodes_.pop_back();
237      delete best;
238      best=NULL;
239#else
240      // let code get rid of it
241      assert (best);
242#endif
243    }
244  }
245  // switched off for now
246  if (best&&comparison_.test_->fullScan()&&false) {
247    CbcNode * saveBest=best;
248    int n=nodes_.size();
249    int iBest=-1;
250    for (int i=0;i<n;i++) {
251      // temp
252      assert (nodes_[i]);
253      assert (nodes_[i]->nodeInfo());
254      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
255        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
256      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
257          &&comparison_.alternateTest(best,nodes_[i])) {
258        best=nodes_[i];
259        iBest=i;
260      }
261    }
262    if (best==saveBest) {
263      // can pop
264      // take off
265      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
266      nodes_.pop_back();
267    } else {
268      // make impossible
269      nodes_[iBest]=NULL;
270    }
271  } else if (best) {
272    // take off
273    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
274    nodes_.pop_back();
275  }
276#ifdef DEBUG_CBC_HEAP
277  if (best) {
278    int n=nodes_.size();
279    bool good=true;
280    for (int i=0;i<n;i++) {
281      // temp
282      assert (nodes_[i]);
283      if (!comparison_.compareNodes(nodes_[i],best)) {
284        good=false;
285        CbcNode * x = nodes_[i];
286        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
287               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
288               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
289      }
290    }
291    if (!good) {
292      // compare best to all
293      int i;
294      for (i=0;i<n;i++) {
295        CbcNode * x = nodes_[i];
296        printf("i=%d x is nun %d depth %d obj %g",i,
297               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
298        if (!comparison_.compareNodes(x,best)) {
299          printf(" - best is worse!\n");
300        } else {
301          printf("\n");
302        }
303      }
304      // Now compare amongst rest
305      for (i=0;i<n;i++) {
306        CbcNode * x = nodes_[i];
307        printf("For i=%d ",i);
308        for (int j=i+1;j<n;j++) {
309          CbcNode * y = nodes_[j];
310          if (!comparison_.compareNodes(x,y)) {
311            printf(" b %d",j);
312          } else {
313            printf(" w %d",j);
314          }
315        }
316        printf("\n");
317      }
318      assert(good);
319    }
320  }
321#endif
322  if (best)
323    best->setOnTree(false);
324  return best;
325}
326
327double
328CbcTree::getBestPossibleObjective(){
329  double r_val = 1e100;
330  for(int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++){
331    if(nodes_[i] && nodes_[i]->objectiveValue() < r_val){
332      r_val = nodes_[i]->objectiveValue();
333    }
334  }
335  return r_val;
336}
337/*! \brief Prune the tree using an objective function cutoff
338
339  This routine removes all nodes with objective worst than the
340  specified cutoff value.
341*/
342
343void 
344CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
345{
346  int j;
347  int nNodes = size();
348  CbcNode ** nodeArray = new CbcNode * [nNodes];
349  int * depth = new int [nNodes];
350  int k=0;
351  int kDelete=nNodes;
352  bestPossibleObjective = 1.0e100 ;
353/*
354    Destructively scan the heap. Nodes to be retained go into the front of
355    nodeArray, nodes to be deleted into the back. Store the depth in a
356    correlated array for nodes to be deleted.
357*/
358  for (j=0;j<nNodes;j++) {
359    CbcNode * node = top();
360    pop();
361    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
362    if (node&&value>=cutoff) {
363      // double check in case node can change its mind!
364      value=node->checkIsCutoff(cutoff);
365    }
366    if (value >= cutoff||!node->active()) {
367      if (node) {
368        nodeArray[--kDelete] = node;
369        depth[kDelete] = node->depth();
370      }
371    } else {
372      bestPossibleObjective = CoinMin(bestPossibleObjective,value);
373      nodeArray[k++]=node;
374    }
375  }
376/*
377  Rebuild the heap using the retained nodes.
378*/
379  for (j=0;j<k;j++) { push(nodeArray[j]); }
380/*
381  Sort the list of nodes to be deleted, nondecreasing.
382*/
383  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
384/*
385  Work back from deepest to shallowest. In spite of the name, addCuts1 is
386  just a preparatory step. When it returns, the following will be true:
387    * all cuts are removed from the solver's copy of the constraint system;
388    * lastws will be a basis appropriate for the specified node;
389    * variable bounds will be adjusted to be appropriate for the specified
390      node;
391    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
392      should be added to the constraint system at this node (but they have
393      not actually been added).
394  Then we scan the cut list for the node. Decrement the reference count
395  for the cut, and if it's gone to 0, really delete it.
396
397  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
398  are necessary. When reconstructing a node, these checks are used to skip
399  over loose cuts, excluding them from the reconstituted basis. But here
400  we're just interested in correcting the reference count. Tight/loose should
401  make no difference.
402
403  Arguably a separate routine should be used in place of addCuts1. It's doing
404  more work than needed, modifying the model to match a subproblem at a node
405  that will be discarded.  Then again, we seem to need the basis.
406*/
407  for (j=nNodes-1;j >= kDelete;j--) {
408    CbcNode * node = nodeArray[j];
409    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
410   
411    model->addCuts1(node,lastws);
412    // Decrement cut counts
413    assert (node);
414    //assert (node->nodeInfo());
415    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
416    int i;
417    for (i=0;i<model->currentNumberCuts();i++) {
418      // take off node
419      CoinWarmStartBasis::Status status = 
420        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
421      if (status != CoinWarmStartBasis::basic&&
422          model->addedCuts()[i]) {
423        if (!model->addedCuts()[i]->decrement(numberLeft))
424          delete model->addedCuts()[i];
425      }
426    }
427    // node should not have anything pointing to it
428    if (node->nodeInfo())   
429      node->nodeInfo()->throwAway();
430    delete node ;
431    delete lastws ;
432  }
433  delete [] nodeArray;
434  delete [] depth;
435}
436
437// Return the best node of the heap using alternate criterion
438CbcNode * 
439CbcTree::bestAlternate() {
440  int n=nodes_.size();
441  CbcNode * best=NULL;
442  if (n) {
443    best = nodes_[0];
444    for (int i=1;i<n;i++) {
445      if (comparison_.alternateTest(best,nodes_[i])) {
446        best=nodes_[i];
447      }
448    }
449  }
450  return best;
451}
452CbcTreeArray::CbcTreeArray()
453  : CbcTree(),
454    lastNode_(NULL),
455    lastNodePopped_(NULL),
456    switches_(0)
457{
458}
459CbcTreeArray::~CbcTreeArray()
460{
461}
462// Copy constructor
463CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
464  : CbcTree(rhs),
465    lastNode_(rhs.lastNode_),
466    lastNodePopped_(rhs.lastNodePopped_),
467    switches_(rhs.switches_)
468{
469}
470// Assignment operator
471CbcTreeArray &
472CbcTreeArray::operator=(const CbcTreeArray & rhs)
473{
474  if (this != &rhs) {
475    CbcTree::operator=(rhs);
476    lastNode_ = rhs.lastNode_;
477    lastNodePopped_ = rhs.lastNodePopped_;
478    switches_ = rhs.switches_;
479  }
480  return *this;
481}
482// Clone
483CbcTree *
484CbcTreeArray::clone() const
485{
486  return new CbcTreeArray(*this);
487}
488// Set comparison function and resort heap
489void 
490CbcTreeArray::setComparison(CbcCompareBase  &compare)
491{
492  comparison_.test_ = &compare;
493  std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
494}
495
496// Add a node to the heap
497void 
498CbcTreeArray::push(CbcNode * x) {
499  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
500         x->objectiveValue(),x->nodeInfo()->decrement(0),
501         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
502  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
503  x->setOnTree(true);
504  if (lastNode_) {
505    if (lastNode_->nodeInfo()->parent()==x->nodeInfo()) {
506      // x is parent of lastNode_ so put x on heap
507      //#define CBCTREE_PRINT
508#ifdef CBCTREE_PRINT
509      printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
510             x,x->nodeInfo(),x->depth(),x->nodeNumber(),
511             lastNode_,lastNode_->nodeInfo(),lastNode_->depth(),lastNode_->nodeNumber());
512#endif
513      nodes_.push_back(x);
514    } else {
515      x->setNodeNumber(maximumNodeNumber_);
516      maximumNodeNumber_++;
517#ifdef CBCTREE_PRINT
518      printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
519             x,x->nodeInfo(),x->depth(),x->nodeNumber(),
520             lastNode_,lastNode_->nodeInfo(),lastNode_->depth(),lastNode_->nodeNumber());
521#endif
522      nodes_.push_back(lastNode_);
523      lastNode_ = x;
524    }
525    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
526  } else {
527    x->setNodeNumber(maximumNodeNumber_);
528    maximumNodeNumber_++;
529    if (x!=lastNodePopped_) {
530      lastNode_ = x;
531#ifdef CBCTREE_PRINT
532      printf("pushNULL x %x (%x at depth %d n %d)\n",
533             x,x->nodeInfo(),x->depth(),x->nodeNumber());
534#endif
535    } else {
536      // means other way was infeasible
537#ifdef CBCTREE_PRINT
538      printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
539             x,x->nodeInfo(),x->depth(),x->nodeNumber());
540#endif
541      nodes_.push_back(x);
542      std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
543    }
544  }
545}
546
547// Test if empty *** note may be overridden
548bool 
549CbcTreeArray::empty() 
550{ 
551  return nodes_.empty()&&(lastNode_==NULL);
552}
553// Gets best node and takes off heap
554CbcNode * 
555CbcTreeArray::bestNode(double cutoff)
556{
557  CbcNode * best = NULL;
558  // See if we want last node or best on heap
559  if (lastNode_) {
560#ifdef CBCTREE_PRINT
561    printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
562           lastNode_,lastNode_->nodeInfo(),lastNode_->depth(),
563           lastNode_->nodeNumber(),lastNode_->objectiveValue());
564#endif
565    assert (lastNode_->onTree());
566    int nodeNumber = lastNode_->nodeNumber();
567    bool useLastNode=false;
568    if (nodeNumber+1==maximumNodeNumber_) {
569      // diving - look further
570      CbcCompareDefault * compareDefault
571        = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
572      assert (compareDefault);
573      double bestPossible = compareDefault->getBestPossible();
574      double cutoff = compareDefault->getCutoff();
575      double objValue = lastNode_->objectiveValue();
576      if (cutoff<1.0e20) {
577        if (objValue-bestPossible<0.999*(cutoff-bestPossible))
578          useLastNode=true;
579      } else {
580        useLastNode=true;
581      }
582    }
583    if (useLastNode) {
584      lastNode_->setOnTree(false);
585      best = lastNode_;
586      lastNode_=NULL;
587      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
588      if (best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
589        assert (best->nodeInfo()->numberBranchesLeft());
590      if (best->objectiveValue()>=cutoff) {
591        // double check in case node can change its mind!
592        best->checkIsCutoff(cutoff);
593      }
594      lastNodePopped_=best;
595      return best;
596    } else {
597      // put on tree
598      nodes_.push_back(lastNode_);
599      lastNode_->setNodeNumber(maximumNodeNumber_);
600      maximumNodeNumber_++;
601      lastNode_ = NULL;
602      std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
603    }
604  }
605  while (!best&&nodes_.size()) {
606    best = nodes_.front();
607    if (best)
608      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
609    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
610      assert (best->nodeInfo()->numberBranchesLeft());
611    if (best&&best->objectiveValue()>=cutoff) {
612      // double check in case node can change its mind!
613      best->checkIsCutoff(cutoff);
614    }
615    if (!best||best->objectiveValue()>=cutoff) {
616      // let code get rid of it
617      assert (best);
618    }
619  }
620  lastNodePopped_=best;
621#ifdef CBCTREE_PRINT
622  if (best)
623    printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
624           best,best->nodeInfo(),best->depth(),
625           best->nodeNumber(),best->objectiveValue());
626  else
627    printf("Heap returning Null\n");
628#endif
629  if (best) {
630    // take off
631    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
632    nodes_.pop_back();
633  }
634#ifdef DEBUG_CBC_HEAP
635  if (best) {
636    int n=nodes_.size();
637    bool good=true;
638    for (int i=0;i<n;i++) {
639      // temp
640      assert (nodes_[i]);
641      if (!comparison_.compareNodes(nodes_[i],best)) {
642        good=false;
643        CbcNode * x = nodes_[i];
644        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
645               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
646               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
647      }
648    }
649    if (!good) {
650      // compare best to all
651      int i;
652      for (i=0;i<n;i++) {
653        CbcNode * x = nodes_[i];
654        printf("i=%d x is nun %d depth %d obj %g",i,
655               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
656        if (!comparison_.compareNodes(x,best)) {
657          printf(" - best is worse!\n");
658        } else {
659          printf("\n");
660        }
661      }
662      // Now compare amongst rest
663      for (i=0;i<n;i++) {
664        CbcNode * x = nodes_[i];
665        printf("For i=%d ",i);
666        for (int j=i+1;j<n;j++) {
667          CbcNode * y = nodes_[j];
668          if (!comparison_.compareNodes(x,y)) {
669            printf(" b %d",j);
670          } else {
671            printf(" w %d",j);
672          }
673        }
674        printf("\n");
675      }
676      assert(good);
677    }
678  }
679#endif
680  if (best)
681    best->setOnTree(false);
682  return best;
683}
684
685double
686CbcTreeArray::getBestPossibleObjective(){
687  double bestPossibleObjective = 1e100;
688  for(int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++){
689    if(nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective){
690      bestPossibleObjective = nodes_[i]->objectiveValue();
691    }
692  }
693  if (lastNode_) {
694    bestPossibleObjective = CoinMin(bestPossibleObjective,lastNode_->objectiveValue());
695  }
696  CbcCompareDefault * compareDefault
697    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
698  assert (compareDefault);
699  compareDefault->setBestPossible(bestPossibleObjective);
700  return bestPossibleObjective;
701}
702/*! \brief Prune the tree using an objective function cutoff
703
704  This routine removes all nodes with objective worst than the
705  specified cutoff value.
706*/
707
708void 
709CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
710{
711  int j;
712  int nNodes = size();
713  int lastNode = nNodes+1;
714  CbcNode ** nodeArray = new CbcNode * [lastNode];
715  int * depth = new int [lastNode];
716  int k=0;
717  int kDelete=lastNode;
718  bestPossibleObjective = 1.0e100 ;
719/*
720    Destructively scan the heap. Nodes to be retained go into the front of
721    nodeArray, nodes to be deleted into the back. Store the depth in a
722    correlated array for nodes to be deleted.
723*/
724  for (j=0;j<nNodes;j++) {
725    CbcNode * node = nodes_.front();
726    nodes_.front()->setOnTree(false);
727    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
728    nodes_.pop_back();
729    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
730    if (node&&value>=cutoff) {
731      // double check in case node can change its mind!
732      value=node->checkIsCutoff(cutoff);
733    }
734    if (value >= cutoff||!node->active()) {
735      if (node) {
736        nodeArray[--kDelete] = node;
737        depth[kDelete] = node->depth();
738      }
739    } else {
740      bestPossibleObjective = CoinMin(bestPossibleObjective,value);
741      nodeArray[k++]=node;
742    }
743  }
744  if (lastNode_) {
745    double value = lastNode_->objectiveValue();
746    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
747    if (value >= cutoff||!lastNode_->active()) {
748      nodeArray[--kDelete] = lastNode_;
749      depth[kDelete] = lastNode_->depth();
750      lastNode_=NULL;
751    }
752  }
753  CbcCompareDefault * compareDefault
754    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
755  assert (compareDefault);
756  compareDefault->setBestPossible(bestPossibleObjective);
757  compareDefault->setCutoff(cutoff);
758/*
759  Rebuild the heap using the retained nodes.
760*/
761  for (j=0;j<k;j++) { 
762    CbcNode * node = nodeArray[j];
763    node->setOnTree(true);
764    nodes_.push_back(node);
765    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
766  }
767/*
768  Sort the list of nodes to be deleted, nondecreasing.
769*/
770  CoinSort_2(depth+kDelete,depth+lastNode,nodeArray+kDelete);
771/*
772  Work back from deepest to shallowest. In spite of the name, addCuts1 is
773  just a preparatory step. When it returns, the following will be true:
774    * all cuts are removed from the solver's copy of the constraint system;
775    * lastws will be a basis appropriate for the specified node;
776    * variable bounds will be adjusted to be appropriate for the specified
777      node;
778    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
779      should be added to the constraint system at this node (but they have
780      not actually been added).
781  Then we scan the cut list for the node. Decrement the reference count
782  for the cut, and if it's gone to 0, really delete it.
783
784  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
785  are necessary. When reconstructing a node, these checks are used to skip
786  over loose cuts, excluding them from the reconstituted basis. But here
787  we're just interested in correcting the reference count. Tight/loose should
788  make no difference.
789
790  Arguably a separate routine should be used in place of addCuts1. It's doing
791  more work than needed, modifying the model to match a subproblem at a node
792  that will be discarded.  Then again, we seem to need the basis.
793*/
794  for (j=lastNode-1;j >= kDelete;j--) {
795    CbcNode * node = nodeArray[j];
796    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
797   
798    model->addCuts1(node,lastws);
799    // Decrement cut counts
800    assert (node);
801    //assert (node->nodeInfo());
802    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
803    int i;
804    for (i=0;i<model->currentNumberCuts();i++) {
805      // take off node
806      CoinWarmStartBasis::Status status = 
807        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
808      if (status != CoinWarmStartBasis::basic&&
809          model->addedCuts()[i]) {
810        if (!model->addedCuts()[i]->decrement(numberLeft))
811          delete model->addedCuts()[i];
812      }
813    }
814    // node should not have anything pointing to it
815    if (node->nodeInfo())   
816      node->nodeInfo()->throwAway();
817    delete node ;
818    delete lastws ;
819  }
820  delete [] nodeArray;
821  delete [] depth;
822}
823#else
824// Set comparison function and resort heap
825void 
826CbcTree::setComparison(CbcCompareBase  &compare)
827{
828  comparison_.test_ = &compare;
829  std::vector <CbcNode *> newNodes=nodes_;
830  nodes_.resize(0);
831  while (newNodes.size()>0) {
832    push( newNodes.back());
833    newNodes.pop_back();
834  }
835}
836
837// Return the top node of the heap
838CbcNode * 
839CbcTree::top() const
840{
841  return nodes_.front();
842}
843
844// Add a node to the heap
845void 
846CbcTree::push(CbcNode * x) {
847  x->setNodeNumber(maximumNodeNumber_);
848  maximumNodeNumber_++;
849  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
850         x->objectiveValue(),x->nodeInfo()->decrement(0),
851         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
852  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
853#if 0
854  nodes_.push_back(x);
855  push_heap(nodes_.begin(), nodes_.end(), comparison_);
856#else
857  realpush(x);
858#endif
859}
860
861// Remove the top node from the heap
862void 
863CbcTree::pop() {
864#if 0
865  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
866  nodes_.pop_back();
867#else
868  if (nodes_.size()) {
869    //CbcNode* s = nodes_.front();
870    realpop();
871    //delete s;
872  }
873  assert (nodes_.size()>=0);
874#endif
875}
876
877// Test if empty *** note may be overridden
878bool 
879CbcTree::empty() 
880{ 
881  return nodes_.empty();
882}
883// Gets best node and takes off heap
884CbcNode * 
885CbcTree::bestNode(double cutoff)
886{
887  CbcNode * best = NULL;
888  while (!best&&nodes_.size()) {
889    best = nodes_.front();
890    if (best)
891      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
892    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
893      assert (best->nodeInfo()->numberBranchesLeft());
894    if (best&&best->objectiveValue()>=cutoff) {
895      // double check in case node can change its mind!
896      best->checkIsCutoff(cutoff);
897    }
898    if (!best||best->objectiveValue()>=cutoff) {
899#if 0
900      // take off
901      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
902      nodes_.pop_back();
903      delete best;
904      best=NULL;
905#else
906      // let code get rid of it
907      assert (best);
908#endif
909    }
910  }
911  // switched off for now
912  if (best&&comparison_.test_->fullScan()&&false) {
913    CbcNode * saveBest=best;
914    int n=nodes_.size();
915    int iBest=-1;
916    for (int i=0;i<n;i++) {
917      // temp
918      assert (nodes_[i]);
919      assert (nodes_[i]->nodeInfo());
920      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
921        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
922      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
923          &&comparison_.alternateTest(best,nodes_[i])) {
924        best=nodes_[i];
925        iBest=i;
926      }
927    }
928    if (best==saveBest) {
929      // can pop
930      // take off
931      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
932      nodes_.pop_back();
933    } else {
934      // make impossible
935      nodes_[iBest]=NULL;
936    }
937  } else if (best) {
938    // take off
939#if 0
940    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
941    nodes_.pop_back();
942#else
943    realpop();
944#endif
945  }
946#ifdef DEBUG_CBC_HEAP
947  if (best) {
948    int n=nodes_.size();
949    bool good=true;
950    for (int i=0;i<n;i++) {
951      // temp
952      assert (nodes_[i]);
953      if (!comparison_.compareNodes(nodes_[i],best)) {
954        good=false;
955        CbcNode * x = nodes_[i];
956        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
957               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
958               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
959      }
960    }
961    if (!good) {
962      // compare best to all
963      int i;
964      for (i=0;i<n;i++) {
965        CbcNode * x = nodes_[i];
966        printf("i=%d x is nun %d depth %d obj %g",i,
967               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
968        if (!comparison_.compareNodes(x,best)) {
969          printf(" - best is worse!\n");
970        } else {
971          printf("\n");
972        }
973      }
974      // Now compare amongst rest
975      for (i=0;i<n;i++) {
976        CbcNode * x = nodes_[i];
977        printf("For i=%d ",i);
978        for (int j=i+1;j<n;j++) {
979          CbcNode * y = nodes_[j];
980          if (!comparison_.compareNodes(x,y)) {
981            printf(" b %d",j);
982          } else {
983            printf(" w %d",j);
984          }
985        }
986        printf("\n");
987      }
988      assert(good);
989    }
990  }
991#endif
992  if (best)
993    best->setOnTree(false);
994  return best;
995}
996
997/*! \brief Prune the tree using an objective function cutoff
998
999  This routine removes all nodes with objective worst than the
1000  specified cutoff value.
1001*/
1002
1003void 
1004CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1005{
1006  int j;
1007  int nNodes = nodes_.size();
1008  CbcNode ** nodeArray = new CbcNode * [nNodes];
1009  int * depth = new int [nNodes];
1010  int k=0;
1011  int kDelete=nNodes;
1012  bestPossibleObjective = 1.0e100 ;
1013/*
1014    Destructively scan the heap. Nodes to be retained go into the front of
1015    nodeArray, nodes to be deleted into the back. Store the depth in a
1016    correlated array for nodes to be deleted.
1017*/
1018  for (j=0;j<nNodes;j++) {
1019    CbcNode * node = top();
1020    pop();
1021    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1022    if (node&&value>=cutoff) {
1023      // double check in case node can change its mind!
1024      value=node->checkIsCutoff(cutoff);
1025    }
1026    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
1027    if (value >= cutoff) {
1028      if (node) {
1029        nodeArray[--kDelete] = node;
1030        depth[kDelete] = node->depth();
1031      }
1032    } else {
1033      nodeArray[k++]=node;
1034    }
1035  }
1036/*
1037  Rebuild the heap using the retained nodes.
1038*/
1039  for (j=0;j<k;j++) { push(nodeArray[j]); }
1040/*
1041  Sort the list of nodes to be deleted, nondecreasing.
1042*/
1043  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
1044/*
1045  Work back from deepest to shallowest. In spite of the name, addCuts1 is
1046  just a preparatory step. When it returns, the following will be true:
1047    * all cuts are removed from the solver's copy of the constraint system;
1048    * lastws will be a basis appropriate for the specified node;
1049    * variable bounds will be adjusted to be appropriate for the specified
1050      node;
1051    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1052      should be added to the constraint system at this node (but they have
1053      not actually been added).
1054  Then we scan the cut list for the node. Decrement the reference count
1055  for the cut, and if it's gone to 0, really delete it.
1056
1057  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1058  are necessary. When reconstructing a node, these checks are used to skip
1059  over loose cuts, excluding them from the reconstituted basis. But here
1060  we're just interested in correcting the reference count. Tight/loose should
1061  make no difference.
1062
1063  Arguably a separate routine should be used in place of addCuts1. It's doing
1064  more work than needed, modifying the model to match a subproblem at a node
1065  that will be discarded.  Then again, we seem to need the basis.
1066*/
1067  for (j=nNodes-1;j >= kDelete;j--) {
1068    CbcNode * node = nodeArray[j];
1069    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1070   
1071    model->addCuts1(node,lastws);
1072    // Decrement cut counts
1073    assert (node);
1074    //assert (node->nodeInfo());
1075    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1076    int i;
1077    for (i=0;i<model->currentNumberCuts();i++) {
1078      // take off node
1079      CoinWarmStartBasis::Status status = 
1080        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
1081      if (status != CoinWarmStartBasis::basic&&
1082          model->addedCuts()[i]) {
1083        if (!model->addedCuts()[i]->decrement(numberLeft))
1084          delete model->addedCuts()[i];
1085      }
1086    }
1087    // node should not have anything pointing to it
1088    if (node->nodeInfo())   
1089      node->nodeInfo()->throwAway();
1090    delete node ;
1091    delete lastws ;
1092  }
1093  delete [] nodeArray;
1094  delete [] depth;
1095}
1096
1097// Return the best node of the heap using alternate criterion
1098CbcNode * 
1099CbcTree::bestAlternate() {
1100  int n=nodes_.size();
1101  CbcNode * best=NULL;
1102  if (n) {
1103    best = nodes_[0];
1104    for (int i=1;i<n;i++) {
1105      if (comparison_.alternateTest(best,nodes_[i])) {
1106        best=nodes_[i];
1107      }
1108    }
1109  }
1110  return best;
1111}
1112void 
1113CbcTree::realpop() {
1114  if (nodes_.size()>0) {
1115    nodes_[0] = nodes_.back();
1116    nodes_.pop_back();
1117    fixTop();
1118  }
1119  assert (nodes_.size()>=0);
1120}
1121/* After changing data in the top node, fix the heap */
1122void 
1123CbcTree::fixTop() {
1124  const int size = nodes_.size();
1125  if (size > 1) {
1126    CbcNode** candidates = &nodes_[0];
1127    CbcNode* s = candidates[0];
1128    --candidates;
1129    int pos = 1;
1130    int ch;
1131    for (ch = 2; ch < size; pos = ch, ch *= 2) {
1132      if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1133        ++ch;
1134      if (!comparison_.compareNodes(s, candidates[ch]))
1135        break;
1136      candidates[pos] = candidates[ch];
1137    }
1138    if (ch == size) {
1139      if (!comparison_.compareNodes(candidates[ch], s)) {
1140        candidates[pos] = candidates[ch];
1141        pos = ch;
1142      }
1143    }
1144    candidates[pos] = s;
1145  }
1146}
1147void 
1148CbcTree::realpush(CbcNode * node) {
1149  node->setOnTree(true);
1150  nodes_.push_back(node);
1151  CbcNode** candidates = &nodes_[0];
1152  --candidates;
1153  int pos = nodes_.size();
1154  int ch;
1155  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
1156    if (!comparison_.compareNodes(candidates[ch], node))
1157      break;
1158    candidates[pos] = candidates[ch];
1159  }
1160  candidates[pos] = node;
1161}
1162#endif
Note: See TracBrowser for help on using the repository browser.