source: trunk/Cbc/src/CbcTree.cpp @ 2097

Last change on this file since 2097 was 2097, checked in by forrest, 4 years ago

try and improve memory leaks (and clean up Clp pthread build problem)

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