source: trunk/Cbc/src/CbcTree.cpp

Last change on this file was 2547, checked in by forrest, 2 months ago

try and improve currentNode_ pointing correctly

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 44.9 KB
Line 
1/* $Id: CbcTree.cpp 2547 2019-04-09 13:45:02Z tkr $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include "CbcModel.hpp"
7#include "CbcNode.hpp"
8#include "CbcTree.hpp"
9#include "CbcThread.hpp"
10#include "CbcCountRowCut.hpp"
11#include "CbcCompareActual.hpp"
12#include "CbcBranchActual.hpp"
13
14#if CBC_DEBUG_HEAP > 0
15
16namespace {
17
18/*
19  The next few methods test that the heap property (parent equal or better
20  than either child) is maintained in the heap. Originally created to sort out
21  why `cbc -unitTest' triggered an `Invalid heap' error in a MSVS debug build.
22*/
23/*
24  Predicate test. The parent should be better or equal to the child. Since the
25  predicate comparison_(x,y) returns true if y (child) is strictly better,
26  we want failure on the initial test. Clearly, success for comparison(x,y)
27  and comparison(y,x) is also a failure.
28
29  Returns true if the predicate passes, false if it fails.
30*/
31bool check_pred(CbcCompareBase &pred, CbcNode *parent, CbcNode *child)
32{
33  if (parent == 0 || child == 0)
34    return (false);
35  if (!pred(parent, child))
36    return (true);
37  else if (pred(child, parent))
38    std::cout
39      << " Heap predicate failure! (x<y) && (y<x)!" << std::endl;
40  return (false);
41}
42
43} // end file-local namespace
44
45/*
46  Check for the heap property: the parent is better than or equal to
47  either child.
48
49  The heap is a binary tree, stored in the vector layer by layer. By advancing
50  parent at half the rate of child (aka curNode), we check both children
51  of a given parent.  (Draw yourself a picture; it'll help.) An empty heap
52  is trivially valid. A heap with no predicate is trivially invalid.
53
54  TODO: The heap -> vector mapping assumed here is valid for the MSVS heap
55        implementation.  No guarantee it's valid elsewhere.
56*/
57
58void CbcTree::validateHeap()
59{
60  if (comparison_.test_ == 0) {
61    std::cout
62      << " Invalid heap (no predicate)!" << std::endl;
63    return;
64  }
65  std::vector< CbcNode * >::const_iterator curNode, lastNode;
66  curNode = nodes_.begin();
67  lastNode = nodes_.end();
68  int curNdx = 0;
69  int parNdx = 0;
70  if (curNode == lastNode)
71    return;
72  if (*curNode == 0) {
73    std::cout
74      << " Invalid heap[" << curNdx << "] (null entry)!" << std::endl;
75  }
76  std::vector< CbcNode * >::const_iterator parent;
77  std::vector< CbcNode * >::const_iterator &child = curNode;
78  for (parent = curNode; ++curNode != lastNode; ++parent, ++parNdx) {
79    curNdx++;
80    if (*parent == 0) {
81      std::cout
82        << " Invalid heap[" << parNdx << "] (parent null entry)!" << std::endl;
83      curNode++;
84      curNdx++;
85      continue;
86    }
87    if (*curNode == 0) {
88      std::cout
89        << " Invalid heap[" << curNdx << "] (left child null entry)!"
90        << std::endl;
91    } else {
92      if (!check_pred(*comparison_.test_, *parent, *child)) {
93        std::cout
94          << " Invalid heap (left child better)!" << std::endl;
95        CbcNode *node = *parent;
96        std::cout
97          << "   Parent [" << parNdx << "] (" << std::hex << node << std::dec
98          << ") unsat " << node->numberUnsatisfied() << ", depth "
99          << node->depth() << ", obj " << node->objectiveValue() << "."
100          << std::endl;
101        node = *child;
102        std::cout
103          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
104          << ") unsat " << node->numberUnsatisfied() << ", depth "
105          << node->depth() << ", obj " << node->objectiveValue() << "."
106          << std::endl;
107      }
108    }
109    curNode++;
110    curNdx++;
111    if (curNode == lastNode)
112      break;
113    if (*curNode == 0) {
114      std::cout
115        << " Invalid heap[" << curNdx << "] (right child null entry)!"
116        << std::endl;
117    } else {
118      if (!check_pred(*comparison_.test_, *parent, *child)) {
119        std::cout
120          << " Invalid heap (right child better)!" << std::endl;
121        CbcNode *node = *parent;
122        std::cout
123          << "   Parent [" << parNdx << "] (" << std::hex << node << std::dec
124          << ") unsat " << node->numberUnsatisfied() << ", depth "
125          << node->depth() << ", obj " << node->objectiveValue() << "."
126          << std::endl;
127        node = *child;
128        std::cout
129          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
130          << ") unsat " << node->numberUnsatisfied() << ", depth "
131          << node->depth() << ", obj " << node->objectiveValue() << "."
132          << std::endl;
133      }
134    }
135  }
136  return;
137}
138
139#endif // CBC_DEBUG_HEAP
140
141CbcTree::CbcTree()
142{
143  maximumNodeNumber_ = 0;
144  numberBranching_ = 0;
145  maximumBranching_ = 0;
146  branched_ = NULL;
147  newBound_ = NULL;
148}
149CbcTree::~CbcTree()
150{
151  delete[] branched_;
152  delete[] newBound_;
153}
154// Copy constructor
155CbcTree::CbcTree(const CbcTree &rhs)
156{
157  nodes_ = rhs.nodes_;
158  maximumNodeNumber_ = rhs.maximumNodeNumber_;
159  numberBranching_ = rhs.numberBranching_;
160  maximumBranching_ = rhs.maximumBranching_;
161  if (maximumBranching_ > 0) {
162    branched_ = CoinCopyOfArray(rhs.branched_, maximumBranching_);
163    newBound_ = CoinCopyOfArray(rhs.newBound_, maximumBranching_);
164  } else {
165    branched_ = NULL;
166    newBound_ = NULL;
167  }
168}
169// Assignment operator
170CbcTree &
171CbcTree::operator=(const CbcTree &rhs)
172{
173  if (this != &rhs) {
174    nodes_ = rhs.nodes_;
175    maximumNodeNumber_ = rhs.maximumNodeNumber_;
176    delete[] branched_;
177    delete[] newBound_;
178    numberBranching_ = rhs.numberBranching_;
179    maximumBranching_ = rhs.maximumBranching_;
180    if (maximumBranching_ > 0) {
181      branched_ = CoinCopyOfArray(rhs.branched_, maximumBranching_);
182      newBound_ = CoinCopyOfArray(rhs.newBound_, maximumBranching_);
183    } else {
184      branched_ = NULL;
185      newBound_ = NULL;
186    }
187  }
188  return *this;
189}
190
191/*
192  Rebuild the heap.
193*/
194void CbcTree::rebuild()
195{
196  std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
197#if CBC_DEBUG_HEAP > 1
198  std::cout << "  HEAP: rebuild complete." << std::endl;
199#endif
200#if CBC_DEBUG_HEAP > 0
201  validateHeap();
202#endif
203}
204
205// Adds branching information to complete state
206void CbcTree::addBranchingInformation(const CbcModel *model, const CbcNodeInfo *nodeInfo,
207  const double *currentLower,
208  const double *currentUpper)
209{
210  const OsiBranchingObject *objA = nodeInfo->owner()->branchingObject();
211  const CbcIntegerBranchingObject *objBranch = dynamic_cast< const CbcIntegerBranchingObject * >(objA);
212  if (objBranch) {
213    const CbcObject *objB = objBranch->object();
214    const CbcSimpleInteger *obj = dynamic_cast< const CbcSimpleInteger * >(objB);
215    assert(obj);
216    int iColumn = obj->columnNumber();
217    const double *down = objBranch->downBounds();
218    const double *up = objBranch->upBounds();
219    assert(currentLower[iColumn] == down[0]);
220    assert(currentUpper[iColumn] == up[1]);
221    if (dynamic_cast< const CbcPartialNodeInfo * >(nodeInfo)) {
222      const CbcPartialNodeInfo *info = dynamic_cast< const CbcPartialNodeInfo * >(nodeInfo);
223      const double *newBounds = info->newBounds();
224      const int *variables = info->variables();
225      int numberChanged = info->numberChangedBounds();
226      for (int i = 0; i < numberChanged; i++) {
227        int jColumn = variables[i];
228        int kColumn = jColumn & (~0x80000000);
229        if (iColumn == kColumn) {
230          jColumn |= 0x40000000;
231#ifndef NDEBUG
232          double value = newBounds[i];
233          if ((jColumn & 0x80000000) == 0) {
234            assert(value == up[0]);
235          } else {
236            assert(value == down[1]);
237          }
238#endif
239        }
240        if (numberBranching_ == maximumBranching_)
241          increaseSpace();
242        newBound_[numberBranching_] = static_cast< int >(newBounds[i]);
243        branched_[numberBranching_++] = jColumn;
244      }
245    } else {
246      const CbcFullNodeInfo *info = dynamic_cast< const CbcFullNodeInfo * >(nodeInfo);
247      int numberIntegers = model->numberIntegers();
248      const int *which = model->integerVariable();
249      const double *newLower = info->lower();
250      const double *newUpper = info->upper();
251      if (numberBranching_ == maximumBranching_)
252        increaseSpace();
253      assert(newLower[iColumn] == up[0] || newUpper[iColumn] == down[1]);
254      int jColumn = iColumn | 0x40000000;
255      if (newLower[iColumn] == up[0]) {
256        newBound_[numberBranching_] = static_cast< int >(up[0]);
257      } else {
258        newBound_[numberBranching_] = static_cast< int >(down[1]);
259        jColumn |= 0x80000000;
260      }
261      branched_[numberBranching_++] = jColumn;
262      for (int i = 0; i < numberIntegers; i++) {
263        int jColumn = which[i];
264        assert(currentLower[jColumn] == newLower[jColumn] || currentUpper[jColumn] == newUpper[jColumn]);
265        if (jColumn != iColumn) {
266          bool changed = false;
267          double value;
268          if (newLower[jColumn] > currentLower[jColumn]) {
269            value = newLower[jColumn];
270            changed = true;
271          } else if (newUpper[jColumn] < currentUpper[jColumn]) {
272            value = newUpper[jColumn];
273            jColumn |= 0x80000000;
274            changed = true;
275          }
276          if (changed) {
277            if (numberBranching_ == maximumBranching_)
278              increaseSpace();
279            newBound_[numberBranching_] = static_cast< int >(value);
280            branched_[numberBranching_++] = jColumn;
281          }
282        }
283      }
284    }
285  } else {
286    // switch off
287    delete[] branched_;
288    delete[] newBound_;
289    maximumBranching_ = -1;
290    branched_ = NULL;
291    newBound_ = NULL;
292  }
293}
294// Increase space for data
295void CbcTree::increaseSpace()
296{
297  assert(numberBranching_ == maximumBranching_);
298  maximumBranching_ = (3 * maximumBranching_ + 10) >> 1;
299  unsigned int *temp1 = CoinCopyOfArrayPartial(branched_, maximumBranching_, numberBranching_);
300  delete[] branched_;
301  branched_ = temp1;
302  int *temp2 = CoinCopyOfArrayPartial(newBound_, maximumBranching_, numberBranching_);
303  delete[] newBound_;
304  newBound_ = temp2;
305}
306// Clone
307CbcTree *
308CbcTree::clone() const
309{
310  return new CbcTree(*this);
311}
312
313#ifndef CBC_DUBIOUS_HEAP
314/*
315  Set comparison predicate and re-sort the heap.
316
317  Note that common usage is to tweak the incumbent predicate and then
318  call this method to rebuild the heap. Hence we cannot check for heap
319  validity at entry. rebuild() will check on the way out, if
320  CBC_DEBUG_HEAP is set.
321
322  TODO: remove the call to cleanDive and put it somewhere appropriate.
323*/
324void CbcTree::setComparison(CbcCompareBase &compare)
325{
326#if CBC_DEBUG_HEAP > 1
327  std::cout << "  HEAP: resetting comparison predicate." << std::endl;
328#endif
329  comparison_.test_ = &compare;
330
331  /*
332  From a software engineering point of view, setComparison has no business
333  knowing anything about the comparison function. Need to look for a better
334  solution. Perhaps a callback comparable to newSolution, executing when
335  the comparison method is set (i.e., in setComparison).
336  -- lh, 100921 --
337*/
338  CbcCompareDefault *compareD = dynamic_cast< CbcCompareDefault * >(&compare);
339  if (compareD) {
340    // clean up diving
341    compareD->cleanDive();
342  }
343  rebuild();
344}
345
346// Return the top node of the heap
347CbcNode *
348CbcTree::top() const
349{
350  return nodes_.front();
351}
352
353// Add a node to the heap
354void CbcTree::push(CbcNode *x)
355{
356  x->setNodeNumber(maximumNodeNumber_);
357  lastObjective_ = x->objectiveValue();
358  lastDepth_ = x->depth();
359  lastUnsatisfied_ = x->numberUnsatisfied();
360  maximumNodeNumber_++;
361#if CBC_DEBUG_HEAP > 2
362  CbcNodeInfo *info = x->nodeInfo();
363  assert(info);
364  std::cout
365    << "  HEAP: Pushing node " << x->nodeNumber()
366    << "(" << std::hex << x << std::dec << ") obj " << x->objectiveValue()
367    << ", ref " << info->decrement(0)
368    << ", todo " << info->numberBranchesLeft()
369    << ", refd by " << info->numberPointingToThis() << "." << std::endl;
370  assert(x->objectiveValue() != COIN_DBL_MAX);
371#endif
372#if CBC_DEBUG_HEAP > 0
373  validateHeap();
374#endif
375  x->setOnTree(true);
376  nodes_.push_back(x);
377  std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
378#if CBC_DEBUG_HEAP > 0
379  validateHeap();
380#endif
381}
382
383// Remove the top node from the heap
384void CbcTree::pop()
385{
386
387#if CBC_DEBUG_HEAP > 2
388  CbcNode *node = nodes_.front();
389  CbcNodeInfo *info = node->nodeInfo();
390  assert(info);
391  std::cout
392    << "  HEAP: Popping node " << node->nodeNumber()
393    << "(" << std::hex << node << std::dec
394    << ") obj " << node->objectiveValue()
395    << ", ref " << info->decrement(0)
396    << ", todo " << info->numberBranchesLeft()
397    << ", refd by " << info->numberPointingToThis() << "." << std::endl;
398#endif
399#if CBC_DEBUG_HEAP > 0
400  validateHeap();
401#endif
402  nodes_.front()->setOnTree(false);
403  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
404  nodes_.pop_back();
405
406#if CBC_DEBUG_HEAP > 0
407  validateHeap();
408#endif
409}
410
411// Test if empty *** note may be overridden
412bool CbcTree::empty()
413{
414  return nodes_.empty();
415}
416/*
417  Return the best node from the heap.
418
419  Note that best is offered a chance (checkIsCutoff) to reevaluate
420  itself and make arbitrary changes. A caller should be prepared
421  to check that the returned node is acceptable.
422
423  There's quite a bit of suspect code here, much of it disabled in
424  some way. The net effect at present is to return the top node on
425  the heap after offering the node an opportunity to reevaluate itself.
426  Documentation for checkIsCutoff() puts no restrictions on allowable
427  changes. -- lh, 100921 --
428*/
429CbcNode *
430CbcTree::bestNode(double cutoff)
431{
432#if CBC_DEBUG_HEAP > 0
433  validateHeap();
434#endif
435  /*
436  This code is problematic. As of 100921, there's really no loop.
437  If front() == null, an assert will trigger. checkIsCutoff seems to be
438  work in progress; comments assert that it can make pretty much arbitrary
439  changes to best. If best can change its objective, there's a good
440  possibility the heap is invalid.
441*/
442  CbcNode *best = NULL;
443  while (!best && nodes_.size()) {
444    best = nodes_.front();
445    if (best)
446      assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
447    if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
448      assert(best->nodeInfo()->numberBranchesLeft());
449    if (best && best->objectiveValue() >= cutoff) {
450      // double check in case node can change its mind!
451      best->checkIsCutoff(cutoff);
452    }
453    if (!best || best->objectiveValue() >= cutoff) {
454#ifdef JJF_ZERO
455      // take off
456      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
457      nodes_.pop_back();
458      delete best;
459      best = NULL;
460#else
461      // let code get rid of it
462      assert(best);
463#endif
464    }
465  }
466  /*
467  See if the comparison object wants us to do a full scan with the
468  alternative criteria. The net effect is to confirm best by the
469  alternative criteria, or identify a competitor and erase it.
470
471  This code is problematic. Nulling an arbitrary node will in general
472  break the heap property. Disabled some time ago, as noted in several
473  places.
474*/
475  if (false && best && comparison_.test_->fullScan()) {
476    CbcNode *saveBest = best;
477    size_t n = nodes_.size();
478    size_t iBest = -1;
479    for (size_t i = 0; i < n; i++) {
480      // temp
481      assert(nodes_[i]);
482      assert(nodes_[i]->nodeInfo());
483      if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
484        assert(nodes_[i]->nodeInfo()->numberBranchesLeft());
485      if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
486        && comparison_.alternateTest(best, nodes_[i])) {
487        best = nodes_[i];
488        iBest = i;
489      }
490    }
491    if (best == saveBest) {
492      // can pop
493      // take off
494      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
495      nodes_.pop_back();
496    } else {
497      // make impossible
498      nodes_[iBest] = NULL;
499    }
500  } else if (best) {
501#if CBC_DEBUG_HEAP > 2
502    CbcNode *node = nodes_.front();
503    CbcNodeInfo *info = node->nodeInfo();
504    assert(info);
505    std::cout
506      << "  bestNode: Popping node " << node->nodeNumber()
507      << "(" << std::hex << node << std::dec
508      << ") obj " << node->objectiveValue()
509      << ", ref " << info->decrement(0)
510      << ", todo " << info->numberBranchesLeft()
511      << ", refd by " << info->numberPointingToThis() << "." << std::endl;
512#endif
513    // take off
514    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
515    nodes_.pop_back();
516  }
517#if CBC_DEBUG_HEAP > 0
518  validateHeap();
519#endif
520  if (best)
521    best->setOnTree(false);
522  return best;
523}
524/*! \brief Prune the tree using an objective function cutoff
525
526  This routine removes all nodes with objective worse than the
527  specified cutoff value.
528*/
529
530void CbcTree::cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
531{
532#if CBC_DEBUG_HEAP > 1
533  std::cout << " cleanTree: beginning clean." << std::endl;
534#endif
535#if CBC_DEBUG_HEAP > 0
536  validateHeap();
537#endif
538  int j;
539  int nNodes = size();
540  CbcNode **nodeArray = new CbcNode *[nNodes];
541  int *depth = new int[nNodes];
542  int k = 0;
543  int kDelete = nNodes;
544  bestPossibleObjective = 1.0e100;
545  /*
546        Destructively scan the heap. Nodes to be retained go into the front of
547        nodeArray, nodes to be deleted into the back. Store the depth in a
548        correlated array for nodes to be deleted.
549    */
550  for (j = 0; j < nNodes; j++) {
551    CbcNode *node = top();
552    pop();
553    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
554    if (node && value >= cutoff) {
555      // double check in case node can change its mind!
556      value = node->checkIsCutoff(cutoff);
557    }
558    if (value >= cutoff || !node->active()) {
559      if (node) {
560        if (cutoff < -1.0e30)
561          node->nodeInfo()->deactivate(7);
562        nodeArray[--kDelete] = node;
563        depth[kDelete] = node->depth();
564      }
565    } else {
566      bestPossibleObjective = CoinMin(bestPossibleObjective, value);
567      nodeArray[k++] = node;
568    }
569  }
570  /*
571      Rebuild the heap using the retained nodes.
572    */
573  for (j = 0; j < k; j++) {
574    push(nodeArray[j]);
575  }
576#if CBC_DEBUG_HEAP > 1
577  std::cout << " cleanTree: finished rebuild." << std::endl;
578#endif
579#if CBC_DEBUG_HEAP > 0
580  validateHeap();
581#endif
582  /*
583      Sort the list of nodes to be deleted, nondecreasing.
584    */
585  CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
586  /*
587      Work back from deepest to shallowest. In spite of the name, addCuts1 is
588      just a preparatory step. When it returns, the following will be true:
589        * all cuts are removed from the solver's copy of the constraint system;
590        * lastws will be a basis appropriate for the specified node;
591        * variable bounds will be adjusted to be appropriate for the specified
592          node;
593        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
594          should be added to the constraint system at this node (but they have
595          not actually been added).
596      Then we scan the cut list for the node. Decrement the reference count
597      for the cut, and if it's gone to 0, really delete it.
598
599      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
600      are necessary. When reconstructing a node, these checks are used to skip
601      over loose cuts, excluding them from the reconstituted basis. But here
602      we're just interested in correcting the reference count. Tight/loose
603      should make no difference.
604
605      Arguably a separate routine should be used in place of addCuts1. It's
606      doing more work than needed, modifying the model to match a subproblem
607      at a node that will be discarded.  Then again, we seem to need the basis.
608    */
609  for (j = nNodes - 1; j >= kDelete; j--) {
610    CbcNode *node = nodeArray[j];
611    CoinWarmStartBasis *lastws = (cutoff != -COIN_DBL_MAX) ? model->getEmptyBasis() : NULL;
612
613    model->addCuts1(node, lastws);
614    // Decrement cut counts
615    assert(node);
616    //assert (node->nodeInfo());
617    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
618    if (cutoff != -COIN_DBL_MAX) {
619      // normal
620      for (int i = 0; i < model->currentNumberCuts(); i++) {
621        // take off node
622        CoinWarmStartBasis::Status status = lastws->getArtifStatus(i + model->numberRowsAtContinuous());
623        if (status != CoinWarmStartBasis::basic && model->addedCuts()[i]) {
624          if (!model->addedCuts()[i]->decrement(numberLeft))
625            delete model->addedCuts()[i];
626        }
627      }
628    } else {
629      // quick
630      for (int i = 0; i < model->currentNumberCuts(); i++) {
631        // take off node
632        if (model->addedCuts()[i]) {
633          if (model->parallelMode() != 1 || true) {
634            if (!model->addedCuts()[i]->decrement(numberLeft))
635              delete model->addedCuts()[i];
636          }
637        }
638      }
639    }
640#ifdef CBC_THREAD
641    if (model->parallelMode() > 0 && model->master()) {
642      // delete reference to node
643      int numberThreads = model->master()->numberThreads();
644      for (int i = 0; i < numberThreads; i++) {
645        CbcThread *child = model->master()->child(i);
646        if (child->createdNode() == node)
647          child->setCreatedNode(NULL);
648      }
649    }
650#endif
651    // node should not have anything pointing to it
652    if (node->nodeInfo())
653      node->nodeInfo()->throwAway();
654    model->deleteNode(node);
655    delete lastws;
656  }
657  delete[] nodeArray;
658  delete[] depth;
659#ifdef CBC_THREAD
660  if (model->parallelMode() > 0 && model->master()) {
661    // need to adjust for ones not on tree
662    CbcBaseModel *master = model->master();
663    int numberThreads = master->numberThreads();
664    for (int i = 0; i < numberThreads; i++) {
665      CbcThread *child = master->child(i);
666      if (child->node()) {
667        double value = child->node()->objectiveValue();
668        // adjust
669        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
670      }
671    }
672  }
673#endif
674}
675
676// Return the best node of the heap using alternate criterion
677CbcNode *
678CbcTree::bestAlternate()
679{
680  size_t n = nodes_.size();
681  CbcNode *best = NULL;
682  if (n) {
683    best = nodes_[0];
684    for (size_t i = 1; i < n; i++) {
685      if (comparison_.alternateTest(best, nodes_[i])) {
686        best = nodes_[i];
687      }
688    }
689  }
690  return best;
691}
692
693#ifdef JJF_ZERO // not used, reference removed in CbcModel.cpp
694CbcTreeArray::CbcTreeArray()
695  : CbcTree()
696  , lastNode_(NULL)
697  , lastNodePopped_(NULL)
698  , switches_(0)
699{
700}
701CbcTreeArray::~CbcTreeArray()
702{
703}
704// Copy constructor
705CbcTreeArray::CbcTreeArray(const CbcTreeArray &rhs)
706  : CbcTree(rhs)
707  , lastNode_(rhs.lastNode_)
708  , lastNodePopped_(rhs.lastNodePopped_)
709  , switches_(rhs.switches_)
710{
711}
712// Assignment operator
713CbcTreeArray &
714CbcTreeArray::operator=(const CbcTreeArray &rhs)
715{
716  if (this != &rhs) {
717    CbcTree::operator=(rhs);
718    lastNode_ = rhs.lastNode_;
719    lastNodePopped_ = rhs.lastNodePopped_;
720    switches_ = rhs.switches_;
721  }
722  return *this;
723}
724// Clone
725CbcTree *
726CbcTreeArray::clone() const
727{
728  return new CbcTreeArray(*this);
729}
730// Set comparison function and resort heap
731void CbcTreeArray::setComparison(CbcCompareBase &compare)
732{
733  comparison_.test_ = &compare;
734  rebuild();
735}
736
737// Add a node to the heap
738void CbcTreeArray::push(CbcNode *x)
739{
740  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
741       x->objectiveValue(),x->nodeInfo()->decrement(0),
742       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
743  assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
744  x->setOnTree(true);
745  if (lastNode_) {
746    if (lastNode_->nodeInfo()->parent() == x->nodeInfo()) {
747      // x is parent of lastNode_ so put x on heap
748      //#define CBCTREE_PRINT
749#ifdef CBCTREE_PRINT
750      printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
751        x, x->nodeInfo(), x->depth(), x->nodeNumber(),
752        lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
753#endif
754      nodes_.push_back(x);
755    } else {
756      x->setNodeNumber(maximumNodeNumber_);
757      maximumNodeNumber_++;
758#ifdef CBCTREE_PRINT
759      printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
760        x, x->nodeInfo(), x->depth(), x->nodeNumber(),
761        lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
762#endif
763      nodes_.push_back(lastNode_);
764      lastNode_ = x;
765    }
766    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
767  } else {
768    x->setNodeNumber(maximumNodeNumber_);
769    maximumNodeNumber_++;
770    if (x != lastNodePopped_) {
771      lastNode_ = x;
772#ifdef CBCTREE_PRINT
773      printf("pushNULL x %x (%x at depth %d n %d)\n",
774        x, x->nodeInfo(), x->depth(), x->nodeNumber());
775#endif
776    } else {
777      // means other way was infeasible
778#ifdef CBCTREE_PRINT
779      printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
780        x, x->nodeInfo(), x->depth(), x->nodeNumber());
781#endif
782      nodes_.push_back(x);
783      std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
784    }
785  }
786}
787
788// Test if empty *** note may be overridden
789bool CbcTreeArray::empty()
790{
791  return nodes_.empty() && (lastNode_ == NULL);
792}
793// Gets best node and takes off heap
794CbcNode *
795CbcTreeArray::bestNode(double cutoff)
796{
797  CbcNode *best = NULL;
798  // See if we want last node or best on heap
799  if (lastNode_) {
800#ifdef CBCTREE_PRINT
801    printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
802      lastNode_, lastNode_->nodeInfo(), lastNode_->depth(),
803      lastNode_->nodeNumber(), lastNode_->objectiveValue());
804#endif
805    assert(lastNode_->onTree());
806    int nodeNumber = lastNode_->nodeNumber();
807    bool useLastNode = false;
808    if (nodeNumber + 1 == maximumNodeNumber_) {
809      // diving - look further
810      CbcCompareDefault *compareDefault
811        = dynamic_cast< CbcCompareDefault * >(comparison_.test_);
812      assert(compareDefault);
813      double bestPossible = compareDefault->getBestPossible();
814      double cutoff = compareDefault->getCutoff();
815      double objValue = lastNode_->objectiveValue();
816      if (cutoff < 1.0e20) {
817        if (objValue - bestPossible < 0.999 * (cutoff - bestPossible))
818          useLastNode = true;
819      } else {
820        useLastNode = true;
821      }
822    }
823    if (useLastNode) {
824      lastNode_->setOnTree(false);
825      best = lastNode_;
826      lastNode_ = NULL;
827      assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
828      if (best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
829        assert(best->nodeInfo()->numberBranchesLeft());
830      if (best->objectiveValue() >= cutoff) {
831        // double check in case node can change its mind!
832        best->checkIsCutoff(cutoff);
833      }
834      lastNodePopped_ = best;
835      return best;
836    } else {
837      // put on tree
838      nodes_.push_back(lastNode_);
839      lastNode_->setNodeNumber(maximumNodeNumber_);
840      maximumNodeNumber_++;
841      lastNode_ = NULL;
842      std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
843    }
844  }
845  while (!best && nodes_.size()) {
846    best = nodes_.front();
847    if (best)
848      assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
849    if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
850      assert(best->nodeInfo()->numberBranchesLeft());
851    if (best && best->objectiveValue() >= cutoff) {
852      // double check in case node can change its mind!
853      best->checkIsCutoff(cutoff);
854    }
855    if (!best || best->objectiveValue() >= cutoff) {
856      // let code get rid of it
857      assert(best);
858    }
859  }
860  lastNodePopped_ = best;
861#ifdef CBCTREE_PRINT
862  if (best)
863    printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
864      best, best->nodeInfo(), best->depth(),
865      best->nodeNumber(), best->objectiveValue());
866  else
867    printf("Heap returning Null\n");
868#endif
869  if (best) {
870    // take off
871    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
872    nodes_.pop_back();
873  }
874#ifdef DEBUG_CBC_HEAP
875  if (best) {
876    int n = nodes_.size();
877    bool good = true;
878    for (int i = 0; i < n; i++) {
879      // temp
880      assert(nodes_[i]);
881      if (!comparison_.compareNodes(nodes_[i], best)) {
882        good = false;
883        CbcNode *x = nodes_[i];
884        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
885          x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
886          best->numberUnsatisfied(), best->depth(), best->objectiveValue());
887      }
888    }
889    if (!good) {
890      // compare best to all
891      int i;
892      for (i = 0; i < n; i++) {
893        CbcNode *x = nodes_[i];
894        printf("i=%d x is nun %d depth %d obj %g", i,
895          x->numberUnsatisfied(), x->depth(), x->objectiveValue());
896        if (!comparison_.compareNodes(x, best)) {
897          printf(" - best is worse!\n");
898        } else {
899          printf("\n");
900        }
901      }
902      // Now compare amongst rest
903      for (i = 0; i < n; i++) {
904        CbcNode *x = nodes_[i];
905        printf("For i=%d ", i);
906        for (int j = i + 1; j < n; j++) {
907          CbcNode *y = nodes_[j];
908          if (!comparison_.compareNodes(x, y)) {
909            printf(" b %d", j);
910          } else {
911            printf(" w %d", j);
912          }
913        }
914        printf("\n");
915      }
916      assert(good);
917    }
918  }
919#endif
920  if (best)
921    best->setOnTree(false);
922  return best;
923}
924
925double
926CbcTreeArray::getBestPossibleObjective()
927{
928  double bestPossibleObjective = 1e100;
929  for (int i = 0; i < static_cast< int >(nodes_.size()); i++) {
930    if (nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective) {
931      bestPossibleObjective = nodes_[i]->objectiveValue();
932    }
933  }
934  if (lastNode_) {
935    bestPossibleObjective = CoinMin(bestPossibleObjective, lastNode_->objectiveValue());
936  }
937#ifdef CBC_THREAD
938  if (model->parallelMode() > 0 && model->master()) {
939    // need to adjust for ones not on tree
940    CbcBaseModel *master = model->master();
941    int numberThreads = master->numberThreads();
942    for (int i = 0; i < numberThreads; i++) {
943      CbcThread *child = master->child(i);
944      if (child->node()) {
945        double value = child->node()->objectiveValue();
946        // adjust
947        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
948      }
949    }
950  }
951#endif
952  CbcCompareDefault *compareDefault
953    = dynamic_cast< CbcCompareDefault * >(comparison_.test_);
954  assert(compareDefault);
955  compareDefault->setBestPossible(bestPossibleObjective);
956  return bestPossibleObjective;
957}
958/*! \brief Prune the tree using an objective function cutoff
959
960  This routine removes all nodes with objective worst than the
961  specified cutoff value.
962*/
963
964void CbcTreeArray::cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
965{
966  int j;
967  int nNodes = size();
968  int lastNode = nNodes + 1;
969  CbcNode **nodeArray = new CbcNode *[lastNode];
970  int *depth = new int[lastNode];
971  int k = 0;
972  int kDelete = lastNode;
973  bestPossibleObjective = 1.0e100;
974  /*
975        Destructively scan the heap. Nodes to be retained go into the front of
976        nodeArray, nodes to be deleted into the back. Store the depth in a
977        correlated array for nodes to be deleted.
978    */
979  for (j = 0; j < nNodes; j++) {
980    CbcNode *node = nodes_.front();
981    nodes_.front()->setOnTree(false);
982    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
983    nodes_.pop_back();
984    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
985    if (node && value >= cutoff) {
986      // double check in case node can change its mind!
987      value = node->checkIsCutoff(cutoff);
988    }
989    if (value >= cutoff || !node->active()) {
990      if (node) {
991        nodeArray[--kDelete] = node;
992        depth[kDelete] = node->depth();
993      }
994    } else {
995      bestPossibleObjective = CoinMin(bestPossibleObjective, value);
996      nodeArray[k++] = node;
997    }
998  }
999#ifdef CBC_THREAD
1000  if (model->parallelMode() > 0 && model->master()) {
1001    // need to adjust for ones not on tree
1002    CbcBaseModel *master = model->master();
1003    int numberThreads = master->numberThreads();
1004    for (int i = 0; i < numberThreads; i++) {
1005      CbcThread *child = master->child(i);
1006      if (child->node()) {
1007        double value = child->node()->objectiveValue();
1008        // adjust
1009        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1010      }
1011    }
1012  }
1013#endif
1014  if (lastNode_) {
1015    double value = lastNode_->objectiveValue();
1016    bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1017    if (value >= cutoff || !lastNode_->active()) {
1018      nodeArray[--kDelete] = lastNode_;
1019      depth[kDelete] = lastNode_->depth();
1020      lastNode_ = NULL;
1021    }
1022  }
1023  CbcCompareDefault *compareDefault
1024    = dynamic_cast< CbcCompareDefault * >(comparison_.test_);
1025  assert(compareDefault);
1026  compareDefault->setBestPossible(bestPossibleObjective);
1027  compareDefault->setCutoff(cutoff);
1028  /*
1029      Rebuild the heap using the retained nodes.
1030    */
1031  for (j = 0; j < k; j++) {
1032    CbcNode *node = nodeArray[j];
1033    node->setOnTree(true);
1034    nodes_.push_back(node);
1035    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
1036  }
1037  /*
1038      Sort the list of nodes to be deleted, nondecreasing.
1039    */
1040  CoinSort_2(depth + kDelete, depth + lastNode, nodeArray + kDelete);
1041  /*
1042      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1043      just a preparatory step. When it returns, the following will be true:
1044        * all cuts are removed from the solver's copy of the constraint system;
1045        * lastws will be a basis appropriate for the specified node;
1046        * variable bounds will be adjusted to be appropriate for the specified
1047          node;
1048        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1049          should be added to the constraint system at this node (but they have
1050          not actually been added).
1051      Then we scan the cut list for the node. Decrement the reference count
1052      for the cut, and if it's gone to 0, really delete it.
1053
1054      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1055      are necessary. When reconstructing a node, these checks are used to skip
1056      over loose cuts, excluding them from the reconstituted basis. But here
1057      we're just interested in correcting the reference count. Tight/loose
1058      should make no difference.
1059
1060      Arguably a separate routine should be used in place of addCuts1. It's
1061      doing more work than needed, modifying the model to match a subproblem
1062      at a node that will be discarded.  Then again, we seem to need the basis.
1063    */
1064  for (j = lastNode - 1; j >= kDelete; j--) {
1065    CbcNode *node = nodeArray[j];
1066    CoinWarmStartBasis *lastws = model->getEmptyBasis();
1067
1068    model->addCuts1(node, lastws);
1069    // Decrement cut counts
1070    assert(node);
1071    //assert (node->nodeInfo());
1072    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1073    int i;
1074    for (i = 0; i < model->currentNumberCuts(); i++) {
1075      // take off node
1076      CoinWarmStartBasis::Status status = lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1077      if (status != CoinWarmStartBasis::basic && model->addedCuts()[i]) {
1078        if (!model->addedCuts()[i]->decrement(numberLeft))
1079          delete model->addedCuts()[i];
1080      }
1081    }
1082    // node should not have anything pointing to it
1083    if (node->nodeInfo())
1084      node->nodeInfo()->throwAway();
1085    delete node;
1086    delete lastws;
1087  }
1088  delete[] nodeArray;
1089  delete[] depth;
1090}
1091#endif
1092
1093#else // defined(CBC_DUBIOUS_HEAP)
1094
1095/*
1096  Unclear whether this code is useful any longer. Likely stale. See
1097  note in CbcCompareDefault.hpp re. CBC_DUBIOUS_HEAP.
1098  -- lh, 100921 --
1099*/
1100
1101// Set comparison function and resort heap
1102void CbcTree::setComparison(CbcCompareBase &compare)
1103{
1104  comparison_.test_ = &compare;
1105  std::vector< CbcNode * > newNodes = nodes_;
1106  nodes_.resize(0);
1107  while (newNodes.size() > 0) {
1108    push(newNodes.back());
1109    newNodes.pop_back();
1110  }
1111}
1112
1113// Return the top node of the heap
1114CbcNode *
1115CbcTree::top() const
1116{
1117  return nodes_.front();
1118}
1119
1120// Add a node to the heap
1121void CbcTree::push(CbcNode *x)
1122{
1123  x->setNodeNumber(maximumNodeNumber_);
1124  maximumNodeNumber_++;
1125  /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
1126       x->objectiveValue(),x->nodeInfo()->decrement(0),
1127       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
1128  assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
1129#ifdef JJF_ZERO
1130  nodes_.push_back(x);
1131  push_heap(nodes_.begin(), nodes_.end(), comparison_);
1132#else
1133  realpush(x);
1134#endif
1135}
1136
1137// Remove the top node from the heap
1138void CbcTree::pop()
1139{
1140#ifdef JJF_ZERO
1141  std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1142  nodes_.pop_back();
1143#else
1144  if (nodes_.size()) {
1145    //CbcNode* s = nodes_.front();
1146    realpop();
1147    //delete s;
1148  }
1149  assert(nodes_.size() >= 0);
1150#endif
1151}
1152
1153// Test if empty *** note may be overridden
1154bool CbcTree::empty()
1155{
1156  return nodes_.empty();
1157}
1158// Gets best node and takes off heap
1159CbcNode *
1160CbcTree::bestNode(double cutoff)
1161{
1162  CbcNode *best = NULL;
1163  while (!best && nodes_.size()) {
1164    best = nodes_.front();
1165    if (best)
1166      assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
1167    if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
1168      assert(best->nodeInfo()->numberBranchesLeft());
1169    if (best && best->objectiveValue() >= cutoff) {
1170      // double check in case node can change its mind!
1171      best->checkIsCutoff(cutoff);
1172    }
1173    if (!best || best->objectiveValue() >= cutoff) {
1174#ifdef JJF_ZERO
1175      // take off
1176      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1177      nodes_.pop_back();
1178      delete best;
1179      best = NULL;
1180#else
1181      // let code get rid of it
1182      assert(best);
1183#endif
1184    }
1185  }
1186  // switched off for now
1187  if (best && comparison_.test_->fullScan() && false) {
1188    CbcNode *saveBest = best;
1189    int n = nodes_.size();
1190    int iBest = -1;
1191    for (int i = 0; i < n; i++) {
1192      // temp
1193      assert(nodes_[i]);
1194      assert(nodes_[i]->nodeInfo());
1195      if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
1196        assert(nodes_[i]->nodeInfo()->numberBranchesLeft());
1197      if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
1198        && comparison_.alternateTest(best, nodes_[i])) {
1199        best = nodes_[i];
1200        iBest = i;
1201      }
1202    }
1203    if (best == saveBest) {
1204      // can pop
1205      // take off
1206      std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1207      nodes_.pop_back();
1208    } else {
1209      // make impossible
1210      nodes_[iBest] = NULL;
1211    }
1212  } else if (best) {
1213    // take off
1214#ifdef JJF_ZERO
1215    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1216    nodes_.pop_back();
1217#else
1218    realpop();
1219#endif
1220  }
1221#ifdef DEBUG_CBC_HEAP
1222  if (best) {
1223    int n = nodes_.size();
1224    bool good = true;
1225    for (int i = 0; i < n; i++) {
1226      // temp
1227      assert(nodes_[i]);
1228      if (!comparison_.compareNodes(nodes_[i], best)) {
1229        good = false;
1230        CbcNode *x = nodes_[i];
1231        printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
1232          x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
1233          best->numberUnsatisfied(), best->depth(), best->objectiveValue());
1234      }
1235    }
1236    if (!good) {
1237      // compare best to all
1238      int i;
1239      for (i = 0; i < n; i++) {
1240        CbcNode *x = nodes_[i];
1241        printf("i=%d x is nun %d depth %d obj %g", i,
1242          x->numberUnsatisfied(), x->depth(), x->objectiveValue());
1243        if (!comparison_.compareNodes(x, best)) {
1244          printf(" - best is worse!\n");
1245        } else {
1246          printf("\n");
1247        }
1248      }
1249      // Now compare amongst rest
1250      for (i = 0; i < n; i++) {
1251        CbcNode *x = nodes_[i];
1252        printf("For i=%d ", i);
1253        for (int j = i + 1; j < n; j++) {
1254          CbcNode *y = nodes_[j];
1255          if (!comparison_.compareNodes(x, y)) {
1256            printf(" b %d", j);
1257          } else {
1258            printf(" w %d", j);
1259          }
1260        }
1261        printf("\n");
1262      }
1263      assert(good);
1264    }
1265  }
1266#endif
1267  if (best)
1268    best->setOnTree(false);
1269  return best;
1270}
1271
1272/*! \brief Prune the tree using an objective function cutoff
1273
1274  This routine removes all nodes with objective worst than the
1275  specified cutoff value.
1276*/
1277
1278void CbcTree::cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective)
1279{
1280  int j;
1281  int nNodes = nodes_.size();
1282  CbcNode **nodeArray = new CbcNode *[nNodes];
1283  int *depth = new int[nNodes];
1284  int k = 0;
1285  int kDelete = nNodes;
1286  bestPossibleObjective = 1.0e100;
1287  /*
1288        Destructively scan the heap. Nodes to be retained go into the front of
1289        nodeArray, nodes to be deleted into the back. Store the depth in a
1290        correlated array for nodes to be deleted.
1291    */
1292  for (j = 0; j < nNodes; j++) {
1293    CbcNode *node = top();
1294    pop();
1295    double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1296    if (node && value >= cutoff) {
1297      // double check in case node can change its mind!
1298      value = node->checkIsCutoff(cutoff);
1299    }
1300    bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1301    if (value >= cutoff) {
1302      if (node) {
1303        nodeArray[--kDelete] = node;
1304        depth[kDelete] = node->depth();
1305      }
1306    } else {
1307      nodeArray[k++] = node;
1308    }
1309  }
1310#ifdef CBC_THREAD
1311  if (model->parallelMode() > 0 && model->master()) {
1312    // need to adjust for ones not on tree
1313    CbcBaseModel *master = model->master();
1314    int numberThreads = master->numberThreads();
1315    for (int i = 0; i < numberThreads; i++) {
1316      CbcThread *child = master->child(i);
1317      if (child->node()) {
1318        double value = child->node()->objectiveValue();
1319        // adjust
1320        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1321      }
1322    }
1323  }
1324#endif
1325  /*
1326      Rebuild the heap using the retained nodes.
1327    */
1328  for (j = 0; j < k; j++) {
1329    push(nodeArray[j]);
1330  }
1331  /*
1332      Sort the list of nodes to be deleted, nondecreasing.
1333    */
1334  CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
1335  /*
1336      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1337      just a preparatory step. When it returns, the following will be true:
1338        * all cuts are removed from the solver's copy of the constraint system;
1339        * lastws will be a basis appropriate for the specified node;
1340        * variable bounds will be adjusted to be appropriate for the specified
1341          node;
1342        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1343          should be added to the constraint system at this node (but they have
1344          not actually been added).
1345      Then we scan the cut list for the node. Decrement the reference count
1346      for the cut, and if it's gone to 0, really delete it.
1347
1348      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1349      are necessary. When reconstructing a node, these checks are used to skip
1350      over loose cuts, excluding them from the reconstituted basis. But here
1351      we're just interested in correcting the reference count. Tight/loose
1352      should make no difference.
1353
1354      Arguably a separate routine should be used in place of addCuts1. It's
1355      doing more work than needed, modifying the model to match a subproblem
1356      at a node that will be discarded.  Then again, we seem to need the basis.
1357    */
1358  for (j = nNodes - 1; j >= kDelete; j--) {
1359    CbcNode *node = nodeArray[j];
1360    CoinWarmStartBasis *lastws = model->getEmptyBasis();
1361
1362    model->addCuts1(node, lastws);
1363    // Decrement cut counts
1364    assert(node);
1365    //assert (node->nodeInfo());
1366    int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1367    int i;
1368    for (i = 0; i < model->currentNumberCuts(); i++) {
1369      // take off node
1370      CoinWarmStartBasis::Status status = lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1371      if (status != CoinWarmStartBasis::basic && model->addedCuts()[i]) {
1372        if (!model->addedCuts()[i]->decrement(numberLeft))
1373          delete model->addedCuts()[i];
1374      }
1375    }
1376    // node should not have anything pointing to it
1377    if (node->nodeInfo())
1378      node->nodeInfo()->throwAway();
1379    delete node;
1380    delete lastws;
1381  }
1382  delete[] nodeArray;
1383  delete[] depth;
1384}
1385
1386// Return the best node of the heap using alternate criterion
1387CbcNode *
1388CbcTree::bestAlternate()
1389{
1390  int n = nodes_.size();
1391  CbcNode *best = NULL;
1392  if (n) {
1393    best = nodes_[0];
1394    for (int i = 1; i < n; i++) {
1395      if (comparison_.alternateTest(best, nodes_[i])) {
1396        best = nodes_[i];
1397      }
1398    }
1399  }
1400  return best;
1401}
1402void CbcTree::realpop()
1403{
1404  if (nodes_.size() > 0) {
1405    nodes_[0] = nodes_.back();
1406    nodes_.pop_back();
1407    fixTop();
1408  }
1409  assert(nodes_.size() >= 0);
1410}
1411/* After changing data in the top node, fix the heap */
1412void CbcTree::fixTop()
1413{
1414  const int size = nodes_.size();
1415  if (size > 1) {
1416    CbcNode **candidates = &nodes_[0];
1417    CbcNode *s = candidates[0];
1418    --candidates;
1419    int pos = 1;
1420    int ch;
1421    for (ch = 2; ch < size; pos = ch, ch *= 2) {
1422      if (!comparison_.compareNodes(candidates[ch + 1], candidates[ch]))
1423        ++ch;
1424      if (!comparison_.compareNodes(s, candidates[ch]))
1425        break;
1426      candidates[pos] = candidates[ch];
1427    }
1428    if (ch == size) {
1429      if (!comparison_.compareNodes(candidates[ch], s)) {
1430        candidates[pos] = candidates[ch];
1431        pos = ch;
1432      }
1433    }
1434    candidates[pos] = s;
1435  }
1436}
1437void CbcTree::realpush(CbcNode *node)
1438{
1439  node->setOnTree(true);
1440  nodes_.push_back(node);
1441  CbcNode **candidates = &nodes_[0];
1442  --candidates;
1443  int pos = nodes_.size();
1444  int ch;
1445  for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
1446    if (!comparison_.compareNodes(candidates[ch], node))
1447      break;
1448    candidates[pos] = candidates[ch];
1449  }
1450  candidates[pos] = node;
1451}
1452#endif
1453
1454double
1455CbcTree::getBestPossibleObjective()
1456{
1457  double r_val = 1e100;
1458  for (int i = 0; i < static_cast< int >(nodes_.size()); i++) {
1459    if (nodes_[i] && nodes_[i]->objectiveValue() < r_val) {
1460      r_val = nodes_[i]->objectiveValue();
1461    }
1462  }
1463  return r_val;
1464}
1465
1466/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
1467*/
Note: See TracBrowser for help on using the repository browser.