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

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

Fix `Invalid heap' error in cl debug builds. Add validateHeap method to CbcTree? for future debugging.

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