source: stable/2.8/Cbc/src/CbcTree.cpp @ 2023

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

fix thread bug

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