source: branches/heur/Cbc/src/CbcTree.cpp @ 885

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

for deterministic parallel

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