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

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

towards common use with other solvers

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