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

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

changes to try and improve performance

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