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

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

more options, copy statistics structure analysis
start coding of "switch" variables i.e. badly scaled ints or hi/lo
changes to allow more influence on small branch and bound
changes to get correct printout with threads

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 46.1 KB
Line 
1/* $Id: CbcTree.cpp 1943 2013-07-21 09:05:45Z 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    lastObjective_ = x->objectiveValue();
366    lastDepth_ = x->depth();
367    lastUnsatisfied_ = x->numberUnsatisfied();
368    maximumNodeNumber_++;
369#   if CBC_DEBUG_HEAP > 2
370    CbcNodeInfo *info = x->nodeInfo() ;
371    assert(info) ;
372    std::cout
373      << "  HEAP: Pushing node " << x->nodeNumber()
374      << "(" << std::hex << x << std::dec << ") obj " << x->objectiveValue()
375      << ", ref " << info->decrement(0)
376      << ", todo " << info->numberBranchesLeft()
377      << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
378    assert(x->objectiveValue() != COIN_DBL_MAX);
379#   endif
380#   if CBC_DEBUG_HEAP > 0
381    validateHeap() ;
382#   endif
383    x->setOnTree(true);
384    nodes_.push_back(x);
385    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
386#   if CBC_DEBUG_HEAP > 0
387    validateHeap() ;
388#   endif
389}
390
391// Remove the top node from the heap
392void
393CbcTree::pop()
394{
395   
396#   if CBC_DEBUG_HEAP > 2
397    CbcNode *node = nodes_.front() ;
398    CbcNodeInfo *info = node->nodeInfo() ;
399    assert(info) ;
400    std::cout
401      << "  HEAP: Popping node " << node->nodeNumber()
402      << "(" << std::hex << node << std::dec
403      << ") obj " << node->objectiveValue()
404      << ", ref " << info->decrement(0)
405      << ", todo " << info->numberBranchesLeft()
406      << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
407#   endif
408#   if CBC_DEBUG_HEAP > 0
409    validateHeap() ;
410#   endif
411    nodes_.front()->setOnTree(false);
412    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
413    nodes_.pop_back();
414
415#   if CBC_DEBUG_HEAP > 0
416    validateHeap() ;
417#   endif
418
419}
420
421// Test if empty *** note may be overridden
422bool
423CbcTree::empty()
424{
425    return nodes_.empty();
426}
427/*
428  Return the best node from the heap.
429
430  Note that best is offered a chance (checkIsCutoff) to reevaluate
431  itself and make arbitrary changes. A caller should be prepared
432  to check that the returned node is acceptable.
433
434  There's quite a bit of suspect code here, much of it disabled in
435  some way. The net effect at present is to return the top node on
436  the heap after offering the node an opportunity to reevaluate itself.
437  Documentation for checkIsCutoff() puts no restrictions on allowable
438  changes. -- lh, 100921 --
439*/
440CbcNode *
441CbcTree::bestNode(double cutoff)
442{
443# if CBC_DEBUG_HEAP > 0
444  validateHeap() ;
445# endif
446/*
447  This code is problematic. As of 100921, there's really no loop.
448  If front() == null, an assert will trigger. checkIsCutoff seems to be
449  work in progress; comments assert that it can make pretty much arbitrary
450  changes to best. If best can change its objective, there's a good
451  possibility the heap is invalid.
452*/
453    CbcNode * best = NULL;
454    while (!best && nodes_.size()) {
455        best = nodes_.front();
456        if (best)
457            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
458        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
459            assert (best->nodeInfo()->numberBranchesLeft());
460        if (best && best->objectiveValue() >= cutoff) {
461            // double check in case node can change its mind!
462            best->checkIsCutoff(cutoff);
463        }
464        if (!best || best->objectiveValue() >= cutoff) {
465#ifdef JJF_ZERO
466            // take off
467            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
468            nodes_.pop_back();
469            delete best;
470            best = NULL;
471#else
472            // let code get rid of it
473            assert (best);
474#endif
475        }
476    }
477/*
478  See if the comparison object wants us to do a full scan with the
479  alternative criteria. The net effect is to confirm best by the
480  alternative criteria, or identify a competitor and erase it.
481
482  This code is problematic. Nulling an arbitrary node will in general
483  break the heap property. Disabled some time ago, as noted in several
484  places.
485*/
486    if (false && best && comparison_.test_->fullScan()) {
487        CbcNode * saveBest = best;
488        size_t n = nodes_.size();
489        size_t iBest = -1;
490        for (size_t i = 0; i < n; i++) {
491            // temp
492            assert (nodes_[i]);
493            assert (nodes_[i]->nodeInfo());
494            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
495                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
496            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
497                    && comparison_.alternateTest(best, nodes_[i])) {
498                best = nodes_[i];
499                iBest = i;
500            }
501        }
502        if (best == saveBest) {
503            // can pop
504            // take off
505            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
506            nodes_.pop_back();
507        } else {
508            // make impossible
509            nodes_[iBest] = NULL;
510        }
511    } else if (best) {
512#       if CBC_DEBUG_HEAP > 2
513        CbcNode *node = nodes_.front() ;
514        CbcNodeInfo *info = node->nodeInfo() ;
515        assert(info) ;
516        std::cout
517          << "  bestNode: Popping node " << node->nodeNumber()
518          << "(" << std::hex << node << std::dec
519          << ") obj " << node->objectiveValue()
520          << ", ref " << info->decrement(0)
521          << ", todo " << info->numberBranchesLeft()
522          << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
523#       endif
524        // take off
525        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
526        nodes_.pop_back();
527    }
528#if CBC_DEBUG_HEAP > 0
529    validateHeap() ;
530#endif
531    if (best)
532        best->setOnTree(false);
533    return best;
534}
535/*! \brief Prune the tree using an objective function cutoff
536
537  This routine removes all nodes with objective worse than the
538  specified cutoff value.
539*/
540
541void
542CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
543{
544#   if CBC_DEBUG_HEAP > 1
545    std::cout << " cleanTree: beginning clean." << std::endl ;
546#   endif
547#   if CBC_DEBUG_HEAP > 0
548    validateHeap() ;
549#   endif
550    int j;
551    int nNodes = size();
552    CbcNode ** nodeArray = new CbcNode * [nNodes];
553    int * depth = new int [nNodes];
554    int k = 0;
555    int kDelete = nNodes;
556    bestPossibleObjective = 1.0e100 ;
557    /*
558        Destructively scan the heap. Nodes to be retained go into the front of
559        nodeArray, nodes to be deleted into the back. Store the depth in a
560        correlated array for nodes to be deleted.
561    */
562    for (j = 0; j < nNodes; j++) {
563        CbcNode * node = top();
564        pop();
565        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
566        if (node && value >= cutoff) {
567            // double check in case node can change its mind!
568            value = node->checkIsCutoff(cutoff);
569        }
570        if (value >= cutoff || !node->active()) {
571            if (node) {
572                if (cutoff<-1.0e30)
573                  node->nodeInfo()->deactivate(7);
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
615      should make no difference.
616
617      Arguably a separate routine should be used in place of addCuts1. It's
618      doing more work than needed, modifying the model to match a subproblem
619      at a node 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
1007      should make no difference.
1008
1009      Arguably a separate routine should be used in place of addCuts1. It's
1010      doing more work than needed, modifying the model to match a subproblem
1011      at a node 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
1293      should make no difference.
1294
1295      Arguably a separate routine should be used in place of addCuts1. It's
1296      doing more work than needed, modifying the model to match a subproblem
1297      at a node 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
1400double
1401CbcTree::getBestPossibleObjective()
1402{
1403    double r_val = 1e100;
1404    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
1405        if (nodes_[i] && nodes_[i]->objectiveValue() < r_val) {
1406            r_val = nodes_[i]->objectiveValue();
1407        }
1408    }
1409    return r_val;
1410}
1411
Note: See TracBrowser for help on using the repository browser.