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

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

chnages to try and make faster

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 33.4 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}
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}
822#else
823// Set comparison function and resort heap
824void 
825CbcTree::setComparison(CbcCompareBase  &compare)
826{
827  comparison_.test_ = &compare;
828  std::vector <CbcNode *> newNodes=nodes_;
829  nodes_.resize(0);
830  while (newNodes.size()>0) {
831    push( newNodes.back());
832    newNodes.pop_back();
833  }
834}
835
836// Return the top node of the heap
837CbcNode * 
838CbcTree::top() const
839{
840  return nodes_.front();
841}
842
843// Add a node to the heap
844void 
845CbcTree::push(CbcNode * x) {
846  x->setNodeNumber(maximumNodeNumber_);
847  maximumNodeNumber_++;
848  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
849         x->objectiveValue(),x->nodeInfo()->decrement(0),
850         x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
851  assert(x->objectiveValue()!=COIN_DBL_MAX&&x->nodeInfo());
852#if 0
853  nodes_.push_back(x);
854  push_heap(nodes_.begin(), nodes_.end(), comparison_);
855#else
856  realpush(x);
857#endif
858}
859
860// Remove the top node from the heap
861void 
862CbcTree::pop() {
863#if 0
864  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
865  nodes_.pop_back();
866#else
867  if (nodes_.size()) {
868    //CbcNode* s = nodes_.front();
869    realpop();
870    //delete s;
871  }
872  assert (nodes_.size()>=0);
873#endif
874}
875
876// Test if empty *** note may be overridden
877bool 
878CbcTree::empty() 
879{ 
880  return nodes_.empty();
881}
882// Gets best node and takes off heap
883CbcNode * 
884CbcTree::bestNode(double cutoff)
885{
886  CbcNode * best = NULL;
887  while (!best&&nodes_.size()) {
888    best = nodes_.front();
889    if (best)
890      assert(best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
891    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
892      assert (best->nodeInfo()->numberBranchesLeft());
893    if (best&&best->objectiveValue()>=cutoff) {
894      // double check in case node can change its mind!
895      best->checkIsCutoff(cutoff);
896    }
897    if (!best||best->objectiveValue()>=cutoff) {
898#if 0
899      // take off
900      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
901      nodes_.pop_back();
902      delete best;
903      best=NULL;
904#else
905      // let code get rid of it
906      assert (best);
907#endif
908    }
909  }
910  // switched off for now
911  if (best&&comparison_.test_->fullScan()&&false) {
912    CbcNode * saveBest=best;
913    int n=nodes_.size();
914    int iBest=-1;
915    for (int i=0;i<n;i++) {
916      // temp
917      assert (nodes_[i]);
918      assert (nodes_[i]->nodeInfo());
919      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
920        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
921      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
922          &&comparison_.alternateTest(best,nodes_[i])) {
923        best=nodes_[i];
924        iBest=i;
925      }
926    }
927    if (best==saveBest) {
928      // can pop
929      // take off
930      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
931      nodes_.pop_back();
932    } else {
933      // make impossible
934      nodes_[iBest]=NULL;
935    }
936  } else if (best) {
937    // take off
938#if 0
939    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
940    nodes_.pop_back();
941#else
942    realpop();
943#endif
944  }
945#ifdef DEBUG_CBC_HEAP
946  if (best) {
947    int n=nodes_.size();
948    bool good=true;
949    for (int i=0;i<n;i++) {
950      // temp
951      assert (nodes_[i]);
952      if (!comparison_.compareNodes(nodes_[i],best)) {
953        good=false;
954        CbcNode * x = nodes_[i];
955        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n",i,
956               x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
957               best->numberUnsatisfied(),best->depth(),best->objectiveValue()); 
958      }
959    }
960    if (!good) {
961      // compare best to all
962      int i;
963      for (i=0;i<n;i++) {
964        CbcNode * x = nodes_[i];
965        printf("i=%d x is nun %d depth %d obj %g",i,
966               x->numberUnsatisfied(),x->depth(),x->objectiveValue());
967        if (!comparison_.compareNodes(x,best)) {
968          printf(" - best is worse!\n");
969        } else {
970          printf("\n");
971        }
972      }
973      // Now compare amongst rest
974      for (i=0;i<n;i++) {
975        CbcNode * x = nodes_[i];
976        printf("For i=%d ",i);
977        for (int j=i+1;j<n;j++) {
978          CbcNode * y = nodes_[j];
979          if (!comparison_.compareNodes(x,y)) {
980            printf(" b %d",j);
981          } else {
982            printf(" w %d",j);
983          }
984        }
985        printf("\n");
986      }
987      assert(good);
988    }
989  }
990#endif
991  if (best)
992    best->setOnTree(false);
993  return best;
994}
995
996/*! \brief Prune the tree using an objective function cutoff
997
998  This routine removes all nodes with objective worst than the
999  specified cutoff value.
1000*/
1001
1002void 
1003CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1004{
1005  int j;
1006  int nNodes = nodes_.size();
1007  CbcNode ** nodeArray = new CbcNode * [nNodes];
1008  int * depth = new int [nNodes];
1009  int k=0;
1010  int kDelete=nNodes;
1011  bestPossibleObjective = 1.0e100 ;
1012/*
1013    Destructively scan the heap. Nodes to be retained go into the front of
1014    nodeArray, nodes to be deleted into the back. Store the depth in a
1015    correlated array for nodes to be deleted.
1016*/
1017  for (j=0;j<nNodes;j++) {
1018    CbcNode * node = top();
1019    pop();
1020    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1021    if (node&&value>=cutoff) {
1022      // double check in case node can change its mind!
1023      value=node->checkIsCutoff(cutoff);
1024    }
1025    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
1026    if (value >= cutoff) {
1027      if (node) {
1028        nodeArray[--kDelete] = node;
1029        depth[kDelete] = node->depth();
1030      }
1031    } else {
1032      nodeArray[k++]=node;
1033    }
1034  }
1035/*
1036  Rebuild the heap using the retained nodes.
1037*/
1038  for (j=0;j<k;j++) { push(nodeArray[j]); }
1039/*
1040  Sort the list of nodes to be deleted, nondecreasing.
1041*/
1042  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
1043/*
1044  Work back from deepest to shallowest. In spite of the name, addCuts1 is
1045  just a preparatory step. When it returns, the following will be true:
1046    * all cuts are removed from the solver's copy of the constraint system;
1047    * lastws will be a basis appropriate for the specified node;
1048    * variable bounds will be adjusted to be appropriate for the specified
1049      node;
1050    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1051      should be added to the constraint system at this node (but they have
1052      not actually been added).
1053  Then we scan the cut list for the node. Decrement the reference count
1054  for the cut, and if it's gone to 0, really delete it.
1055
1056  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1057  are necessary. When reconstructing a node, these checks are used to skip
1058  over loose cuts, excluding them from the reconstituted basis. But here
1059  we're just interested in correcting the reference count. Tight/loose should
1060  make no difference.
1061
1062  Arguably a separate routine should be used in place of addCuts1. It's doing
1063  more work than needed, modifying the model to match a subproblem at a node
1064  that will be discarded.  Then again, we seem to need the basis.
1065*/
1066  for (j=nNodes-1;j >= kDelete;j--) {
1067    CbcNode * node = nodeArray[j];
1068    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1069   
1070    model->addCuts1(node,lastws);
1071    // Decrement cut counts
1072    assert (node);
1073    //assert (node->nodeInfo());
1074    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1075    int i;
1076    for (i=0;i<model->currentNumberCuts();i++) {
1077      // take off node
1078      CoinWarmStartBasis::Status status = 
1079        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
1080      if (status != CoinWarmStartBasis::basic&&
1081          model->addedCuts()[i]) {
1082        if (!model->addedCuts()[i]->decrement(numberLeft))
1083          delete model->addedCuts()[i];
1084      }
1085    }
1086    // node should not have anything pointing to it
1087    if (node->nodeInfo())   
1088      node->nodeInfo()->throwAway();
1089    delete node ;
1090    delete lastws ;
1091  }
1092  delete [] nodeArray;
1093  delete [] depth;
1094}
1095
1096// Return the best node of the heap using alternate criterion
1097CbcNode * 
1098CbcTree::bestAlternate() {
1099  int n=nodes_.size();
1100  CbcNode * best=NULL;
1101  if (n) {
1102    best = nodes_[0];
1103    for (int i=1;i<n;i++) {
1104      if (comparison_.alternateTest(best,nodes_[i])) {
1105        best=nodes_[i];
1106      }
1107    }
1108  }
1109  return best;
1110}
1111void 
1112CbcTree::realpop() {
1113  if (nodes_.size()>0) {
1114    nodes_[0] = nodes_.back();
1115    nodes_.pop_back();
1116    fixTop();
1117  }
1118  assert (nodes_.size()>=0);
1119}
1120/* After changing data in the top node, fix the heap */
1121void 
1122CbcTree::fixTop() {
1123  const int size = nodes_.size();
1124  if (size > 1) {
1125    CbcNode** candidates = &nodes_[0];
1126    CbcNode* s = candidates[0];
1127    --candidates;
1128    int pos = 1;
1129    int ch;
1130    for (ch = 2; ch < size; pos = ch, ch *= 2) {
1131      if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1132        ++ch;
1133      if (!comparison_.compareNodes(s, candidates[ch]))
1134        break;
1135      candidates[pos] = candidates[ch];
1136    }
1137    if (ch == size) {
1138      if (!comparison_.compareNodes(candidates[ch], s)) {
1139        candidates[pos] = candidates[ch];
1140        pos = ch;
1141      }
1142    }
1143    candidates[pos] = s;
1144  }
1145}
1146void 
1147CbcTree::realpush(CbcNode * node) {
1148  node->setOnTree(true);
1149  nodes_.push_back(node);
1150  CbcNode** candidates = &nodes_[0];
1151  --candidates;
1152  int pos = nodes_.size();
1153  int ch;
1154  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
1155    if (!comparison_.compareNodes(candidates[ch], node))
1156      break;
1157    candidates[pos] = candidates[ch];
1158  }
1159  candidates[pos] = node;
1160}
1161#endif
Note: See TracBrowser for help on using the repository browser.