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

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

update branches/devel for threads

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