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

Last change on this file since 2094 was 2094, checked in by forrest, 5 years ago

for memory leaks and heuristics and some experimental stuff

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