source: branches/devel/Cbc/src/CbcTree.cpp @ 419

Last change on this file since 419 was 419, checked in by forrest, 15 years ago

possible bug in tree

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 5.9 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
9CbcTree::CbcTree()
10{
11}
12CbcTree::~CbcTree()
13{
14}
15// Copy constructor
16CbcTree::CbcTree ( const CbcTree & rhs)
17{
18  nodes_=rhs.nodes_;
19}
20// Assignment operator
21CbcTree &
22CbcTree::operator=(const CbcTree & rhs)
23{
24  if (this != &rhs) {
25    nodes_=rhs.nodes_;
26  }
27  return *this;
28}
29// Clone
30CbcTree *
31CbcTree::clone() const
32{
33  return new CbcTree(*this);
34}
35// Set comparison function and resort heap
36void 
37CbcTree::setComparison(CbcCompareBase  &compare)
38{
39  comparison_.test_ = &compare;
40  make_heap(nodes_.begin(), nodes_.end(), comparison_);
41}
42
43// Return the top node of the heap
44CbcNode * 
45CbcTree::top() const
46{
47  return nodes_.front();
48}
49
50// Add a node to the heap
51void 
52CbcTree::push(CbcNode * x) {
53  nodes_.push_back(x);
54  push_heap(nodes_.begin(), nodes_.end(), comparison_);
55}
56
57// Remove the top node from the heap
58void 
59CbcTree::pop() {
60  pop_heap(nodes_.begin(), nodes_.end(), comparison_);
61  nodes_.pop_back();
62}
63
64// Test if empty *** note may be overridden
65bool 
66CbcTree::empty() 
67{ 
68  return nodes_.empty();
69}
70// Gets best node and takes off heap
71CbcNode * 
72CbcTree::bestNode(double cutoff)
73{
74  CbcNode * best = NULL;
75  while (!best&&nodes_.size()) {
76    best = nodes_.front();
77    if (best)
78      assert (best->nodeInfo()->numberBranchesLeft());
79    if (!best||best->objectiveValue()>=cutoff) {
80      // take off
81      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
82      nodes_.pop_back();
83      best=NULL;
84    }
85  }
86  if (best&&comparison_.test_->fullScan()) {
87    CbcNode * saveBest=best;
88    int n=nodes_.size();
89    int iBest=-1;
90    for (int i=0;i<n;i++) {
91      if (nodes_[i])
92        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
93      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
94          &&comparison_.alternateTest(best,nodes_[i])) {
95        best=nodes_[i];
96        iBest=i;
97      }
98    }
99    if (best==saveBest) {
100      // can pop
101      // take off
102      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
103      nodes_.pop_back();
104    } else {
105      // make impossible
106      nodes_[iBest]=NULL;
107      printf("needs coding CbcTree::bestNode\n");
108      abort();
109    }
110  } else if (best) {
111    // take off
112    pop_heap(nodes_.begin(), nodes_.end(), comparison_);
113    nodes_.pop_back();
114  }
115  return best;
116}
117
118/*! \brief Prune the tree using an objective function cutoff
119
120  This routine removes all nodes with objective worst than the
121  specified cutoff value.
122*/
123
124void 
125CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
126{
127  int j;
128  int nNodes = size();
129  CbcNode ** nodeArray = new CbcNode * [nNodes];
130  int * depth = new int [nNodes];
131  int k=0;
132  int kDelete=nNodes;
133  bestPossibleObjective = 1.0e100 ;
134/*
135    Destructively scan the heap. Nodes to be retained go into the front of
136    nodeArray, nodes to be deleted into the back. Store the depth in a
137    correlated array for nodes to be deleted.
138*/
139  for (j=0;j<nNodes;j++) {
140    CbcNode * node = top();
141    pop();
142    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
143    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
144    if (value >= cutoff) {
145      if (node) {
146        nodeArray[--kDelete] = node;
147        depth[kDelete] = node->depth();
148      }
149    } else {
150      nodeArray[k++]=node;
151    }
152  }
153/*
154  Rebuild the heap using the retained nodes.
155*/
156  for (j=0;j<k;j++) { push(nodeArray[j]); }
157/*
158  Sort the list of nodes to be deleted, nondecreasing.
159*/
160  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
161/*
162  Work back from deepest to shallowest. In spite of the name, addCuts1 is
163  just a preparatory step. When it returns, the following will be true:
164    * all cuts are removed from the solver's copy of the constraint system;
165    * lastws will be a basis appropriate for the specified node;
166    * variable bounds will be adjusted to be appropriate for the specified
167      node;
168    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
169      should be added to the constraint system at this node (but they have
170      not actually been added).
171  Then we scan the cut list for the node. Decrement the reference count
172  for the cut, and if it's gone to 0, really delete it.
173
174  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
175  are necessary. When reconstructing a node, these checks are used to skip
176  over loose cuts, excluding them from the reconstituted basis. But here
177  we're just interested in correcting the reference count. Tight/loose should
178  make no difference.
179
180  Arguably a separate routine should be used in place of addCuts1. It's doing
181  more work than needed, modifying the model to match a subproblem at a node
182  that will be discarded.  Then again, we seem to need the basis.
183*/
184  for (j=nNodes-1;j >= kDelete;j--) {
185    CbcNode * node = nodeArray[j];
186    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
187   
188    model->addCuts1(node,lastws);
189    // Decrement cut counts
190    int numberLeft = node->nodeInfo()->numberBranchesLeft();
191    int i;
192    for (i=0;i<model->currentNumberCuts();i++) {
193      // take off node
194      CoinWarmStartBasis::Status status = 
195        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
196      if (status != CoinWarmStartBasis::basic&&
197          model->addedCuts()[i]) {
198        if (!model->addedCuts()[i]->decrement(numberLeft))
199          delete model->addedCuts()[i];
200      }
201    }
202    // node should not have anything pointing to it
203    node->nodeInfo()->throwAway();
204    delete node ;
205    delete lastws ;
206  }
207  delete [] nodeArray;
208  delete [] depth;
209}
210
211// Return the best node of the heap using alternate criterion
212CbcNode * 
213CbcTree::bestAlternate() {
214  int n=nodes_.size();
215  CbcNode * best=NULL;
216  if (n) {
217    best = nodes_[0];
218    for (int i=1;i<n;i++) {
219      if (comparison_.alternateTest(best,nodes_[i])) {
220        best=nodes_[i];
221      }
222    }
223  }
224  return best;
225}
226
Note: See TracBrowser for help on using the repository browser.