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

Last change on this file since 417 was 317, checked in by andreasw, 14 years ago

Several fixes to make autotools work on Cygwin

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