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

Last change on this file since 1750 was 1573, checked in by lou, 9 years ago

Change to EPL license notice.

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