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

Last change on this file since 782 was 782, checked in by andreasw, 13 years ago

bugfix suggested by Pierre in CbcTree::getBestPossibleObjective

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