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

Last change on this file since 1813 was 1813, checked in by forrest, 6 years ago

add random seed setting

  • 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 1813 2012-11-22 19:00:22Z forrest $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include "CbcModel.hpp"
7#include "CbcNode.hpp"
8#include "CbcTree.hpp"
9#include "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#ifndef CBC_DUBIOUS_HEAP
319/*
320  Set comparison predicate and re-sort the heap.
321
322  Note that common usage is to tweak the incumbent predicate and then
323  call this method to rebuild the heap. Hence we cannot check for heap
324  validity at entry. rebuild() will check on the way out, if
325  CBC_DEBUG_HEAP is set.
326
327  TODO: remove the call to cleanDive and put it somewhere appropriate.
328*/
329void
330CbcTree::setComparison(CbcCompareBase  &compare)
331{
332#   if CBC_DEBUG_HEAP > 1
333    std::cout << "  HEAP: resetting comparison predicate." << std::endl ;
334#   endif
335    comparison_.test_ = &compare;
336   
337/*
338  From a software engineering point of view, setComparison has no business
339  knowing anything about the comparison function. Need to look for a better
340  solution. Perhaps a callback comparable to newSolution, executing when
341  the comparison method is set (i.e., in setComparison).
342  -- lh, 100921 --
343*/
344    CbcCompareDefault *compareD =
345          dynamic_cast<CbcCompareDefault *>(&compare);
346    if (compareD) {
347        // clean up diving
348        compareD->cleanDive();
349    }
350    rebuild() ;
351}
352
353// Return the top node of the heap
354CbcNode *
355CbcTree::top() const
356{
357    return nodes_.front();
358}
359
360// Add a node to the heap
361void
362CbcTree::push(CbcNode * x)
363{
364    x->setNodeNumber(maximumNodeNumber_);
365    maximumNodeNumber_++;
366#   if CBC_DEBUG_HEAP > 2
367    CbcNodeInfo *info = x->nodeInfo() ;
368    assert(info) ;
369    std::cout
370      << "  HEAP: Pushing node " << x->nodeNumber()
371      << "(" << std::hex << x << std::dec << ") obj " << x->objectiveValue()
372      << ", ref " << info->decrement(0)
373      << ", todo " << info->numberBranchesLeft()
374      << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
375    assert(x->objectiveValue() != COIN_DBL_MAX);
376#   endif
377#   if CBC_DEBUG_HEAP > 0
378    validateHeap() ;
379#   endif
380    x->setOnTree(true);
381    nodes_.push_back(x);
382    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
383#   if CBC_DEBUG_HEAP > 0
384    validateHeap() ;
385#   endif
386}
387
388// Remove the top node from the heap
389void
390CbcTree::pop()
391{
392   
393#   if CBC_DEBUG_HEAP > 2
394    CbcNode *node = nodes_.front() ;
395    CbcNodeInfo *info = node->nodeInfo() ;
396    assert(info) ;
397    std::cout
398      << "  HEAP: Popping node " << node->nodeNumber()
399      << "(" << std::hex << node << std::dec
400      << ") obj " << node->objectiveValue()
401      << ", ref " << info->decrement(0)
402      << ", todo " << info->numberBranchesLeft()
403      << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
404#   endif
405#   if CBC_DEBUG_HEAP > 0
406    validateHeap() ;
407#   endif
408    nodes_.front()->setOnTree(false);
409    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
410    nodes_.pop_back();
411
412#   if CBC_DEBUG_HEAP > 0
413    validateHeap() ;
414#   endif
415
416}
417
418// Test if empty *** note may be overridden
419bool
420CbcTree::empty()
421{
422    return nodes_.empty();
423}
424/*
425  Return the best node from the heap.
426
427  Note that best is offered a chance (checkIsCutoff) to reevaluate
428  itself and make arbitrary changes. A caller should be prepared
429  to check that the returned node is acceptable.
430
431  There's quite a bit of suspect code here, much of it disabled in
432  some way. The net effect at present is to return the top node on
433  the heap after offering the node an opportunity to reevaluate itself.
434  Documentation for checkIsCutoff() puts no restrictions on allowable
435  changes. -- lh, 100921 --
436*/
437CbcNode *
438CbcTree::bestNode(double cutoff)
439{
440# if CBC_DEBUG_HEAP > 0
441  validateHeap() ;
442# endif
443/*
444  This code is problematic. As of 100921, there's really no loop.
445  If front() == null, an assert will trigger. checkIsCutoff seems to be
446  work in progress; comments assert that it can make pretty much arbitrary
447  changes to best. If best can change its objective, there's a good
448  possibility the heap is invalid.
449*/
450    CbcNode * best = NULL;
451    while (!best && nodes_.size()) {
452        best = nodes_.front();
453        if (best)
454            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
455        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
456            assert (best->nodeInfo()->numberBranchesLeft());
457        if (best && best->objectiveValue() >= cutoff) {
458            // double check in case node can change its mind!
459            best->checkIsCutoff(cutoff);
460        }
461        if (!best || best->objectiveValue() >= cutoff) {
462#ifdef JJF_ZERO
463            // take off
464            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
465            nodes_.pop_back();
466            delete best;
467            best = NULL;
468#else
469            // let code get rid of it
470            assert (best);
471#endif
472        }
473    }
474/*
475  See if the comparison object wants us to do a full scan with the
476  alternative criteria. The net effect is to confirm best by the
477  alternative criteria, or identify a competitor and erase it.
478
479  This code is problematic. Nulling an arbitrary node will in general
480  break the heap property. Disabled some time ago, as noted in several
481  places.
482*/
483    if (false && best && comparison_.test_->fullScan()) {
484        CbcNode * saveBest = best;
485        size_t n = nodes_.size();
486        size_t iBest = -1;
487        for (size_t i = 0; i < n; i++) {
488            // temp
489            assert (nodes_[i]);
490            assert (nodes_[i]->nodeInfo());
491            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
492                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
493            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
494                    && comparison_.alternateTest(best, nodes_[i])) {
495                best = nodes_[i];
496                iBest = i;
497            }
498        }
499        if (best == saveBest) {
500            // can pop
501            // take off
502            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
503            nodes_.pop_back();
504        } else {
505            // make impossible
506            nodes_[iBest] = NULL;
507        }
508    } else if (best) {
509#       if CBC_DEBUG_HEAP > 2
510        CbcNode *node = nodes_.front() ;
511        CbcNodeInfo *info = node->nodeInfo() ;
512        assert(info) ;
513        std::cout
514          << "  bestNode: Popping node " << node->nodeNumber()
515          << "(" << std::hex << node << std::dec
516          << ") obj " << node->objectiveValue()
517          << ", ref " << info->decrement(0)
518          << ", todo " << info->numberBranchesLeft()
519          << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
520#       endif
521        // take off
522        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
523        nodes_.pop_back();
524    }
525#if CBC_DEBUG_HEAP > 0
526    validateHeap() ;
527#endif
528    if (best)
529        best->setOnTree(false);
530    return best;
531}
532/*! \brief Prune the tree using an objective function cutoff
533
534  This routine removes all nodes with objective worse than the
535  specified cutoff value.
536*/
537
538void
539CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
540{
541#   if CBC_DEBUG_HEAP > 1
542    std::cout << " cleanTree: beginning clean." << std::endl ;
543#   endif
544#   if CBC_DEBUG_HEAP > 0
545    validateHeap() ;
546#   endif
547    int j;
548    int nNodes = size();
549    CbcNode ** nodeArray = new CbcNode * [nNodes];
550    int * depth = new int [nNodes];
551    int k = 0;
552    int kDelete = nNodes;
553    bestPossibleObjective = 1.0e100 ;
554    /*
555        Destructively scan the heap. Nodes to be retained go into the front of
556        nodeArray, nodes to be deleted into the back. Store the depth in a
557        correlated array for nodes to be deleted.
558    */
559    for (j = 0; j < nNodes; j++) {
560        CbcNode * node = top();
561        pop();
562        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
563        if (node && value >= cutoff) {
564            // double check in case node can change its mind!
565            value = node->checkIsCutoff(cutoff);
566        }
567        if (value >= cutoff || !node->active()) {
568            if (node) {
569                nodeArray[--kDelete] = node;
570                depth[kDelete] = node->depth();
571            }
572        } else {
573            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
574            nodeArray[k++] = node;
575        }
576    }
577    /*
578      Rebuild the heap using the retained nodes.
579    */
580    for (j = 0; j < k; j++) {
581        push(nodeArray[j]);
582    }
583#   if CBC_DEBUG_HEAP > 1
584    std::cout << " cleanTree: finished rebuild." << std::endl ;
585#   endif
586#   if CBC_DEBUG_HEAP > 0
587    validateHeap() ;
588#   endif
589    /*
590      Sort the list of nodes to be deleted, nondecreasing.
591    */
592    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
593    /*
594      Work back from deepest to shallowest. In spite of the name, addCuts1 is
595      just a preparatory step. When it returns, the following will be true:
596        * all cuts are removed from the solver's copy of the constraint system;
597        * lastws will be a basis appropriate for the specified node;
598        * variable bounds will be adjusted to be appropriate for the specified
599          node;
600        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
601          should be added to the constraint system at this node (but they have
602          not actually been added).
603      Then we scan the cut list for the node. Decrement the reference count
604      for the cut, and if it's gone to 0, really delete it.
605
606      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
607      are necessary. When reconstructing a node, these checks are used to skip
608      over loose cuts, excluding them from the reconstituted basis. But here
609      we're just interested in correcting the reference count. Tight/loose
610      should make no difference.
611
612      Arguably a separate routine should be used in place of addCuts1. It's
613      doing more work than needed, modifying the model to match a subproblem
614      at a node that will be discarded.  Then again, we seem to need the basis.
615    */
616    for (j = nNodes - 1; j >= kDelete; j--) {
617        CbcNode * node = nodeArray[j];
618        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
619
620        model->addCuts1(node, lastws);
621        // Decrement cut counts
622        assert (node);
623        //assert (node->nodeInfo());
624        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
625        int i;
626        for (i = 0; i < model->currentNumberCuts(); i++) {
627            // take off node
628            CoinWarmStartBasis::Status status =
629                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
630            if (status != CoinWarmStartBasis::basic &&
631                    model->addedCuts()[i]) {
632                if (!model->addedCuts()[i]->decrement(numberLeft))
633                    delete model->addedCuts()[i];
634            }
635        }
636        // node should not have anything pointing to it
637        if (node->nodeInfo())
638            node->nodeInfo()->throwAway();
639        delete node ;
640        delete lastws ;
641    }
642    delete [] nodeArray;
643    delete [] depth;
644}
645
646// Return the best node of the heap using alternate criterion
647CbcNode *
648CbcTree::bestAlternate()
649{
650    size_t n = nodes_.size();
651    CbcNode * best = NULL;
652    if (n) {
653        best = nodes_[0];
654        for (size_t i = 1; i < n; i++) {
655            if (comparison_.alternateTest(best, nodes_[i])) {
656                best = nodes_[i];
657            }
658        }
659    }
660    return best;
661}
662
663#ifdef JJF_ZERO // not used, reference removed in CbcModel.cpp
664CbcTreeArray::CbcTreeArray()
665        : CbcTree(),
666        lastNode_(NULL),
667        lastNodePopped_(NULL),
668        switches_(0)
669{
670}
671CbcTreeArray::~CbcTreeArray()
672{
673}
674// Copy constructor
675CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
676        : CbcTree(rhs),
677        lastNode_(rhs.lastNode_),
678        lastNodePopped_(rhs.lastNodePopped_),
679        switches_(rhs.switches_)
680{
681}
682// Assignment operator
683CbcTreeArray &
684CbcTreeArray::operator=(const CbcTreeArray & rhs)
685{
686    if (this != &rhs) {
687        CbcTree::operator=(rhs);
688        lastNode_ = rhs.lastNode_;
689        lastNodePopped_ = rhs.lastNodePopped_;
690        switches_ = rhs.switches_;
691    }
692    return *this;
693}
694// Clone
695CbcTree *
696CbcTreeArray::clone() const
697{
698    return new CbcTreeArray(*this);
699}
700// Set comparison function and resort heap
701void
702CbcTreeArray::setComparison(CbcCompareBase  &compare)
703{
704    comparison_.test_ = &compare;
705    rebuild() ;
706}
707
708// Add a node to the heap
709void
710CbcTreeArray::push(CbcNode * x)
711{
712    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
713       x->objectiveValue(),x->nodeInfo()->decrement(0),
714       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
715    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
716    x->setOnTree(true);
717    if (lastNode_) {
718        if (lastNode_->nodeInfo()->parent() == x->nodeInfo()) {
719            // x is parent of lastNode_ so put x on heap
720            //#define CBCTREE_PRINT
721#ifdef CBCTREE_PRINT
722            printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
723                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
724                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
725#endif
726            nodes_.push_back(x);
727        } else {
728            x->setNodeNumber(maximumNodeNumber_);
729            maximumNodeNumber_++;
730#ifdef CBCTREE_PRINT
731            printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
732                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
733                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
734#endif
735            nodes_.push_back(lastNode_);
736            lastNode_ = x;
737        }
738        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
739    } else {
740        x->setNodeNumber(maximumNodeNumber_);
741        maximumNodeNumber_++;
742        if (x != lastNodePopped_) {
743            lastNode_ = x;
744#ifdef CBCTREE_PRINT
745            printf("pushNULL x %x (%x at depth %d n %d)\n",
746                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
747#endif
748        } else {
749            // means other way was infeasible
750#ifdef CBCTREE_PRINT
751            printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
752                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
753#endif
754            nodes_.push_back(x);
755            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
756        }
757    }
758}
759
760// Test if empty *** note may be overridden
761bool
762CbcTreeArray::empty()
763{
764    return nodes_.empty() && (lastNode_ == NULL);
765}
766// Gets best node and takes off heap
767CbcNode *
768CbcTreeArray::bestNode(double cutoff)
769{
770    CbcNode * best = NULL;
771    // See if we want last node or best on heap
772    if (lastNode_) {
773#ifdef CBCTREE_PRINT
774        printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
775               lastNode_, lastNode_->nodeInfo(), lastNode_->depth(),
776               lastNode_->nodeNumber(), lastNode_->objectiveValue());
777#endif
778        assert (lastNode_->onTree());
779        int nodeNumber = lastNode_->nodeNumber();
780        bool useLastNode = false;
781        if (nodeNumber + 1 == maximumNodeNumber_) {
782            // diving - look further
783            CbcCompareDefault * compareDefault
784            = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
785            assert (compareDefault);
786            double bestPossible = compareDefault->getBestPossible();
787            double cutoff = compareDefault->getCutoff();
788            double objValue = lastNode_->objectiveValue();
789            if (cutoff < 1.0e20) {
790                if (objValue - bestPossible < 0.999*(cutoff - bestPossible))
791                    useLastNode = true;
792            } else {
793                useLastNode = true;
794            }
795        }
796        if (useLastNode) {
797            lastNode_->setOnTree(false);
798            best = lastNode_;
799            lastNode_ = NULL;
800            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
801            if (best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
802                assert (best->nodeInfo()->numberBranchesLeft());
803            if (best->objectiveValue() >= cutoff) {
804                // double check in case node can change its mind!
805                best->checkIsCutoff(cutoff);
806            }
807            lastNodePopped_ = best;
808            return best;
809        } else {
810            // put on tree
811            nodes_.push_back(lastNode_);
812            lastNode_->setNodeNumber(maximumNodeNumber_);
813            maximumNodeNumber_++;
814            lastNode_ = NULL;
815            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
816        }
817    }
818    while (!best && nodes_.size()) {
819        best = nodes_.front();
820        if (best)
821            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
822        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
823            assert (best->nodeInfo()->numberBranchesLeft());
824        if (best && best->objectiveValue() >= cutoff) {
825            // double check in case node can change its mind!
826            best->checkIsCutoff(cutoff);
827        }
828        if (!best || best->objectiveValue() >= cutoff) {
829            // let code get rid of it
830            assert (best);
831        }
832    }
833    lastNodePopped_ = best;
834#ifdef CBCTREE_PRINT
835    if (best)
836        printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
837               best, best->nodeInfo(), best->depth(),
838               best->nodeNumber(), best->objectiveValue());
839    else
840        printf("Heap returning Null\n");
841#endif
842    if (best) {
843        // take off
844        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
845        nodes_.pop_back();
846    }
847#ifdef DEBUG_CBC_HEAP
848    if (best) {
849        int n = nodes_.size();
850        bool good = true;
851        for (int i = 0; i < n; i++) {
852            // temp
853            assert (nodes_[i]);
854            if (!comparison_.compareNodes(nodes_[i], best)) {
855                good = false;
856                CbcNode * x = nodes_[i];
857                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
858                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
859                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
860            }
861        }
862        if (!good) {
863            // compare best to all
864            int i;
865            for (i = 0; i < n; i++) {
866                CbcNode * x = nodes_[i];
867                printf("i=%d x is nun %d depth %d obj %g", i,
868                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
869                if (!comparison_.compareNodes(x, best)) {
870                    printf(" - best is worse!\n");
871                } else {
872                    printf("\n");
873                }
874            }
875            // Now compare amongst rest
876            for (i = 0; i < n; i++) {
877                CbcNode * x = nodes_[i];
878                printf("For i=%d ", i);
879                for (int j = i + 1; j < n; j++) {
880                    CbcNode * y = nodes_[j];
881                    if (!comparison_.compareNodes(x, y)) {
882                        printf(" b %d", j);
883                    } else {
884                        printf(" w %d", j);
885                    }
886                }
887                printf("\n");
888            }
889            assert(good);
890        }
891    }
892#endif
893    if (best)
894        best->setOnTree(false);
895    return best;
896}
897
898double
899CbcTreeArray::getBestPossibleObjective()
900{
901    double bestPossibleObjective = 1e100;
902    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
903        if (nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective) {
904            bestPossibleObjective = nodes_[i]->objectiveValue();
905        }
906    }
907    if (lastNode_) {
908        bestPossibleObjective = CoinMin(bestPossibleObjective, lastNode_->objectiveValue());
909    }
910    CbcCompareDefault * compareDefault
911    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
912    assert (compareDefault);
913    compareDefault->setBestPossible(bestPossibleObjective);
914    return bestPossibleObjective;
915}
916/*! \brief Prune the tree using an objective function cutoff
917
918  This routine removes all nodes with objective worst than the
919  specified cutoff value.
920*/
921
922void
923CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
924{
925    int j;
926    int nNodes = size();
927    int lastNode = nNodes + 1;
928    CbcNode ** nodeArray = new CbcNode * [lastNode];
929    int * depth = new int [lastNode];
930    int k = 0;
931    int kDelete = lastNode;
932    bestPossibleObjective = 1.0e100 ;
933    /*
934        Destructively scan the heap. Nodes to be retained go into the front of
935        nodeArray, nodes to be deleted into the back. Store the depth in a
936        correlated array for nodes to be deleted.
937    */
938    for (j = 0; j < nNodes; j++) {
939        CbcNode * node = nodes_.front();
940        nodes_.front()->setOnTree(false);
941        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
942        nodes_.pop_back();
943        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
944        if (node && value >= cutoff) {
945            // double check in case node can change its mind!
946            value = node->checkIsCutoff(cutoff);
947        }
948        if (value >= cutoff || !node->active()) {
949            if (node) {
950                nodeArray[--kDelete] = node;
951                depth[kDelete] = node->depth();
952            }
953        } else {
954            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
955            nodeArray[k++] = node;
956        }
957    }
958    if (lastNode_) {
959        double value = lastNode_->objectiveValue();
960        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
961        if (value >= cutoff || !lastNode_->active()) {
962            nodeArray[--kDelete] = lastNode_;
963            depth[kDelete] = lastNode_->depth();
964            lastNode_ = NULL;
965        }
966    }
967    CbcCompareDefault * compareDefault
968    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
969    assert (compareDefault);
970    compareDefault->setBestPossible(bestPossibleObjective);
971    compareDefault->setCutoff(cutoff);
972    /*
973      Rebuild the heap using the retained nodes.
974    */
975    for (j = 0; j < k; j++) {
976        CbcNode * node = nodeArray[j];
977        node->setOnTree(true);
978        nodes_.push_back(node);
979        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
980    }
981    /*
982      Sort the list of nodes to be deleted, nondecreasing.
983    */
984    CoinSort_2(depth + kDelete, depth + lastNode, nodeArray + kDelete);
985    /*
986      Work back from deepest to shallowest. In spite of the name, addCuts1 is
987      just a preparatory step. When it returns, the following will be true:
988        * all cuts are removed from the solver's copy of the constraint system;
989        * lastws will be a basis appropriate for the specified node;
990        * variable bounds will be adjusted to be appropriate for the specified
991          node;
992        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
993          should be added to the constraint system at this node (but they have
994          not actually been added).
995      Then we scan the cut list for the node. Decrement the reference count
996      for the cut, and if it's gone to 0, really delete it.
997
998      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
999      are necessary. When reconstructing a node, these checks are used to skip
1000      over loose cuts, excluding them from the reconstituted basis. But here
1001      we're just interested in correcting the reference count. Tight/loose
1002      should make no difference.
1003
1004      Arguably a separate routine should be used in place of addCuts1. It's
1005      doing more work than needed, modifying the model to match a subproblem
1006      at a node that will be discarded.  Then again, we seem to need the basis.
1007    */
1008    for (j = lastNode - 1; j >= kDelete; j--) {
1009        CbcNode * node = nodeArray[j];
1010        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1011
1012        model->addCuts1(node, lastws);
1013        // Decrement cut counts
1014        assert (node);
1015        //assert (node->nodeInfo());
1016        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1017        int i;
1018        for (i = 0; i < model->currentNumberCuts(); i++) {
1019            // take off node
1020            CoinWarmStartBasis::Status status =
1021                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1022            if (status != CoinWarmStartBasis::basic &&
1023                    model->addedCuts()[i]) {
1024                if (!model->addedCuts()[i]->decrement(numberLeft))
1025                    delete model->addedCuts()[i];
1026            }
1027        }
1028        // node should not have anything pointing to it
1029        if (node->nodeInfo())
1030            node->nodeInfo()->throwAway();
1031        delete node ;
1032        delete lastws ;
1033    }
1034    delete [] nodeArray;
1035    delete [] depth;
1036}
1037#endif
1038
1039#else  // defined(CBC_DUBIOUS_HEAP)
1040
1041/*
1042  Unclear whether this code is useful any longer. Likely stale. See
1043  note in CbcCompareDefault.hpp re. CBC_DUBIOUS_HEAP.
1044  -- lh, 100921 --
1045*/
1046
1047// Set comparison function and resort heap
1048void
1049CbcTree::setComparison(CbcCompareBase  &compare)
1050{
1051    comparison_.test_ = &compare;
1052    std::vector <CbcNode *> newNodes = nodes_;
1053    nodes_.resize(0);
1054    while (newNodes.size() > 0) {
1055        push( newNodes.back());
1056        newNodes.pop_back();
1057    }
1058}
1059
1060// Return the top node of the heap
1061CbcNode *
1062CbcTree::top() const
1063{
1064    return nodes_.front();
1065}
1066
1067// Add a node to the heap
1068void
1069CbcTree::push(CbcNode * x)
1070{
1071    x->setNodeNumber(maximumNodeNumber_);
1072    maximumNodeNumber_++;
1073    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
1074       x->objectiveValue(),x->nodeInfo()->decrement(0),
1075       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
1076    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
1077#ifdef JJF_ZERO
1078    nodes_.push_back(x);
1079    push_heap(nodes_.begin(), nodes_.end(), comparison_);
1080#else
1081realpush(x);
1082#endif
1083}
1084
1085// Remove the top node from the heap
1086void
1087CbcTree::pop()
1088{
1089#ifdef JJF_ZERO
1090    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1091    nodes_.pop_back();
1092#else
1093if (nodes_.size()) {
1094    //CbcNode* s = nodes_.front();
1095    realpop();
1096    //delete s;
1097}
1098assert (nodes_.size() >= 0);
1099#endif
1100}
1101
1102// Test if empty *** note may be overridden
1103bool
1104CbcTree::empty()
1105{
1106    return nodes_.empty();
1107}
1108// Gets best node and takes off heap
1109CbcNode *
1110CbcTree::bestNode(double cutoff)
1111{
1112    CbcNode * best = NULL;
1113    while (!best && nodes_.size()) {
1114        best = nodes_.front();
1115        if (best)
1116            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
1117        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
1118            assert (best->nodeInfo()->numberBranchesLeft());
1119        if (best && best->objectiveValue() >= cutoff) {
1120            // double check in case node can change its mind!
1121            best->checkIsCutoff(cutoff);
1122        }
1123        if (!best || best->objectiveValue() >= cutoff) {
1124#ifdef JJF_ZERO
1125            // take off
1126            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1127            nodes_.pop_back();
1128            delete best;
1129            best = NULL;
1130#else
1131// let code get rid of it
1132assert (best);
1133#endif
1134        }
1135    }
1136    // switched off for now
1137    if (best && comparison_.test_->fullScan() && false) {
1138        CbcNode * saveBest = best;
1139        int n = nodes_.size();
1140        int iBest = -1;
1141        for (int i = 0; i < n; i++) {
1142            // temp
1143            assert (nodes_[i]);
1144            assert (nodes_[i]->nodeInfo());
1145            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
1146                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
1147            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
1148                    && comparison_.alternateTest(best, nodes_[i])) {
1149                best = nodes_[i];
1150                iBest = i;
1151            }
1152        }
1153        if (best == saveBest) {
1154            // can pop
1155            // take off
1156            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1157            nodes_.pop_back();
1158        } else {
1159            // make impossible
1160            nodes_[iBest] = NULL;
1161        }
1162    } else if (best) {
1163        // take off
1164#ifdef JJF_ZERO
1165        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1166        nodes_.pop_back();
1167#else
1168realpop();
1169#endif
1170    }
1171#ifdef DEBUG_CBC_HEAP
1172    if (best) {
1173        int n = nodes_.size();
1174        bool good = true;
1175        for (int i = 0; i < n; i++) {
1176            // temp
1177            assert (nodes_[i]);
1178            if (!comparison_.compareNodes(nodes_[i], best)) {
1179                good = false;
1180                CbcNode * x = nodes_[i];
1181                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
1182                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
1183                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
1184            }
1185        }
1186        if (!good) {
1187            // compare best to all
1188            int i;
1189            for (i = 0; i < n; i++) {
1190                CbcNode * x = nodes_[i];
1191                printf("i=%d x is nun %d depth %d obj %g", i,
1192                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
1193                if (!comparison_.compareNodes(x, best)) {
1194                    printf(" - best is worse!\n");
1195                } else {
1196                    printf("\n");
1197                }
1198            }
1199            // Now compare amongst rest
1200            for (i = 0; i < n; i++) {
1201                CbcNode * x = nodes_[i];
1202                printf("For i=%d ", i);
1203                for (int j = i + 1; j < n; j++) {
1204                    CbcNode * y = nodes_[j];
1205                    if (!comparison_.compareNodes(x, y)) {
1206                        printf(" b %d", j);
1207                    } else {
1208                        printf(" w %d", j);
1209                    }
1210                }
1211                printf("\n");
1212            }
1213            assert(good);
1214        }
1215    }
1216#endif
1217    if (best)
1218        best->setOnTree(false);
1219    return best;
1220}
1221
1222/*! \brief Prune the tree using an objective function cutoff
1223
1224  This routine removes all nodes with objective worst than the
1225  specified cutoff value.
1226*/
1227
1228void
1229CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1230{
1231    int j;
1232    int nNodes = nodes_.size();
1233    CbcNode ** nodeArray = new CbcNode * [nNodes];
1234    int * depth = new int [nNodes];
1235    int k = 0;
1236    int kDelete = nNodes;
1237    bestPossibleObjective = 1.0e100 ;
1238    /*
1239        Destructively scan the heap. Nodes to be retained go into the front of
1240        nodeArray, nodes to be deleted into the back. Store the depth in a
1241        correlated array for nodes to be deleted.
1242    */
1243    for (j = 0; j < nNodes; j++) {
1244        CbcNode * node = top();
1245        pop();
1246        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1247        if (node && value >= cutoff) {
1248            // double check in case node can change its mind!
1249            value = node->checkIsCutoff(cutoff);
1250        }
1251        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1252        if (value >= cutoff) {
1253            if (node) {
1254                nodeArray[--kDelete] = node;
1255                depth[kDelete] = node->depth();
1256            }
1257        } else {
1258            nodeArray[k++] = node;
1259        }
1260    }
1261    /*
1262      Rebuild the heap using the retained nodes.
1263    */
1264    for (j = 0; j < k; j++) {
1265        push(nodeArray[j]);
1266    }
1267    /*
1268      Sort the list of nodes to be deleted, nondecreasing.
1269    */
1270    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
1271    /*
1272      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1273      just a preparatory step. When it returns, the following will be true:
1274        * all cuts are removed from the solver's copy of the constraint system;
1275        * lastws will be a basis appropriate for the specified node;
1276        * variable bounds will be adjusted to be appropriate for the specified
1277          node;
1278        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1279          should be added to the constraint system at this node (but they have
1280          not actually been added).
1281      Then we scan the cut list for the node. Decrement the reference count
1282      for the cut, and if it's gone to 0, really delete it.
1283
1284      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1285      are necessary. When reconstructing a node, these checks are used to skip
1286      over loose cuts, excluding them from the reconstituted basis. But here
1287      we're just interested in correcting the reference count. Tight/loose
1288      should make no difference.
1289
1290      Arguably a separate routine should be used in place of addCuts1. It's
1291      doing more work than needed, modifying the model to match a subproblem
1292      at a node that will be discarded.  Then again, we seem to need the basis.
1293    */
1294    for (j = nNodes - 1; j >= kDelete; j--) {
1295        CbcNode * node = nodeArray[j];
1296        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1297
1298        model->addCuts1(node, lastws);
1299        // Decrement cut counts
1300        assert (node);
1301        //assert (node->nodeInfo());
1302        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1303        int i;
1304        for (i = 0; i < model->currentNumberCuts(); i++) {
1305            // take off node
1306            CoinWarmStartBasis::Status status =
1307                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1308            if (status != CoinWarmStartBasis::basic &&
1309                    model->addedCuts()[i]) {
1310                if (!model->addedCuts()[i]->decrement(numberLeft))
1311                    delete model->addedCuts()[i];
1312            }
1313        }
1314        // node should not have anything pointing to it
1315        if (node->nodeInfo())
1316            node->nodeInfo()->throwAway();
1317        delete node ;
1318        delete lastws ;
1319    }
1320    delete [] nodeArray;
1321    delete [] depth;
1322}
1323
1324// Return the best node of the heap using alternate criterion
1325CbcNode *
1326CbcTree::bestAlternate()
1327{
1328    int n = nodes_.size();
1329    CbcNode * best = NULL;
1330    if (n) {
1331        best = nodes_[0];
1332        for (int i = 1; i < n; i++) {
1333            if (comparison_.alternateTest(best, nodes_[i])) {
1334                best = nodes_[i];
1335            }
1336        }
1337    }
1338    return best;
1339}
1340void
1341CbcTree::realpop()
1342{
1343    if (nodes_.size() > 0) {
1344        nodes_[0] = nodes_.back();
1345        nodes_.pop_back();
1346        fixTop();
1347    }
1348    assert (nodes_.size() >= 0);
1349}
1350/* After changing data in the top node, fix the heap */
1351void
1352CbcTree::fixTop()
1353{
1354    const int size = nodes_.size();
1355    if (size > 1) {
1356        CbcNode** candidates = &nodes_[0];
1357        CbcNode* s = candidates[0];
1358        --candidates;
1359        int pos = 1;
1360        int ch;
1361        for (ch = 2; ch < size; pos = ch, ch *= 2) {
1362            if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1363                ++ch;
1364            if (!comparison_.compareNodes(s, candidates[ch]))
1365                break;
1366            candidates[pos] = candidates[ch];
1367        }
1368        if (ch == size) {
1369            if (!comparison_.compareNodes(candidates[ch], s)) {
1370                candidates[pos] = candidates[ch];
1371                pos = ch;
1372            }
1373        }
1374        candidates[pos] = s;
1375    }
1376}
1377void
1378CbcTree::realpush(CbcNode * node)
1379{
1380    node->setOnTree(true);
1381    nodes_.push_back(node);
1382    CbcNode** candidates = &nodes_[0];
1383    --candidates;
1384    int pos = nodes_.size();
1385    int ch;
1386    for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
1387        if (!comparison_.compareNodes(candidates[ch], node))
1388            break;
1389        candidates[pos] = candidates[ch];
1390    }
1391    candidates[pos] = node;
1392}
1393#endif
1394
1395double
1396CbcTree::getBestPossibleObjective()
1397{
1398    double r_val = 1e100;
1399    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
1400        if (nodes_[i] && nodes_[i]->objectiveValue() < r_val) {
1401            r_val = nodes_[i]->objectiveValue();
1402        }
1403    }
1404    return r_val;
1405}
1406
Note: See TracBrowser for help on using the repository browser.