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

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

fix bug with cbc threads

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 48.3 KB
RevLine 
[1271]1/* $Id: CbcTree.cpp 2022 2014-03-25 11:18:50Z forrest $ */
[2]2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
[1573]4// This code is licensed under the terms of the Eclipse Public License (EPL).
[2]5
6#include "CbcModel.hpp"
7#include "CbcNode.hpp"
8#include "CbcTree.hpp"
[2022]9#include "CbcThread.hpp"
[2]10#include "CbcCountRowCut.hpp"
[724]11#include "CbcCompareActual.hpp"
[940]12#include "CbcBranchActual.hpp"
[2]13
[1506]14
15#if CBC_DEBUG_HEAP > 0
16
17namespace {
18
19
20/*
[1573]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.
[1506]24*/
25/*
[1573]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.
[1506]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/*
[1573]47  Check for the heap property: the parent is better than or equal to
48  either child.
[1506]49
[1573]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.
[1506]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
[1573]89        << " Invalid heap[" << curNdx << "] (left child null entry)!"
90        << std::endl ;
[1506]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
[1573]98          << ") unsat " << node->numberUnsatisfied() << ", depth "
99          << node->depth() << ", obj " << node->objectiveValue() << "."
100          << std::endl ;
[1506]101        node = *child ;
102        std::cout
103          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
[1573]104          << ") unsat " << node->numberUnsatisfied() << ", depth "
105          << node->depth() << ", obj " << node->objectiveValue() << "."
106          << std::endl ;
[1506]107      }
108    }
109    curNode++ ;
110    curNdx++ ;
111    if (curNode == lastNode) break ;
112    if (*curNode == 0) {
113      std::cout
[1573]114        << " Invalid heap[" << curNdx << "] (right child null entry)!"
115        << std::endl ;
[1506]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
[1573]123          << ") unsat " << node->numberUnsatisfied() << ", depth "
124          << node->depth() << ", obj " << node->objectiveValue() << "."
125          << std::endl ;
[1506]126        node = *child ;
127        std::cout
128          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
[1573]129          << ") unsat " << node->numberUnsatisfied() << ", depth "
130          << node->depth() << ", obj " << node->objectiveValue() << "."
131          << std::endl ;
[1506]132      }
133    }
134  }
[1573]135  return ;
[1506]136}
137   
138
139#endif // CBC_DEBUG_HEAP
140
141
[2]142CbcTree::CbcTree()
143{
[1286]144    maximumNodeNumber_ = 0;
145    numberBranching_ = 0;
146    maximumBranching_ = 0;
147    branched_ = NULL;
148    newBound_ = NULL;
[2]149}
150CbcTree::~CbcTree()
151{
[1286]152    delete [] branched_;
153    delete [] newBound_;
[2]154}
[1286]155// Copy constructor
[2]156CbcTree::CbcTree ( const CbcTree & rhs)
157{
[1286]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    }
[2]169}
[1286]170// Assignment operator
[2]171CbcTree &
172CbcTree::operator=(const CbcTree & rhs)
173{
[1286]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        }
[940]188    }
[1286]189    return *this;
[2]190}
[1506]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
[940]207// Adds branching information to complete state
[1286]208void
[940]209CbcTree::addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
[1286]210                                 const double * currentLower,
211                                 const double * currentUpper)
[940]212{
[1286]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;
[1053]234#ifndef NDEBUG
[1286]235                    double value = newBounds[i];
236                    if ((jColumn&0x80000000) == 0) {
237                        assert (value == up[0]);
238                    } else {
239                        assert (value == down[1]);
240                    }
[1053]241#endif
[1286]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        }
[940]290    } else {
[1286]291        // switch off
292        delete [] branched_;
293        delete [] newBound_;
294        maximumBranching_ = -1;
295        branched_ = NULL;
296        newBound_ = NULL;
[940]297    }
298}
299// Increase space for data
[1286]300void
[940]301CbcTree::increaseSpace()
302{
[1286]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;
[940]311}
[2]312// Clone
313CbcTree *
314CbcTree::clone() const
315{
[1286]316    return new CbcTree(*this);
[2]317}
[1506]318
[1286]319#ifndef CBC_DUBIOUS_HEAP
[1506]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*/
[1286]330void
[2]331CbcTree::setComparison(CbcCompareBase  &compare)
332{
[1506]333#   if CBC_DEBUG_HEAP > 1
334    std::cout << "  HEAP: resetting comparison predicate." << std::endl ;
335#   endif
[1286]336    comparison_.test_ = &compare;
[1506]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);
[1315]347    if (compareD) {
348        // clean up diving
349        compareD->cleanDive();
350    }
[1506]351    rebuild() ;
[2]352}
353
[1286]354// Return the top node of the heap
355CbcNode *
[640]356CbcTree::top() const
357{
[1286]358    return nodes_.front();
[2]359}
360
361// Add a node to the heap
[1286]362void
363CbcTree::push(CbcNode * x)
364{
365    x->setNodeNumber(maximumNodeNumber_);
[1943]366    lastObjective_ = x->objectiveValue();
367    lastDepth_ = x->depth();
368    lastUnsatisfied_ = x->numberUnsatisfied();
[1286]369    maximumNodeNumber_++;
[1506]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
[1286]384    x->setOnTree(true);
385    nodes_.push_back(x);
386    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
[1506]387#   if CBC_DEBUG_HEAP > 0
388    validateHeap() ;
389#   endif
[2]390}
391
392// Remove the top node from the heap
[1286]393void
394CbcTree::pop()
395{
[1506]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
[1286]412    nodes_.front()->setOnTree(false);
413    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
414    nodes_.pop_back();
[1506]415
416#   if CBC_DEBUG_HEAP > 0
417    validateHeap() ;
418#   endif
419
[2]420}
421
422// Test if empty *** note may be overridden
[1286]423bool
424CbcTree::empty()
425{
426    return nodes_.empty();
[2]427}
[1506]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*/
[1286]441CbcNode *
[135]442CbcTree::bestNode(double cutoff)
443{
[1506]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*/
[1286]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) {
[1393]466#ifdef JJF_ZERO
[1286]467            // take off
468            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
469            nodes_.pop_back();
470            delete best;
471            best = NULL;
[687]472#else
[1286]473            // let code get rid of it
474            assert (best);
[687]475#endif
[1286]476        }
[135]477    }
[1506]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()) {
[1286]488        CbcNode * saveBest = best;
[1506]489        size_t n = nodes_.size();
490        size_t iBest = -1;
491        for (size_t i = 0; i < n; i++) {
[1286]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) {
[1506]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
[1286]525        // take off
526        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
527        nodes_.pop_back();
[135]528    }
[1506]529#if CBC_DEBUG_HEAP > 0
530    validateHeap() ;
[724]531#endif
[1286]532    if (best)
533        best->setOnTree(false);
534    return best;
[135]535}
[2]536/*! \brief Prune the tree using an objective function cutoff
537
[1506]538  This routine removes all nodes with objective worse than the
[2]539  specified cutoff value.
540*/
541
[1286]542void
[54]543CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
[2]544{
[1506]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
[1286]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) {
[1943]573                if (cutoff<-1.0e30)
574                  node->nodeInfo()->deactivate(7);
[1286]575                nodeArray[--kDelete] = node;
576                depth[kDelete] = node->depth();
577            }
578        } else {
579            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
580            nodeArray[k++] = node;
581        }
[931]582    }
[1286]583    /*
584      Rebuild the heap using the retained nodes.
585    */
586    for (j = 0; j < k; j++) {
587        push(nodeArray[j]);
[2]588    }
[1506]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
[1286]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.
[2]611
[1286]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
[1573]615      we're just interested in correcting the reference count. Tight/loose
616      should make no difference.
[2]617
[1573]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.
[1286]621    */
622    for (j = nNodes - 1; j >= kDelete; j--) {
623        CbcNode * node = nodeArray[j];
[1951]624        CoinWarmStartBasis *lastws = (cutoff!=-COIN_DBL_MAX) ? model->getEmptyBasis() : NULL;
[1286]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;
[1951]631        if (cutoff != -COIN_DBL_MAX) {
632          // normal
633          for (int i = 0; i < model->currentNumberCuts(); i++) {
[1286]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            }
[1951]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->addedCuts()[i]->decrement(numberLeft))
649                    delete model->addedCuts()[i];
650            }
651          }
652        }
[1286]653        // node should not have anything pointing to it
654        if (node->nodeInfo())
655            node->nodeInfo()->throwAway();
656        delete node ;
657        delete lastws ;
[2]658    }
[1286]659    delete [] nodeArray;
660    delete [] depth;
[2022]661#ifdef CBC_THREAD
662    if (model->parallelMode() > 0 && model->master()) {
663      // need to adjust for ones not on tree
664      CbcBaseModel * master = model->master();
665      int numberThreads = master->numberThreads();
666      for (int i=0;i<numberThreads;i++) {
667        CbcThread * child = master->child(i);
668        if (child->node()) {
669          double value = child->node()->objectiveValue();
670          // adjust
671          bestPossibleObjective = CoinMin(bestPossibleObjective, value);
672        }
673      }
674    }
675#endif
[317]676}
[2]677
[135]678// Return the best node of the heap using alternate criterion
[1286]679CbcNode *
680CbcTree::bestAlternate()
681{
[1506]682    size_t n = nodes_.size();
[1286]683    CbcNode * best = NULL;
684    if (n) {
685        best = nodes_[0];
[1506]686        for (size_t i = 1; i < n; i++) {
[1286]687            if (comparison_.alternateTest(best, nodes_[i])) {
688                best = nodes_[i];
689            }
690        }
[135]691    }
[1286]692    return best;
[135]693}
[1342]694
[1506]695#ifdef JJF_ZERO // not used, reference removed in CbcModel.cpp
[1132]696CbcTreeArray::CbcTreeArray()
[1286]697        : CbcTree(),
698        lastNode_(NULL),
699        lastNodePopped_(NULL),
700        switches_(0)
[1132]701{
702}
703CbcTreeArray::~CbcTreeArray()
704{
705}
[1286]706// Copy constructor
[1132]707CbcTreeArray::CbcTreeArray ( const CbcTreeArray & rhs)
[1286]708        : CbcTree(rhs),
709        lastNode_(rhs.lastNode_),
710        lastNodePopped_(rhs.lastNodePopped_),
711        switches_(rhs.switches_)
[1132]712{
713}
[1286]714// Assignment operator
[1132]715CbcTreeArray &
716CbcTreeArray::operator=(const CbcTreeArray & rhs)
717{
[1286]718    if (this != &rhs) {
719        CbcTree::operator=(rhs);
720        lastNode_ = rhs.lastNode_;
721        lastNodePopped_ = rhs.lastNodePopped_;
722        switches_ = rhs.switches_;
723    }
724    return *this;
[1132]725}
726// Clone
727CbcTree *
728CbcTreeArray::clone() const
729{
[1286]730    return new CbcTreeArray(*this);
[1132]731}
732// Set comparison function and resort heap
[1286]733void
[1132]734CbcTreeArray::setComparison(CbcCompareBase  &compare)
735{
[1286]736    comparison_.test_ = &compare;
[1506]737    rebuild() ;
[1132]738}
739
740// Add a node to the heap
[1286]741void
742CbcTreeArray::push(CbcNode * x)
743{
744    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
745       x->objectiveValue(),x->nodeInfo()->decrement(0),
746       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
747    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
748    x->setOnTree(true);
749    if (lastNode_) {
750        if (lastNode_->nodeInfo()->parent() == x->nodeInfo()) {
751            // x is parent of lastNode_ so put x on heap
752            //#define CBCTREE_PRINT
[1132]753#ifdef CBCTREE_PRINT
[1286]754            printf("pushX x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
755                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
756                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
[1132]757#endif
[1286]758            nodes_.push_back(x);
759        } else {
760            x->setNodeNumber(maximumNodeNumber_);
761            maximumNodeNumber_++;
[1132]762#ifdef CBCTREE_PRINT
[1286]763            printf("pushLast x %x (%x at depth %d n %d) is parent of lastNode_ %x (%x at depth %d n %d)\n",
764                   x, x->nodeInfo(), x->depth(), x->nodeNumber(),
765                   lastNode_, lastNode_->nodeInfo(), lastNode_->depth(), lastNode_->nodeNumber());
[1132]766#endif
[1286]767            nodes_.push_back(lastNode_);
768            lastNode_ = x;
769        }
770        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
771    } else {
772        x->setNodeNumber(maximumNodeNumber_);
773        maximumNodeNumber_++;
774        if (x != lastNodePopped_) {
775            lastNode_ = x;
[1132]776#ifdef CBCTREE_PRINT
[1286]777            printf("pushNULL x %x (%x at depth %d n %d)\n",
778                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
[1132]779#endif
[1286]780        } else {
781            // means other way was infeasible
[1132]782#ifdef CBCTREE_PRINT
[1286]783            printf("push_other_infeasible x %x (%x at depth %d n %d)\n",
784                   x, x->nodeInfo(), x->depth(), x->nodeNumber());
[1132]785#endif
[1286]786            nodes_.push_back(x);
787            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
788        }
[1132]789    }
790}
791
792// Test if empty *** note may be overridden
[1286]793bool
794CbcTreeArray::empty()
795{
796    return nodes_.empty() && (lastNode_ == NULL);
[1132]797}
798// Gets best node and takes off heap
[1286]799CbcNode *
[1132]800CbcTreeArray::bestNode(double cutoff)
801{
[1286]802    CbcNode * best = NULL;
803    // See if we want last node or best on heap
804    if (lastNode_) {
[1132]805#ifdef CBCTREE_PRINT
[1286]806        printf("Best lastNode_ %x (%x at depth %d) - nodeNumber %d obj %g\n",
807               lastNode_, lastNode_->nodeInfo(), lastNode_->depth(),
808               lastNode_->nodeNumber(), lastNode_->objectiveValue());
[1132]809#endif
[1286]810        assert (lastNode_->onTree());
811        int nodeNumber = lastNode_->nodeNumber();
812        bool useLastNode = false;
813        if (nodeNumber + 1 == maximumNodeNumber_) {
814            // diving - look further
815            CbcCompareDefault * compareDefault
816            = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
817            assert (compareDefault);
818            double bestPossible = compareDefault->getBestPossible();
819            double cutoff = compareDefault->getCutoff();
820            double objValue = lastNode_->objectiveValue();
821            if (cutoff < 1.0e20) {
822                if (objValue - bestPossible < 0.999*(cutoff - bestPossible))
823                    useLastNode = true;
824            } else {
825                useLastNode = true;
826            }
827        }
828        if (useLastNode) {
829            lastNode_->setOnTree(false);
830            best = lastNode_;
831            lastNode_ = NULL;
832            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
833            if (best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
834                assert (best->nodeInfo()->numberBranchesLeft());
835            if (best->objectiveValue() >= cutoff) {
836                // double check in case node can change its mind!
837                best->checkIsCutoff(cutoff);
838            }
839            lastNodePopped_ = best;
840            return best;
841        } else {
842            // put on tree
843            nodes_.push_back(lastNode_);
844            lastNode_->setNodeNumber(maximumNodeNumber_);
845            maximumNodeNumber_++;
846            lastNode_ = NULL;
847            std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
848        }
[1132]849    }
[1286]850    while (!best && nodes_.size()) {
851        best = nodes_.front();
852        if (best)
853            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
854        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
855            assert (best->nodeInfo()->numberBranchesLeft());
856        if (best && best->objectiveValue() >= cutoff) {
857            // double check in case node can change its mind!
858            best->checkIsCutoff(cutoff);
859        }
860        if (!best || best->objectiveValue() >= cutoff) {
861            // let code get rid of it
862            assert (best);
863        }
[1132]864    }
[1286]865    lastNodePopped_ = best;
866#ifdef CBCTREE_PRINT
[1132]867    if (best)
[1286]868        printf("Heap returning node %x (%x at depth %d) - nodeNumber %d - obj %g\n",
869               best, best->nodeInfo(), best->depth(),
870               best->nodeNumber(), best->objectiveValue());
871    else
872        printf("Heap returning Null\n");
873#endif
874    if (best) {
875        // take off
876        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
877        nodes_.pop_back();
[1132]878    }
879#ifdef DEBUG_CBC_HEAP
[1286]880    if (best) {
881        int n = nodes_.size();
882        bool good = true;
883        for (int i = 0; i < n; i++) {
884            // temp
885            assert (nodes_[i]);
886            if (!comparison_.compareNodes(nodes_[i], best)) {
887                good = false;
888                CbcNode * x = nodes_[i];
889                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
890                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
891                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
892            }
893        }
894        if (!good) {
895            // compare best to all
896            int i;
897            for (i = 0; i < n; i++) {
898                CbcNode * x = nodes_[i];
899                printf("i=%d x is nun %d depth %d obj %g", i,
900                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
901                if (!comparison_.compareNodes(x, best)) {
902                    printf(" - best is worse!\n");
903                } else {
904                    printf("\n");
905                }
906            }
907            // Now compare amongst rest
908            for (i = 0; i < n; i++) {
909                CbcNode * x = nodes_[i];
910                printf("For i=%d ", i);
911                for (int j = i + 1; j < n; j++) {
912                    CbcNode * y = nodes_[j];
913                    if (!comparison_.compareNodes(x, y)) {
914                        printf(" b %d", j);
915                    } else {
916                        printf(" w %d", j);
917                    }
918                }
919                printf("\n");
920            }
921            assert(good);
922        }
[1132]923    }
924#endif
[1286]925    if (best)
926        best->setOnTree(false);
927    return best;
[1132]928}
929
930double
[1286]931CbcTreeArray::getBestPossibleObjective()
932{
933    double bestPossibleObjective = 1e100;
934    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
935        if (nodes_[i] && nodes_[i]->objectiveValue() < bestPossibleObjective) {
936            bestPossibleObjective = nodes_[i]->objectiveValue();
937        }
[1132]938    }
[1286]939    if (lastNode_) {
940        bestPossibleObjective = CoinMin(bestPossibleObjective, lastNode_->objectiveValue());
941    }
[2022]942#ifdef CBC_THREAD
943    if (model->parallelMode() > 0 && model->master()) {
944      // need to adjust for ones not on tree
945      CbcBaseModel * master = model->master();
946      int numberThreads = master->numberThreads();
947      for (int i=0;i<numberThreads;i++) {
948        CbcThread * child = master->child(i);
949        if (child->node()) {
950          double value = child->node()->objectiveValue();
951          // adjust
952          bestPossibleObjective = CoinMin(bestPossibleObjective, value);
953        }
954      }
955    }
956#endif
[1286]957    CbcCompareDefault * compareDefault
[1132]958    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
[1286]959    assert (compareDefault);
960    compareDefault->setBestPossible(bestPossibleObjective);
961    return bestPossibleObjective;
[1132]962}
963/*! \brief Prune the tree using an objective function cutoff
964
965  This routine removes all nodes with objective worst than the
966  specified cutoff value.
967*/
968
[1286]969void
[1132]970CbcTreeArray::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
971{
[1286]972    int j;
973    int nNodes = size();
974    int lastNode = nNodes + 1;
975    CbcNode ** nodeArray = new CbcNode * [lastNode];
976    int * depth = new int [lastNode];
977    int k = 0;
978    int kDelete = lastNode;
979    bestPossibleObjective = 1.0e100 ;
980    /*
981        Destructively scan the heap. Nodes to be retained go into the front of
982        nodeArray, nodes to be deleted into the back. Store the depth in a
983        correlated array for nodes to be deleted.
984    */
985    for (j = 0; j < nNodes; j++) {
986        CbcNode * node = nodes_.front();
987        nodes_.front()->setOnTree(false);
988        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
989        nodes_.pop_back();
990        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
991        if (node && value >= cutoff) {
992            // double check in case node can change its mind!
993            value = node->checkIsCutoff(cutoff);
994        }
995        if (value >= cutoff || !node->active()) {
996            if (node) {
997                nodeArray[--kDelete] = node;
998                depth[kDelete] = node->depth();
999            }
1000        } else {
1001            bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1002            nodeArray[k++] = node;
1003        }
[1132]1004    }
[2022]1005#ifdef CBC_THREAD
1006    if (model->parallelMode() > 0 && model->master()) {
1007      // need to adjust for ones not on tree
1008      CbcBaseModel * master = model->master();
1009      int numberThreads = master->numberThreads();
1010      for (int i=0;i<numberThreads;i++) {
1011        CbcThread * child = master->child(i);
1012        if (child->node()) {
1013          double value = child->node()->objectiveValue();
1014          // adjust
1015          bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1016        }
1017      }
1018    }
1019#endif
[1286]1020    if (lastNode_) {
1021        double value = lastNode_->objectiveValue();
1022        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1023        if (value >= cutoff || !lastNode_->active()) {
1024            nodeArray[--kDelete] = lastNode_;
1025            depth[kDelete] = lastNode_->depth();
1026            lastNode_ = NULL;
1027        }
[1132]1028    }
[1286]1029    CbcCompareDefault * compareDefault
1030    = dynamic_cast<CbcCompareDefault *> (comparison_.test_);
1031    assert (compareDefault);
1032    compareDefault->setBestPossible(bestPossibleObjective);
1033    compareDefault->setCutoff(cutoff);
1034    /*
1035      Rebuild the heap using the retained nodes.
1036    */
1037    for (j = 0; j < k; j++) {
1038        CbcNode * node = nodeArray[j];
1039        node->setOnTree(true);
1040        nodes_.push_back(node);
1041        std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
[1132]1042    }
[1286]1043    /*
1044      Sort the list of nodes to be deleted, nondecreasing.
1045    */
1046    CoinSort_2(depth + kDelete, depth + lastNode, nodeArray + kDelete);
1047    /*
1048      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1049      just a preparatory step. When it returns, the following will be true:
1050        * all cuts are removed from the solver's copy of the constraint system;
1051        * lastws will be a basis appropriate for the specified node;
1052        * variable bounds will be adjusted to be appropriate for the specified
1053          node;
1054        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1055          should be added to the constraint system at this node (but they have
1056          not actually been added).
1057      Then we scan the cut list for the node. Decrement the reference count
1058      for the cut, and if it's gone to 0, really delete it.
[1132]1059
[1286]1060      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1061      are necessary. When reconstructing a node, these checks are used to skip
1062      over loose cuts, excluding them from the reconstituted basis. But here
[1573]1063      we're just interested in correcting the reference count. Tight/loose
1064      should make no difference.
[1132]1065
[1573]1066      Arguably a separate routine should be used in place of addCuts1. It's
1067      doing more work than needed, modifying the model to match a subproblem
1068      at a node that will be discarded.  Then again, we seem to need the basis.
[1286]1069    */
1070    for (j = lastNode - 1; j >= kDelete; j--) {
1071        CbcNode * node = nodeArray[j];
1072        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1073
1074        model->addCuts1(node, lastws);
1075        // Decrement cut counts
1076        assert (node);
1077        //assert (node->nodeInfo());
1078        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1079        int i;
1080        for (i = 0; i < model->currentNumberCuts(); i++) {
1081            // take off node
1082            CoinWarmStartBasis::Status status =
1083                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1084            if (status != CoinWarmStartBasis::basic &&
1085                    model->addedCuts()[i]) {
1086                if (!model->addedCuts()[i]->decrement(numberLeft))
1087                    delete model->addedCuts()[i];
1088            }
1089        }
1090        // node should not have anything pointing to it
1091        if (node->nodeInfo())
1092            node->nodeInfo()->throwAway();
1093        delete node ;
1094        delete lastws ;
[1132]1095    }
[1286]1096    delete [] nodeArray;
1097    delete [] depth;
[1132]1098}
[1342]1099#endif
[1506]1100
1101#else  // defined(CBC_DUBIOUS_HEAP)
1102
1103/*
1104  Unclear whether this code is useful any longer. Likely stale. See
1105  note in CbcCompareDefault.hpp re. CBC_DUBIOUS_HEAP.
1106  -- lh, 100921 --
1107*/
1108
[724]1109// Set comparison function and resort heap
[1286]1110void
[724]1111CbcTree::setComparison(CbcCompareBase  &compare)
1112{
[1286]1113    comparison_.test_ = &compare;
1114    std::vector <CbcNode *> newNodes = nodes_;
1115    nodes_.resize(0);
1116    while (newNodes.size() > 0) {
1117        push( newNodes.back());
1118        newNodes.pop_back();
1119    }
[724]1120}
[2]1121
[1286]1122// Return the top node of the heap
1123CbcNode *
[724]1124CbcTree::top() const
1125{
[1286]1126    return nodes_.front();
[724]1127}
1128
1129// Add a node to the heap
[1286]1130void
1131CbcTree::push(CbcNode * x)
1132{
1133    x->setNodeNumber(maximumNodeNumber_);
1134    maximumNodeNumber_++;
1135    /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
1136       x->objectiveValue(),x->nodeInfo()->decrement(0),
1137       x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
1138    assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
[1393]1139#ifdef JJF_ZERO
[1286]1140    nodes_.push_back(x);
1141    push_heap(nodes_.begin(), nodes_.end(), comparison_);
[724]1142#else
[1286]1143realpush(x);
[724]1144#endif
1145}
1146
1147// Remove the top node from the heap
[1286]1148void
1149CbcTree::pop()
1150{
[1393]1151#ifdef JJF_ZERO
[1286]1152    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1153    nodes_.pop_back();
[724]1154#else
[1286]1155if (nodes_.size()) {
[724]1156    //CbcNode* s = nodes_.front();
1157    realpop();
1158    //delete s;
[1286]1159}
1160assert (nodes_.size() >= 0);
[724]1161#endif
1162}
1163
1164// Test if empty *** note may be overridden
[1286]1165bool
1166CbcTree::empty()
1167{
1168    return nodes_.empty();
[724]1169}
1170// Gets best node and takes off heap
[1286]1171CbcNode *
[724]1172CbcTree::bestNode(double cutoff)
1173{
[1286]1174    CbcNode * best = NULL;
1175    while (!best && nodes_.size()) {
1176        best = nodes_.front();
1177        if (best)
1178            assert(best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo());
1179        if (best && best->objectiveValue() != COIN_DBL_MAX && best->nodeInfo())
1180            assert (best->nodeInfo()->numberBranchesLeft());
1181        if (best && best->objectiveValue() >= cutoff) {
1182            // double check in case node can change its mind!
1183            best->checkIsCutoff(cutoff);
1184        }
1185        if (!best || best->objectiveValue() >= cutoff) {
[1393]1186#ifdef JJF_ZERO
[1286]1187            // take off
1188            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1189            nodes_.pop_back();
1190            delete best;
1191            best = NULL;
[724]1192#else
[1286]1193// let code get rid of it
1194assert (best);
[724]1195#endif
[1286]1196        }
[724]1197    }
[1286]1198    // switched off for now
1199    if (best && comparison_.test_->fullScan() && false) {
1200        CbcNode * saveBest = best;
1201        int n = nodes_.size();
1202        int iBest = -1;
1203        for (int i = 0; i < n; i++) {
1204            // temp
1205            assert (nodes_[i]);
1206            assert (nodes_[i]->nodeInfo());
1207            if (nodes_[i] && nodes_[i]->objectiveValue() != COIN_DBL_MAX && nodes_[i]->nodeInfo())
1208                assert (nodes_[i]->nodeInfo()->numberBranchesLeft());
1209            if (nodes_[i] && nodes_[i]->objectiveValue() < cutoff
1210                    && comparison_.alternateTest(best, nodes_[i])) {
1211                best = nodes_[i];
1212                iBest = i;
1213            }
1214        }
1215        if (best == saveBest) {
1216            // can pop
1217            // take off
1218            std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1219            nodes_.pop_back();
1220        } else {
1221            // make impossible
1222            nodes_[iBest] = NULL;
1223        }
1224    } else if (best) {
1225        // take off
[1393]1226#ifdef JJF_ZERO
[1286]1227        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
1228        nodes_.pop_back();
[724]1229#else
[1286]1230realpop();
[724]1231#endif
[1286]1232    }
[724]1233#ifdef DEBUG_CBC_HEAP
[1286]1234    if (best) {
1235        int n = nodes_.size();
1236        bool good = true;
1237        for (int i = 0; i < n; i++) {
1238            // temp
1239            assert (nodes_[i]);
1240            if (!comparison_.compareNodes(nodes_[i], best)) {
1241                good = false;
1242                CbcNode * x = nodes_[i];
1243                printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
1244                       x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
1245                       best->numberUnsatisfied(), best->depth(), best->objectiveValue());
1246            }
1247        }
1248        if (!good) {
1249            // compare best to all
1250            int i;
1251            for (i = 0; i < n; i++) {
1252                CbcNode * x = nodes_[i];
1253                printf("i=%d x is nun %d depth %d obj %g", i,
1254                       x->numberUnsatisfied(), x->depth(), x->objectiveValue());
1255                if (!comparison_.compareNodes(x, best)) {
1256                    printf(" - best is worse!\n");
1257                } else {
1258                    printf("\n");
1259                }
1260            }
1261            // Now compare amongst rest
1262            for (i = 0; i < n; i++) {
1263                CbcNode * x = nodes_[i];
1264                printf("For i=%d ", i);
1265                for (int j = i + 1; j < n; j++) {
1266                    CbcNode * y = nodes_[j];
1267                    if (!comparison_.compareNodes(x, y)) {
1268                        printf(" b %d", j);
1269                    } else {
1270                        printf(" w %d", j);
1271                    }
1272                }
1273                printf("\n");
1274            }
1275            assert(good);
1276        }
[724]1277    }
1278#endif
[1286]1279    if (best)
1280        best->setOnTree(false);
1281    return best;
[724]1282}
1283
1284/*! \brief Prune the tree using an objective function cutoff
1285
1286  This routine removes all nodes with objective worst than the
1287  specified cutoff value.
1288*/
1289
[1286]1290void
[724]1291CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
1292{
[1286]1293    int j;
1294    int nNodes = nodes_.size();
1295    CbcNode ** nodeArray = new CbcNode * [nNodes];
1296    int * depth = new int [nNodes];
1297    int k = 0;
1298    int kDelete = nNodes;
1299    bestPossibleObjective = 1.0e100 ;
1300    /*
1301        Destructively scan the heap. Nodes to be retained go into the front of
1302        nodeArray, nodes to be deleted into the back. Store the depth in a
1303        correlated array for nodes to be deleted.
1304    */
1305    for (j = 0; j < nNodes; j++) {
1306        CbcNode * node = top();
1307        pop();
1308        double value = node ? node->objectiveValue() : COIN_DBL_MAX;
1309        if (node && value >= cutoff) {
1310            // double check in case node can change its mind!
1311            value = node->checkIsCutoff(cutoff);
1312        }
1313        bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1314        if (value >= cutoff) {
1315            if (node) {
1316                nodeArray[--kDelete] = node;
1317                depth[kDelete] = node->depth();
1318            }
1319        } else {
1320            nodeArray[k++] = node;
1321        }
[931]1322    }
[2022]1323#ifdef CBC_THREAD
1324    if (model->parallelMode() > 0 && model->master()) {
1325      // need to adjust for ones not on tree
1326      CbcBaseModel * master = model->master();
1327      int numberThreads = master->numberThreads();
1328      for (int i=0;i<numberThreads;i++) {
1329        CbcThread * child = master->child(i);
1330        if (child->node()) {
1331          double value = child->node()->objectiveValue();
1332          // adjust
1333          bestPossibleObjective = CoinMin(bestPossibleObjective, value);
1334        }
1335      }
1336    }
1337#endif
[1286]1338    /*
1339      Rebuild the heap using the retained nodes.
1340    */
1341    for (j = 0; j < k; j++) {
1342        push(nodeArray[j]);
[724]1343    }
[1286]1344    /*
1345      Sort the list of nodes to be deleted, nondecreasing.
1346    */
1347    CoinSort_2(depth + kDelete, depth + nNodes, nodeArray + kDelete);
1348    /*
1349      Work back from deepest to shallowest. In spite of the name, addCuts1 is
1350      just a preparatory step. When it returns, the following will be true:
1351        * all cuts are removed from the solver's copy of the constraint system;
1352        * lastws will be a basis appropriate for the specified node;
1353        * variable bounds will be adjusted to be appropriate for the specified
1354          node;
1355        * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
1356          should be added to the constraint system at this node (but they have
1357          not actually been added).
1358      Then we scan the cut list for the node. Decrement the reference count
1359      for the cut, and if it's gone to 0, really delete it.
[724]1360
[1286]1361      I don't yet see why the checks for status != basic and addedCuts_[i] != 0
1362      are necessary. When reconstructing a node, these checks are used to skip
1363      over loose cuts, excluding them from the reconstituted basis. But here
[1573]1364      we're just interested in correcting the reference count. Tight/loose
1365      should make no difference.
[724]1366
[1573]1367      Arguably a separate routine should be used in place of addCuts1. It's
1368      doing more work than needed, modifying the model to match a subproblem
1369      at a node that will be discarded.  Then again, we seem to need the basis.
[1286]1370    */
1371    for (j = nNodes - 1; j >= kDelete; j--) {
1372        CbcNode * node = nodeArray[j];
1373        CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
1374
1375        model->addCuts1(node, lastws);
1376        // Decrement cut counts
1377        assert (node);
1378        //assert (node->nodeInfo());
1379        int numberLeft = (node->nodeInfo()) ? node->nodeInfo()->numberBranchesLeft() : 0;
1380        int i;
1381        for (i = 0; i < model->currentNumberCuts(); i++) {
1382            // take off node
1383            CoinWarmStartBasis::Status status =
1384                lastws->getArtifStatus(i + model->numberRowsAtContinuous());
1385            if (status != CoinWarmStartBasis::basic &&
1386                    model->addedCuts()[i]) {
1387                if (!model->addedCuts()[i]->decrement(numberLeft))
1388                    delete model->addedCuts()[i];
1389            }
1390        }
1391        // node should not have anything pointing to it
1392        if (node->nodeInfo())
1393            node->nodeInfo()->throwAway();
1394        delete node ;
1395        delete lastws ;
[724]1396    }
[1286]1397    delete [] nodeArray;
1398    delete [] depth;
[724]1399}
1400
1401// Return the best node of the heap using alternate criterion
[1286]1402CbcNode *
1403CbcTree::bestAlternate()
1404{
1405    int n = nodes_.size();
1406    CbcNode * best = NULL;
1407    if (n) {
1408        best = nodes_[0];
1409        for (int i = 1; i < n; i++) {
1410            if (comparison_.alternateTest(best, nodes_[i])) {
1411                best = nodes_[i];
1412            }
1413        }
[724]1414    }
[1286]1415    return best;
[724]1416}
[1286]1417void
1418CbcTree::realpop()
1419{
1420    if (nodes_.size() > 0) {
1421        nodes_[0] = nodes_.back();
1422        nodes_.pop_back();
1423        fixTop();
1424    }
1425    assert (nodes_.size() >= 0);
[724]1426}
1427/* After changing data in the top node, fix the heap */
[1286]1428void
1429CbcTree::fixTop()
1430{
1431    const int size = nodes_.size();
1432    if (size > 1) {
1433        CbcNode** candidates = &nodes_[0];
1434        CbcNode* s = candidates[0];
1435        --candidates;
1436        int pos = 1;
1437        int ch;
1438        for (ch = 2; ch < size; pos = ch, ch *= 2) {
1439            if (!comparison_.compareNodes(candidates[ch+1], candidates[ch]))
1440                ++ch;
1441            if (!comparison_.compareNodes(s, candidates[ch]))
1442                break;
1443            candidates[pos] = candidates[ch];
1444        }
1445        if (ch == size) {
1446            if (!comparison_.compareNodes(candidates[ch], s)) {
1447                candidates[pos] = candidates[ch];
1448                pos = ch;
1449            }
1450        }
1451        candidates[pos] = s;
1452    }
1453}
1454void
1455CbcTree::realpush(CbcNode * node)
1456{
1457    node->setOnTree(true);
1458    nodes_.push_back(node);
[724]1459    CbcNode** candidates = &nodes_[0];
1460    --candidates;
[1286]1461    int pos = nodes_.size();
[724]1462    int ch;
[1286]1463    for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
1464        if (!comparison_.compareNodes(candidates[ch], node))
1465            break;
1466        candidates[pos] = candidates[ch];
[724]1467    }
[1286]1468    candidates[pos] = node;
[724]1469}
1470#endif
[1432]1471
[1813]1472double
1473CbcTree::getBestPossibleObjective()
1474{
1475    double r_val = 1e100;
1476    for (int i = 0 ; i < static_cast<int> (nodes_.size()) ; i++) {
1477        if (nodes_[i] && nodes_[i]->objectiveValue() < r_val) {
1478            r_val = nodes_[i]->objectiveValue();
1479        }
1480    }
1481    return r_val;
1482}
1483
Note: See TracBrowser for help on using the repository browser.