source: trunk/CbcTree.cpp @ 129

Last change on this file since 129 was 54, checked in by forrest, 16 years ago

add getBestPossibleObjective for Matt Galati

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.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() {
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
70/*! \brief Prune the tree using an objective function cutoff
71
72  This routine removes all nodes with objective worst than the
73  specified cutoff value.
74*/
75
76void 
77CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
78{
79  int j;
80  int nNodes = size();
81  CbcNode ** nodeArray = new CbcNode * [nNodes];
82  int * depth = new int [nNodes];
83  int k=0;
84  int kDelete=nNodes;
85  bestPossibleObjective = 1.0e100 ;
86/*
87    Destructively scan the heap. Nodes to be retained go into the front of
88    nodeArray, nodes to be deleted into the back. Store the depth in a
89    correlated array for nodes to be deleted.
90*/
91  for (j=0;j<nNodes;j++) {
92    CbcNode * node = top();
93    pop();
94    double value = node->objectiveValue();
95    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
96    if (value >= cutoff) {
97      nodeArray[--kDelete] = node;
98      depth[kDelete] = node->depth();
99    } else {
100      nodeArray[k++]=node;
101    }
102  }
103/*
104  Rebuild the heap using the retained nodes.
105*/
106  for (j=0;j<k;j++) { push(nodeArray[j]); }
107/*
108  Sort the list of nodes to be deleted, nondecreasing.
109*/
110  CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
111/*
112  Work back from deepest to shallowest. In spite of the name, addCuts1 is
113  just a preparatory step. When it returns, the following will be true:
114    * all cuts are removed from the solver's copy of the constraint system;
115    * lastws will be a basis appropriate for the specified node;
116    * variable bounds will be adjusted to be appropriate for the specified
117      node;
118    * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
119      should be added to the constraint system at this node (but they have
120      not actually been added).
121  Then we scan the cut list for the node. Decrement the reference count
122  for the cut, and if it's gone to 0, really delete it.
123
124  I don't yet see why the checks for status != basic and addedCuts_[i] != 0
125  are necessary. When reconstructing a node, these checks are used to skip
126  over loose cuts, excluding them from the reconstituted basis. But here
127  we're just interested in correcting the reference count. Tight/loose should
128  make no difference.
129
130  Arguably a separate routine should be used in place of addCuts1. It's doing
131  more work than needed, modifying the model to match a subproblem at a node
132  that will be discarded.  Then again, we seem to need the basis.
133*/
134  for (j=nNodes-1;j >= kDelete;j--) {
135    CbcNode * node = nodeArray[j];
136    CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
137   
138    model->addCuts1(node,lastws);
139    // Decrement cut counts
140    int numberLeft = node->nodeInfo()->numberBranchesLeft();
141    int i;
142    for (i=0;i<model->currentNumberCuts();i++) {
143      // take off node
144      CoinWarmStartBasis::Status status = 
145        lastws->getArtifStatus(i+model->numberRowsAtContinuous());
146      if (status != CoinWarmStartBasis::basic&&
147          model->addedCuts()[i]) {
148        if (!model->addedCuts()[i]->decrement(numberLeft))
149          delete model->addedCuts()[i];
150      }
151    }
152    // node should not have anything pointing to it
153    node->nodeInfo()->throwAway();
154    delete node ;
155    delete lastws ;
156  }
157  delete [] nodeArray;
158  delete [] depth;
159};
160
161
Note: See TracBrowser for help on using the repository browser.