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

Last change on this file since 424 was 424, checked in by forrest, 13 years ago

many changes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.2 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->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo());
79    if (best&&best->objectiveValue()!=COIN_DBL_MAX&&best->nodeInfo())
80      assert (best->nodeInfo()->numberBranchesLeft());
81    if (!best||best->objectiveValue()>=cutoff) {
82      // take off
83      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
84      nodes_.pop_back();
85      best=NULL;
86    }
87  }
88  // switched off for now
89  if (best&&comparison_.test_->fullScan()&&false) {
90    CbcNode * saveBest=best;
91    int n=nodes_.size();
92    int iBest=-1;
93    for (int i=0;i<n;i++) {
94      // temp
95      assert (nodes_[i]);
96      assert (nodes_[i]->nodeInfo());
97      if (nodes_[i]&&nodes_[i]->objectiveValue()!=COIN_DBL_MAX&&nodes_[i]->nodeInfo())
98        assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
99      if (nodes_[i]&&nodes_[i]->objectiveValue()<cutoff
100          &&comparison_.alternateTest(best,nodes_[i])) {
101        best=nodes_[i];
102        iBest=i;
103      }
104    }
105    if (best==saveBest) {
106      // can pop
107      // take off
108      pop_heap(nodes_.begin(), nodes_.end(), comparison_);
109      nodes_.pop_back();
110    } else {
111      // make impossible
112      nodes_[iBest]=NULL;
113    }
114  } else if (best) {
115    // take off
116    pop_heap(nodes_.begin(), nodes_.end(), comparison_);
117    nodes_.pop_back();
118  }
119  return best;
120}
121
122/*! \brief Prune the tree using an objective function cutoff
123
124  This routine removes all nodes with objective worst than the
125  specified cutoff value.
126*/
127
128void 
129CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
130{
131  int j;
132  int nNodes = size();
133  CbcNode ** nodeArray = new CbcNode * [nNodes];
134  int * depth = new int [nNodes];
135  int k=0;
136  int kDelete=nNodes;
137  bestPossibleObjective = 1.0e100 ;
138/*
139    Destructively scan the heap. Nodes to be retained go into the front of
140    nodeArray, nodes to be deleted into the back. Store the depth in a
141    correlated array for nodes to be deleted.
142*/
143  for (j=0;j<nNodes;j++) {
144    CbcNode * node = top();
145    pop();
146    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
147    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
148    if (value >= cutoff) {
149      if (node) {
150        nodeArray[--kDelete] = node;
151        depth[kDelete] = node->depth();
152      }
153    } else {
154      nodeArray[k++]=node;
155    }
156  }
157/*
158  Rebuild the heap using the retained nodes.
159*/
160  for (j=0;j<k;j++) { push(nodeArray[j]); }
161/*
162  Sort the list of nodes to be deleted, nondecreasing.
163*/
164  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
165/*
166  Work back from deepest to shallowest. In spite of the name, addCuts1 is
167  just a preparatory step. When it returns, the following will be true:
168    * all cuts are removed from the solver's copy of the constraint system;
169    * lastws will be a basis appropriate for the specified node;
170    * variable bounds will be adjusted to be appropriate for the specified
171      node;
172    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
173      should be added to the constraint system at this node (but they have
174      not actually been added).
175  Then we scan the cut list for the node. Decrement the reference count
176  for the cut, and if it's gone to 0, really delete it.
177
178  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
179  are necessary. When reconstructing a node, these checks are used to skip
180  over loose cuts, excluding them from the reconstituted basis. But here
181  we're just interested in correcting the reference count. Tight/loose should
182  make no difference.
183
184  Arguably a separate routine should be used in place of addCuts1. It's doing
185  more work than needed, modifying the model to match a subproblem at a node
186  that will be discarded.  Then again, we seem to need the basis.
187*/
188  for (j=nNodes-1;j >= kDelete;j--) {
189    CbcNode * node = nodeArray[j];
190    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
191   
192    model->addCuts1(node,lastws);
193    // Decrement cut counts
194    assert (node);
195    //assert (node->nodeInfo());
196    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
197    int i;
198    for (i=0;i<model->currentNumberCuts();i++) {
199      // take off node
200      CoinWarmStartBasis::Status status = 
201        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
202      if (status != CoinWarmStartBasis::basic&&
203          model->addedCuts()[i]) {
204        if (!model->addedCuts()[i]->decrement(numberLeft))
205          delete model->addedCuts()[i];
206      }
207    }
208    // node should not have anything pointing to it
209    if (node->nodeInfo())   
210      node->nodeInfo()->throwAway();
211    delete node ;
212    delete lastws ;
213  }
214  delete [] nodeArray;
215  delete [] depth;
216}
217
218// Return the best node of the heap using alternate criterion
219CbcNode * 
220CbcTree::bestAlternate() {
221  int n=nodes_.size();
222  CbcNode * best=NULL;
223  if (n) {
224    best = nodes_[0];
225    for (int i=1;i<n;i++) {
226      if (comparison_.alternateTest(best,nodes_[i])) {
227        best=nodes_[i];
228      }
229    }
230  }
231  return best;
232}
233
Note: See TracBrowser for help on using the repository browser.