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

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

changes to fix bug on max nodes

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 46.4 KB
Line 
1/* $Id: CbcTree.cpp 1951 2013-08-02 14:26:23Z 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 = (cutoff!=-COIN_DBL_MAX) ? model->getEmptyBasis() : NULL;
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        if (cutoff != -COIN_DBL_MAX) {
631          // normal
632          for (int i = 0; i < model->currentNumberCuts(); i++) {
633            // take off node
634            CoinWarmStartBasis::Status status =
635                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
636            if (status != CoinWarmStartBasis::basic &&
637                    model->addedCuts()[i]) {
638                if (!model->addedCuts()[i]->decrement(numberLeft))
639                    delete model->addedCuts()[i];
640            }
641          }
642        } else {
643          // quick
644          for (int i = 0; i < model->currentNumberCuts(); i++) {
645            // take off node
646            if (model->addedCuts()[i]) {
647                if (!model->addedCuts()[i]->decrement(numberLeft))
648                    delete model->addedCuts()[i];
649            }
650          }
651        }
652        // node should not have anything pointing to it
653        if (node->nodeInfo())
654            node->nodeInfo()->throwAway();
655        delete node ;
656        delete lastws ;
657    }
658    delete [] nodeArray;
659    delete [] depth;
660}
661
662// Return the best node of the heap using alternate criterion
663CbcNode *
664CbcTree::bestAlternate()
665{
666    size_t n = nodes_.size();
667    CbcNode * best = NULL;
668    if (n) {
669        best = nodes_[0];
670        for (size_t i = 1; i < n; i++) {
671            if (comparison_.alternateTest(best, nodes_[i])) {
672                best = nodes_[i];
673            }
674        }
675    }
676    return best;
677}
678
679#ifdef JJF_ZERO // not used, reference removed in CbcModel.cpp
680CbcTreeArray::CbcTreeArray()
681        : CbcTree(),
682        lastNode_(NULL),
683        lastNodePopped_(NULL),
684        switches_(0)
685{
686}
687CbcTreeArray::~CbcTreeArray()
688{
689}
690// Copy constructor
691CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
692        : CbcTree(rhs),
693        lastNode_(rhs.lastNode_),
694        lastNodePopped_(rhs.lastNodePopped_),
695        switches_(rhs.switches_)
696{
697}
698// Assignment operator
699CbcTreeArray &
700CbcTreeArray::operator=(const CbcTreeArray & rhs)
701{
702    if (this != &rhs) {
703        CbcTree::operator=(rhs);
704        lastNode_ = rhs.lastNode_;
705        lastNodePopped_ = rhs.lastNodePopped_;
706        switches_ = rhs.switches_;
707    }
708    return *this;
709}
710// Clone
711CbcTree *
712CbcTreeArray::clone() const
713{
714    return new CbcTreeArray(*this);
715}
716// Set comparison function and resort heap
717void
718CbcTreeArray::setComparison(CbcCompareBase  &compare)
719{
720    comparison_.test_ = &compare;
721    rebuild() ;
722}
723
724// Add a node to the heap
725void
726CbcTreeArray::push(CbcNode * x)
727{
728    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
729       x->objectiveValue(),x->nodeInfo()->decrement(0),
730       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
731    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
732    x->setOnTree(true);
733    if (lastNode_) {
734        if (lastNode_->nodeInfo()->parent() == x->nodeInfo()) {
735            // x is parent of lastNode_ so put x on heap
736            //#define CBCTREE_PRINT
737#ifdef CBCTREE_PRINT
738            printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
739                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
740                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
741#endif
742            nodes_.push_back(x);
743        } else {
744            x->setNodeNumber(maximumNodeNumber_);
745            maximumNodeNumber_++;
746#ifdef CBCTREE_PRINT
747            printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
748                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
749                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
750#endif
751            nodes_.push_back(lastNode_);
752            lastNode_ = x;
753        }
754        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
755    } else {
756        x->setNodeNumber(maximumNodeNumber_);
757        maximumNodeNumber_++;
758        if (x != lastNodePopped_) {
759            lastNode_ = x;
760#ifdef CBCTREE_PRINT
761            printf("pushNULL x %x (%x at depth %d n %d)\n",
762                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
763#endif
764        } else {
765            // means other way was infeasible
766#ifdef CBCTREE_PRINT
767            printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
768                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
769#endif
770            nodes_.push_back(x);
771            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
772        }
773    }
774}
775
776// Test if empty *** note may be overridden
777bool
778CbcTreeArray::empty()
779{
780    return nodes_.empty() && (lastNode_ == NULL);
781}
782// Gets best node and takes off heap
783CbcNode *
784CbcTreeArray::bestNode(double cutoff)
785{
786    CbcNode * best = NULL;
787    // See if we want last node or best on heap
788    if (lastNode_) {
789#ifdef CBCTREE_PRINT
790        printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
791               lastNode_, lastNode_->nodeInfo(), lastNode_->depth(),
792               lastNode_->nodeNumber(), lastNode_->objectiveValue());
793#endif
794        assert (lastNode_->onTree());
795        int nodeNumber = lastNode_->nodeNumber();
796        bool useLastNode = false;
797        if (nodeNumber + 1 == maximumNodeNumber_) {
798            // diving - look further
799            CbcCompareDefault * compareDefault
800            = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
801            assert (compareDefault);
802            double bestPossible = compareDefault->getBestPossible();
803            double cutoff = compareDefault->getCutoff();
804            double objValue = lastNode_->objectiveValue();
805            if (cutoff < 1.0e20) {
806                if (objValue - bestPossible < 0.999*(cutoff - bestPossible))
807                    useLastNode = true;
808            } else {
809                useLastNode = true;
810            }
811        }
812        if (useLastNode) {
813            lastNode_->setOnTree(false);
814            best = lastNode_;
815            lastNode_ = NULL;
816            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
817            if (best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
818                assert (best->nodeInfo()->numberBranchesLeft());
819            if (best->objectiveValue() >= cutoff) {
820                // double check in case node can change its mind!
821                best->checkIsCutoff(cutoff);
822            }
823            lastNodePopped_ = best;
824            return best;
825        } else {
826            // put on tree
827            nodes_.push_back(lastNode_);
828            lastNode_->setNodeNumber(maximumNodeNumber_);
829            maximumNodeNumber_++;
830            lastNode_ = NULL;
831            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
832        }
833    }
834    while (!best && nodes_.size()) {
835        best = nodes_.front();
836        if (best)
837            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
838        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
839            assert (best->nodeInfo()->numberBranchesLeft());
840        if (best && best->objectiveValue() >= cutoff) {
841            // double check in case node can change its mind!
842            best->checkIsCutoff(cutoff);
843        }
844        if (!best || best->objectiveValue() >= cutoff) {
845            // let code get rid of it
846            assert (best);
847        }
848    }
849    lastNodePopped_ = best;
850#ifdef CBCTREE_PRINT
851    if (best)
852        printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
853               best, best->nodeInfo(), best->depth(),
854               best->nodeNumber(), best->objectiveValue());
855    else
856        printf("Heap returning Null\n");
857#endif
858    if (best) {
859        // take off
860        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
861        nodes_.pop_back();
862    }
863#ifdef DEBUG_CBC_HEAP
864    if (best) {
865        int n = nodes_.size();
866        bool good = true;
867        for (int i = 0; i < n; i++) {
868            // temp
869            assert (nodes_[i]);
870            if (!comparison_.compareNodes(nodes_[i], best)) {
871                good = false;
872                CbcNode * x = nodes_[i];
873                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
874                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
875                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
876            }
877        }
878        if (!good) {
879            // compare best to all
880            int i;
881            for (i = 0; i < n; i++) {
882                CbcNode * x = nodes_[i];
883                printf("i=%d x is nun %d depth %d obj %g", i,
884                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
885                if (!comparison_.compareNodes(x, best)) {
886                    printf(" - best is worse!\n");
887                } else {
888                    printf("\n");
889                }
890            }
891            // Now compare amongst rest
892            for (i = 0; i < n; i++) {
893                CbcNode * x = nodes_[i];
894                printf("For i=%d ", i);
895                for (int j = i + 1; j < n; j++) {
896                    CbcNode * y = nodes_[j];
897                    if (!comparison_.compareNodes(x, y)) {
898                        printf(" b %d", j);
899                    } else {
900                        printf(" w %d", j);
901                    }
902                }
903                printf("\n");
904            }
905            assert(good);
906        }
907    }
908#endif
909    if (best)
910        best->setOnTree(false);
911    return best;
912}
913
914double
915CbcTreeArray::getBestPossibleObjective()
916{
917    double bestPossibleObjective = 1e100;
918    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
919        if (nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective) {
920            bestPossibleObjective = nodes_[i]->objectiveValue();
921        }
922    }
923    if (lastNode_) {
924        bestPossibleObjective = CoinMin(bestPossibleObjective, lastNode_->objectiveValue());
925    }
926    CbcCompareDefault * compareDefault
927    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
928    assert (compareDefault);
929    compareDefault->setBestPossible(bestPossibleObjective);
930    return bestPossibleObjective;
931}
932/*! \brief Prune the tree using an objective function cutoff
933
934  This routine removes all nodes with objective worst than the
935  specified cutoff value.
936*/
937
938void
939CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
940{
941    int j;
942    int nNodes = size();
943    int lastNode = nNodes + 1;
944    CbcNode ** nodeArray = new CbcNode * [lastNode];
945    int * depth = new int [lastNode];
946    int k = 0;
947    int kDelete = lastNode;
948    bestPossibleObjective = 1.0e100 ;
949    /*
950        Destructively scan the heap. Nodes to be retained go into the front of
951        nodeArray, nodes to be deleted into the back. Store the depth in a
952        correlated array for nodes to be deleted.
953    */
954    for (j = 0; j < nNodes; j++) {
955        CbcNode * node = nodes_.front();
956        nodes_.front()->setOnTree(false);
957        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
958        nodes_.pop_back();
959        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
960        if (node && value >= cutoff) {
961            // double check in case node can change its mind!
962            value = node->checkIsCutoff(cutoff);
963        }
964        if (value >= cutoff || !node->active()) {
965            if (node) {
966                nodeArray[--kDelete] = node;
967                depth[kDelete] = node->depth();
968            }
969        } else {
970            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
971            nodeArray[k++] = node;
972        }
973    }
974    if (lastNode_) {
975        double value = lastNode_->objectiveValue();
976        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
977        if (value >= cutoff || !lastNode_->active()) {
978            nodeArray[--kDelete] = lastNode_;
979            depth[kDelete] = lastNode_->depth();
980            lastNode_ = NULL;
981        }
982    }
983    CbcCompareDefault * compareDefault
984    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
985    assert (compareDefault);
986    compareDefault->setBestPossible(bestPossibleObjective);
987    compareDefault->setCutoff(cutoff);
988    /*
989      Rebuild the heap using the retained nodes.
990    */
991    for (j = 0; j < k; j++) {
992        CbcNode * node = nodeArray[j];
993        node->setOnTree(true);
994        nodes_.push_back(node);
995        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
996    }
997    /*
998      Sort the list of nodes to be deleted, nondecreasing.
999    */
1000    CoinSort_2(depth + kDelete, depth + lastNode, nodeArray + kDelete);
1001    /*
1002      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1003      just a preparatory step. When it returns, the following will be true:
1004        * all cuts are removed from the solver's copy of the constraint system;
1005        * lastws will be a basis appropriate for the specified node;
1006        * variable bounds will be adjusted to be appropriate for the specified
1007          node;
1008        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1009          should be added to the constraint system at this node (but they have
1010          not actually been added).
1011      Then we scan the cut list for the node. Decrement the reference count
1012      for the cut, and if it's gone to 0, really delete it.
1013
1014      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1015      are necessary. When reconstructing a node, these checks are used to skip
1016      over loose cuts, excluding them from the reconstituted basis. But here
1017      we're just interested in correcting the reference count. Tight/loose
1018      should make no difference.
1019
1020      Arguably a separate routine should be used in place of addCuts1. It's
1021      doing more work than needed, modifying the model to match a subproblem
1022      at a node that will be discarded.  Then again, we seem to need the basis.
1023    */
1024    for (j = lastNode - 1; j >= kDelete; j--) {
1025        CbcNode * node = nodeArray[j];
1026        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1027
1028        model->addCuts1(node, lastws);
1029        // Decrement cut counts
1030        assert (node);
1031        //assert (node->nodeInfo());
1032        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1033        int i;
1034        for (i = 0; i < model->currentNumberCuts(); i++) {
1035            // take off node
1036            CoinWarmStartBasis::Status status =
1037                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1038            if (status != CoinWarmStartBasis::basic &&
1039                    model->addedCuts()[i]) {
1040                if (!model->addedCuts()[i]->decrement(numberLeft))
1041                    delete model->addedCuts()[i];
1042            }
1043        }
1044        // node should not have anything pointing to it
1045        if (node->nodeInfo())
1046            node->nodeInfo()->throwAway();
1047        delete node ;
1048        delete lastws ;
1049    }
1050    delete [] nodeArray;
1051    delete [] depth;
1052}
1053#endif
1054
1055#else  // defined(CBC_DUBIOUS_HEAP)
1056
1057/*
1058  Unclear whether this code is useful any longer. Likely stale. See
1059  note in CbcCompareDefault.hpp re. CBC_DUBIOUS_HEAP.
1060  -- lh, 100921 --
1061*/
1062
1063// Set comparison function and resort heap
1064void
1065CbcTree::setComparison(CbcCompareBase  &compare)
1066{
1067    comparison_.test_ = &compare;
1068    std::vector <CbcNode *> newNodes = nodes_;
1069    nodes_.resize(0);
1070    while (newNodes.size() > 0) {
1071        push( newNodes.back());
1072        newNodes.pop_back();
1073    }
1074}
1075
1076// Return the top node of the heap
1077CbcNode *
1078CbcTree::top() const
1079{
1080    return nodes_.front();
1081}
1082
1083// Add a node to the heap
1084void
1085CbcTree::push(CbcNode * x)
1086{
1087    x->setNodeNumber(maximumNodeNumber_);
1088    maximumNodeNumber_++;
1089    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
1090       x->objectiveValue(),x->nodeInfo()->decrement(0),
1091       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
1092    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
1093#ifdef JJF_ZERO
1094    nodes_.push_back(x);
1095    push_heap(nodes_.begin(), nodes_.end(), comparison_);
1096#else
1097realpush(x);
1098#endif
1099}
1100
1101// Remove the top node from the heap
1102void
1103CbcTree::pop()
1104{
1105#ifdef JJF_ZERO
1106    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1107    nodes_.pop_back();
1108#else
1109if (nodes_.size()) {
1110    //CbcNode* s = nodes_.front();
1111    realpop();
1112    //delete s;
1113}
1114assert (nodes_.size() >= 0);
1115#endif
1116}
1117
1118// Test if empty *** note may be overridden
1119bool
1120CbcTree::empty()
1121{
1122    return nodes_.empty();
1123}
1124// Gets best node and takes off heap
1125CbcNode *
1126CbcTree::bestNode(double cutoff)
1127{
1128    CbcNode * best = NULL;
1129    while (!best && nodes_.size()) {
1130        best = nodes_.front();
1131        if (best)
1132            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
1133        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
1134            assert (best->nodeInfo()->numberBranchesLeft());
1135        if (best && best->objectiveValue() >= cutoff) {
1136            // double check in case node can change its mind!
1137            best->checkIsCutoff(cutoff);
1138        }
1139        if (!best || best->objectiveValue() >= cutoff) {
1140#ifdef JJF_ZERO
1141            // take off
1142            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1143            nodes_.pop_back();
1144            delete best;
1145            best = NULL;
1146#else
1147// let code get rid of it
1148assert (best);
1149#endif
1150        }
1151    }
1152    // switched off for now
1153    if (best && comparison_.test_->fullScan() && false) {
1154        CbcNode * saveBest = best;
1155        int n = nodes_.size();
1156        int iBest = -1;
1157        for (int i = 0; i < n; i++) {
1158            // temp
1159            assert (nodes_[i]);
1160            assert (nodes_[i]->nodeInfo());
1161            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
1162                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
1163            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
1164                    && comparison_.alternateTest(best, nodes_[i])) {
1165                best = nodes_[i];
1166                iBest = i;
1167            }
1168        }
1169        if (best == saveBest) {
1170            // can pop
1171            // take off
1172            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1173            nodes_.pop_back();
1174        } else {
1175            // make impossible
1176            nodes_[iBest] = NULL;
1177        }
1178    } else if (best) {
1179        // take off
1180#ifdef JJF_ZERO
1181        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1182        nodes_.pop_back();
1183#else
1184realpop();
1185#endif
1186    }
1187#ifdef DEBUG_CBC_HEAP
1188    if (best) {
1189        int n = nodes_.size();
1190        bool good = true;
1191        for (int i = 0; i < n; i++) {
1192            // temp
1193            assert (nodes_[i]);
1194            if (!comparison_.compareNodes(nodes_[i], best)) {
1195                good = false;
1196                CbcNode * x = nodes_[i];
1197                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
1198                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
1199                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
1200            }
1201        }
1202        if (!good) {
1203            // compare best to all
1204            int i;
1205            for (i = 0; i < n; i++) {
1206                CbcNode * x = nodes_[i];
1207                printf("i=%d x is nun %d depth %d obj %g", i,
1208                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
1209                if (!comparison_.compareNodes(x, best)) {
1210                    printf(" - best is worse!\n");
1211                } else {
1212                    printf("\n");
1213                }
1214            }
1215            // Now compare amongst rest
1216            for (i = 0; i < n; i++) {
1217                CbcNode * x = nodes_[i];
1218                printf("For i=%d ", i);
1219                for (int j = i + 1; j < n; j++) {
1220                    CbcNode * y = nodes_[j];
1221                    if (!comparison_.compareNodes(x, y)) {
1222                        printf(" b %d", j);
1223                    } else {
1224                        printf(" w %d", j);
1225                    }
1226                }
1227                printf("\n");
1228            }
1229            assert(good);
1230        }
1231    }
1232#endif
1233    if (best)
1234        best->setOnTree(false);
1235    return best;
1236}
1237
1238/*! \brief Prune the tree using an objective function cutoff
1239
1240  This routine removes all nodes with objective worst than the
1241  specified cutoff value.
1242*/
1243
1244void
1245CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1246{
1247    int j;
1248    int nNodes = nodes_.size();
1249    CbcNode ** nodeArray = new CbcNode * [nNodes];
1250    int * depth = new int [nNodes];
1251    int k = 0;
1252    int kDelete = nNodes;
1253    bestPossibleObjective = 1.0e100 ;
1254    /*
1255        Destructively scan the heap. Nodes to be retained go into the front of
1256        nodeArray, nodes to be deleted into the back. Store the depth in a
1257        correlated array for nodes to be deleted.
1258    */
1259    for (j = 0; j < nNodes; j++) {
1260        CbcNode * node = top();
1261        pop();
1262        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1263        if (node && value >= cutoff) {
1264            // double check in case node can change its mind!
1265            value = node->checkIsCutoff(cutoff);
1266        }
1267        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1268        if (value >= cutoff) {
1269            if (node) {
1270                nodeArray[--kDelete] = node;
1271                depth[kDelete] = node->depth();
1272            }
1273        } else {
1274            nodeArray[k++] = node;
1275        }
1276    }
1277    /*
1278      Rebuild the heap using the retained nodes.
1279    */
1280    for (j = 0; j < k; j++) {
1281        push(nodeArray[j]);
1282    }
1283    /*
1284      Sort the list of nodes to be deleted, nondecreasing.
1285    */
1286    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
1287    /*
1288      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1289      just a preparatory step. When it returns, the following will be true:
1290        * all cuts are removed from the solver's copy of the constraint system;
1291        * lastws will be a basis appropriate for the specified node;
1292        * variable bounds will be adjusted to be appropriate for the specified
1293          node;
1294        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1295          should be added to the constraint system at this node (but they have
1296          not actually been added).
1297      Then we scan the cut list for the node. Decrement the reference count
1298      for the cut, and if it's gone to 0, really delete it.
1299
1300      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1301      are necessary. When reconstructing a node, these checks are used to skip
1302      over loose cuts, excluding them from the reconstituted basis. But here
1303      we're just interested in correcting the reference count. Tight/loose
1304      should make no difference.
1305
1306      Arguably a separate routine should be used in place of addCuts1. It's
1307      doing more work than needed, modifying the model to match a subproblem
1308      at a node that will be discarded.  Then again, we seem to need the basis.
1309    */
1310    for (j = nNodes - 1; j >= kDelete; j--) {
1311        CbcNode * node = nodeArray[j];
1312        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1313
1314        model->addCuts1(node, lastws);
1315        // Decrement cut counts
1316        assert (node);
1317        //assert (node->nodeInfo());
1318        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1319        int i;
1320        for (i = 0; i < model->currentNumberCuts(); i++) {
1321            // take off node
1322            CoinWarmStartBasis::Status status =
1323                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1324            if (status != CoinWarmStartBasis::basic &&
1325                    model->addedCuts()[i]) {
1326                if (!model->addedCuts()[i]->decrement(numberLeft))
1327                    delete model->addedCuts()[i];
1328            }
1329        }
1330        // node should not have anything pointing to it
1331        if (node->nodeInfo())
1332            node->nodeInfo()->throwAway();
1333        delete node ;
1334        delete lastws ;
1335    }
1336    delete [] nodeArray;
1337    delete [] depth;
1338}
1339
1340// Return the best node of the heap using alternate criterion
1341CbcNode *
1342CbcTree::bestAlternate()
1343{
1344    int n = nodes_.size();
1345    CbcNode * best = NULL;
1346    if (n) {
1347        best = nodes_[0];
1348        for (int i = 1; i < n; i++) {
1349            if (comparison_.alternateTest(best, nodes_[i])) {
1350                best = nodes_[i];
1351            }
1352        }
1353    }
1354    return best;
1355}
1356void
1357CbcTree::realpop()
1358{
1359    if (nodes_.size() > 0) {
1360        nodes_[0] = nodes_.back();
1361        nodes_.pop_back();
1362        fixTop();
1363    }
1364    assert (nodes_.size() >= 0);
1365}
1366/* After changing data in the top node, fix the heap */
1367void
1368CbcTree::fixTop()
1369{
1370    const int size = nodes_.size();
1371    if (size > 1) {
1372        CbcNode** candidates = &nodes_[0];
1373        CbcNode* s = candidates[0];
1374        --candidates;
1375        int pos = 1;
1376        int ch;
1377        for (ch = 2; ch < size; pos = ch, ch *= 2) {
1378            if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1379                ++ch;
1380            if (!comparison_.compareNodes(s, candidates[ch]))
1381                break;
1382            candidates[pos] = candidates[ch];
1383        }
1384        if (ch == size) {
1385            if (!comparison_.compareNodes(candidates[ch], s)) {
1386                candidates[pos] = candidates[ch];
1387                pos = ch;
1388            }
1389        }
1390        candidates[pos] = s;
1391    }
1392}
1393void
1394CbcTree::realpush(CbcNode * node)
1395{
1396    node->setOnTree(true);
1397    nodes_.push_back(node);
1398    CbcNode** candidates = &nodes_[0];
1399    --candidates;
1400    int pos = nodes_.size();
1401    int ch;
1402    for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
1403        if (!comparison_.compareNodes(candidates[ch], node))
1404            break;
1405        candidates[pos] = candidates[ch];
1406    }
1407    candidates[pos] = node;
1408}
1409#endif
1410
1411double
1412CbcTree::getBestPossibleObjective()
1413{
1414    double r_val = 1e100;
1415    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
1416        if (nodes_[i] && nodes_[i]->objectiveValue() < r_val) {
1417            r_val = nodes_[i]->objectiveValue();
1418        }
1419    }
1420    return r_val;
1421}
1422
Note: See TracBrowser for help on using the repository browser.