source: trunk/CbcTree.cpp @ 2

Last change on this file since 2 was 2, checked in by ladanyi, 15 years ago

Import of Coin Branch-and-Cut (formerly known as Sbb)

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