Changeset 1506 for trunk/Cbc


Ignore:
Timestamp:
Sep 27, 2010 12:55:11 PM (9 years ago)
Author:
lou
Message:

Fix `Invalid heap' error in cl debug builds. Add validateHeap method to CbcTree? for future debugging.

Location:
trunk/Cbc/src
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcCompareBase.hpp

    r1400 r1506  
    3131    }
    3232
    33     // This allows any method to change behavior as it is called
    34     // after each solution
    35     virtual void newSolution(CbcModel * ) {}
     33    /*! \brief Reconsider behaviour after discovering a new solution.
     34   
     35      This allows any method to change its behaviour. It is called
     36      after each solution.
    3637
    37     // This Also allows any method to change behavior as it is called
    38     // after each solution
    39     virtual void newSolution(CbcModel * ,
     38      The method should return true if changes are made which will
     39      alter the evaluation criteria applied to a node. (So that in
     40      cases where the search tree is sorted, it can be properly
     41      rebuilt.)
     42    */
     43    virtual bool newSolution(CbcModel * ) { return (false) ; }
     44
     45    /*! \brief Reconsider behaviour after discovering a new solution.
     46   
     47      This allows any method to change its behaviour. It is called
     48      after each solution.
     49
     50      The method should return true if changes are made which will
     51      alter the evaluation criteria applied to a node. (So that in
     52      cases where the search tree is sorted, it can be properly
     53      rebuilt.)
     54    */
     55    virtual bool newSolution(CbcModel * ,
    4056                             double ,
    41                              int ) {}
     57                             int ) { return (false) ; }
    4258
    4359    // This allows any method to change behavior as it is called
  • trunk/Cbc/src/CbcCompareDefault.cpp

    r1393 r1506  
    2929        breadthDepth_(5),
    3030        startNodeNumber_(-1),
    31         afterNodeNumber_(-1)
     31        afterNodeNumber_(-1),
     32        setupForDiving_(false)
    3233{
    3334    test_ = this;
     
    4546        breadthDepth_(5),
    4647        startNodeNumber_(-1),
    47         afterNodeNumber_(-1)
     48        afterNodeNumber_(-1),
     49        setupForDiving_(false)
    4850{
    4951    test_ = this;
     
    6567    startNodeNumber_ = rhs.startNodeNumber_;
    6668    afterNodeNumber_ = rhs.afterNodeNumber_;
     69    setupForDiving_ = rhs.setupForDiving_ ;
    6770}
    6871
     
    8992        startNodeNumber_ = rhs.startNodeNumber_;
    9093        afterNodeNumber_ = rhs.afterNodeNumber_;
     94        setupForDiving_ = rhs.setupForDiving_ ;
    9195    }
    9296    return *this;
     
    203207    }
    204208}
    205 // This allows method to change behavior as it is called
    206 // after each solution
    207 void
     209/*
     210  Change the weight attached to unsatisfied integer variables, unless it's
     211  fairly early on in the search and all solutions to date are heuristic.
     212*/
     213bool
    208214CbcCompareDefault::newSolution(CbcModel * model,
    209215                               double objectiveAtContinuous,
     
    213219    if (model->getSolutionCount() == model->getNumberHeuristicSolutions() &&
    214220            model->getSolutionCount() < 5 && model->getNodeCount() < 500)
    215         return; // solution was got by rounding
     221        return (false) ; // solution was got by rounding
    216222    // set to get close to this solution
    217223    double costPerInteger =
     
    223229    //if (numberSolutions_>5)
    224230    //weight_ =0.0; // this searches on objective
     231    return (true) ;
    225232}
    226233// This allows method to change behavior
     
    278285    startNodeNumber_ = best->nodeNumber();
    279286    // send signal to setComparison
    280     afterNodeNumber_ = -2;
     287    setupForDiving_ = true ;
     288    /*
     289      TODO (review when fixing cleanDive and setComparison)
     290      Both afterNodeNumber_ and weight_ must not change
     291      after setComparison is invoked, as that will change
     292      the behaviour of test(). I replaced the overload on
     293      afterNodeNumber_ (magic number -2) with a boolean. Weight_
     294      is more problematic. Either it's correct before calling
     295      setComparison, or it needs to be cut from the tie-breaking
     296      part of test() during a dive, or there needs to be a new
     297      attribute to save and restore it around the dive. Otherwise
     298      heap checks fail in debug builds with Visual Studio.
     299     
     300      Given that weight_ was restored immediately after the call
     301      to setComparison, there should be no change in behaviour
     302      in terms of calls to test().
     303      -- lh, 100921 --
     304    */
     305    afterNodeNumber_ = model->tree()->maximumNodeNumber();
     306    weight_ = saveWeight ;
    281307    // redo tree
    282308    model->tree()->setComparison(*this);
    283     afterNodeNumber_ = model->tree()->maximumNodeNumber();
    284     weight_ = saveWeight;
     309    setupForDiving_ = false ;
    285310}
    286311// Clean up dive
     
    288313CbcCompareDefault::cleanDive()
    289314{
    290     if (afterNodeNumber_ != -2) {
     315    if (setupForDiving_ == false) {
    291316        // switch off
    292317        startNodeNumber_ = -1;
  • trunk/Cbc/src/CbcCompareDefault.hpp

    r1432 r1506  
    4949    /// This allows method to change behavior as it is called
    5050    /// after each solution
    51     virtual void newSolution(CbcModel * model,
     51    virtual bool newSolution(CbcModel * model,
    5252                             double objectiveAtContinuous,
    5353                             int numberInfeasibilitiesAtContinuous) ;
     
    107107    /// Node number when dive started
    108108    int afterNodeNumber_;
     109    /// Indicates doing setup for diving
     110    bool setupForDiving_ ;
    109111};
    110112
  • trunk/Cbc/src/CbcModel.cpp

    r1500 r1506  
    36243624            }
    36253625            lockThread();
    3626             // Do from deepest (clean tree w.r.t. new solution)
    3627             tree_->cleanTree(this, newCutoff, bestPossibleObjective_) ;
    3628             nodeCompare_->newSolution(this) ;
    3629             nodeCompare_->newSolution(this, continuousObjective_,
    3630                                       continuousInfeasibilities_) ;
    3631             // side effect: redo heap
    3632             tree_->setComparison(*nodeCompare_) ;
     3626            /*
     3627              Clean the tree to reflect the new solution, then see if the
     3628              node comparison predicate wants to make any changes. If so,
     3629              call setComparison for the side effect of rebuilding the heap.
     3630            */
     3631            tree_->cleanTree(this,newCutoff,bestPossibleObjective_) ;
     3632            if (nodeCompare_->newSolution(this) ||
     3633                nodeCompare_->newSolution(this,continuousObjective_,
     3634                                          continuousInfeasibilities_)) {
     3635              tree_->setComparison(*nodeCompare_) ;
     3636            }
    36333637            if (tree_->empty()) {
    36343638                continue;
  • trunk/Cbc/src/CbcTree.cpp

    r1432 r1506  
    22// Copyright (C) 2004, International Business Machines
    33// Corporation and others.  All Rights Reserved.
     4
    45
    56#include "CbcModel.hpp"
     
    910#include "CbcCompareActual.hpp"
    1011#include "CbcBranchActual.hpp"
     12
     13
     14#if CBC_DEBUG_HEAP > 0
     15
     16namespace {
     17
     18
     19/*
     20  The next few methods test that the heap property (parent equal or better than either
     21  child) is maintained in the heap. Originally created to sort out why `cbc -unitTest'
     22  triggered an `Invalid heap' error in a MSVS debug build.
     23*/
     24/*
     25  Predicate test. The parent should be better or equal to the child. Since the predicate
     26  comparison_(x,y) returns true if y (child) is strictly better, we want failure on the
     27  initial test. Clearly, success for comparison(x,y) and comparison(y,x) is also a failure.
     28
     29  Returns true if the predicate passes, false if it fails.
     30*/
     31bool check_pred (CbcCompareBase &pred, CbcNode *parent, CbcNode *child)
     32{
     33  if (parent == 0 || child == 0) return (false) ;
     34        if (!pred(parent,child))
     35                return (true) ;
     36  else if (pred(child,parent))
     37          std::cout
     38                        << " Heap predicate failure! (x<y) && (y<x)!" << std::endl ;
     39        return (false) ;
     40}
     41
     42} // end file-local namespace
     43
     44/*
     45  Check for the heap property: the parent is better than or equal to either child.
     46 
     47  The heap is a binary tree, stored in the vector layer by layer. By advancing parent
     48  at half the rate of child (aka curNode), we check both children of a given parent.
     49  (Draw yourself a picture; it'll help.) An empty heap is trivially valid. A heap with
     50  no predicate is trivially invalid.
     51
     52  TODO: The heap -> vector mapping assumed here is valid for the MSVS heap implementation.
     53        No guarantee it's valid elsewhere.
     54*/
     55
     56void CbcTree::validateHeap ()
     57{
     58  if (comparison_.test_ == 0) {
     59    std::cout
     60      << " Invalid heap (no predicate)!" << std::endl ;
     61    return ;
     62  }
     63  std::vector<CbcNode *>::const_iterator curNode,lastNode ;
     64  curNode = nodes_.begin() ;
     65  lastNode = nodes_.end() ;
     66  int curNdx = 0 ;
     67  int parNdx = 0 ;
     68  if (curNode == lastNode) return ;
     69  if (*curNode == 0) {
     70    std::cout
     71      << " Invalid heap[" << curNdx << "] (null entry)!" << std::endl ;
     72  }
     73  std::vector<CbcNode *>::const_iterator parent ;
     74  std::vector<CbcNode*>::const_iterator &child = curNode ;
     75  for (parent = curNode ; ++curNode != lastNode ; ++parent, ++parNdx) {
     76    curNdx++ ;
     77    if (*parent == 0) {
     78      std::cout
     79        << " Invalid heap[" << parNdx << "] (parent null entry)!" << std::endl ;
     80      curNode++ ;
     81      curNdx++ ;
     82      continue ;
     83    }
     84    if (*curNode == 0) {
     85      std::cout
     86        << " Invalid heap[" << curNdx << "] (left child null entry)!" << std::endl ;
     87    } else {
     88      if (!check_pred(*comparison_.test_,*parent,*child)) {
     89        std::cout
     90          << " Invalid heap (left child better)!" << std::endl ;
     91        CbcNode *node = *parent ;
     92        std::cout
     93          << "   Parent [" << parNdx << "] (" << std::hex << node << std::dec
     94          << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
     95          << ", obj " << node->objectiveValue() << "." << std::endl ;
     96        node = *child ;
     97        std::cout
     98          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
     99          << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
     100          << ", obj " << node->objectiveValue() << "." << std::endl ;
     101      }
     102    }
     103    curNode++ ;
     104    curNdx++ ;
     105    if (curNode == lastNode) break ;
     106    if (*curNode == 0) {
     107      std::cout
     108        << " Invalid heap[" << curNdx << "] (right child null entry)!" << std::endl ;
     109    } else {
     110      if (!check_pred(*comparison_.test_,*parent,*child)) {
     111        std::cout
     112          << " Invalid heap (right child better)!" << std::endl ;
     113        CbcNode *node = *parent ;
     114        std::cout
     115          << "   Parent [" << parNdx << "] (" << std::hex << node << std::dec
     116          << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
     117          << ", obj " << node->objectiveValue() << "." << std::endl ;
     118        node = *child ;
     119        std::cout
     120          << "   Child [" << curNdx << "] (" << std::hex << node << std::dec
     121          << ") unsat " << node->numberUnsatisfied() << ", depth " << node->depth()
     122          << ", obj " << node->objectiveValue() << "." << std::endl ;
     123      }
     124    }
     125  }
     126return ;
     127}
     128   
     129
     130#endif // CBC_DEBUG_HEAP
     131
    11132
    12133CbcTree::CbcTree()
     
    59180    return *this;
    60181}
     182
     183/*
     184  Rebuild the heap.
     185*/
     186void CbcTree::rebuild ()
     187{
     188  std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
     189# if CBC_DEBUG_HEAP > 1
     190  std::cout << "  HEAP: rebuild complete." << std::endl ;
     191# endif
     192# if CBC_DEBUG_HEAP > 0
     193  validateHeap() ;
     194# endif
     195}
     196
     197
    61198// Adds branching information to complete state
    62199void
     
    170307    return new CbcTree(*this);
    171308}
    172 //#define CBC_DEBUG_HEAP
     309
     310
    173311#ifndef CBC_DUBIOUS_HEAP
    174 // Set comparison function and resort heap
     312/*
     313  Set comparison predicate and re-sort the heap.
     314
     315  Note that common usage is to tweak the incumbent predicate and then
     316  call this method to rebuild the heap. Hence we cannot check for heap
     317  validity at entry. rebuild() will check on the way out, if
     318  CBC_DEBUG_HEAP is set.
     319
     320  TODO: remove the call to cleanDive and put it somewhere appropriate.
     321*/
    175322void
    176323CbcTree::setComparison(CbcCompareBase  &compare)
    177324{
     325#   if CBC_DEBUG_HEAP > 1
     326    std::cout << "  HEAP: resetting comparison predicate." << std::endl ;
     327#   endif
    178328    comparison_.test_ = &compare;
    179     CbcCompareDefault * compareD = dynamic_cast<CbcCompareDefault *>
    180                                    (&compare);
     329   
     330/*
     331  From a software engineering point of view, setComparison has no business
     332  knowing anything about the comparison function. Need to look for a better
     333  solution. Perhaps a callback comparable to newSolution, executing when
     334  the comparison method is set (i.e., in setComparison).
     335  -- lh, 100921 --
     336*/
     337    CbcCompareDefault *compareD =
     338          dynamic_cast<CbcCompareDefault *>(&compare);
    181339    if (compareD) {
    182340        // clean up diving
    183341        compareD->cleanDive();
    184342    }
    185     std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
     343    rebuild() ;
    186344}
    187345
     
    199357    x->setNodeNumber(maximumNodeNumber_);
    200358    maximumNodeNumber_++;
    201     /*printf("push obj %g, refcount %d, left %d, pointing to %d\n",
    202        x->objectiveValue(),x->nodeInfo()->decrement(0),
    203        x->nodeInfo()->numberBranchesLeft(),x->nodeInfo()->numberPointingToThis());*/
    204     assert(x->objectiveValue() != COIN_DBL_MAX && x->nodeInfo());
     359#   if CBC_DEBUG_HEAP > 2
     360    CbcNodeInfo *info = x->nodeInfo() ;
     361    assert(info) ;
     362    std::cout
     363      << "  HEAP: Pushing node " << x->nodeNumber()
     364      << "(" << std::hex << x << std::dec << ") obj " << x->objectiveValue()
     365      << ", ref " << info->decrement(0)
     366      << ", todo " << info->numberBranchesLeft()
     367      << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
     368    assert(x->objectiveValue() != COIN_DBL_MAX);
     369#   endif
     370#   if CBC_DEBUG_HEAP > 0
     371    validateHeap() ;
     372#   endif
    205373    x->setOnTree(true);
    206374    nodes_.push_back(x);
    207375    std::push_heap(nodes_.begin(), nodes_.end(), comparison_);
     376#   if CBC_DEBUG_HEAP > 0
     377    validateHeap() ;
     378#   endif
    208379}
    209380
     
    212383CbcTree::pop()
    213384{
     385   
     386#   if CBC_DEBUG_HEAP > 2
     387    CbcNode *node = nodes_.front() ;
     388    CbcNodeInfo *info = node->nodeInfo() ;
     389    assert(info) ;
     390    std::cout
     391      << "  HEAP: Popping node " << node->nodeNumber()
     392      << "(" << std::hex << node << std::dec
     393      << ") obj " << node->objectiveValue()
     394      << ", ref " << info->decrement(0)
     395      << ", todo " << info->numberBranchesLeft()
     396      << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
     397#   endif
     398#   if CBC_DEBUG_HEAP > 0
     399    validateHeap() ;
     400#   endif
    214401    nodes_.front()->setOnTree(false);
    215402    std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
    216403    nodes_.pop_back();
     404
     405#   if CBC_DEBUG_HEAP > 0
     406    validateHeap() ;
     407#   endif
     408
    217409}
    218410
     
    223415    return nodes_.empty();
    224416}
    225 // Gets best node and takes off heap
     417/*
     418  Return the best node from the heap.
     419
     420  Note that best is offered a chance (checkIsCutoff) to reevaluate
     421  itself and make arbitrary changes. A caller should be prepared
     422  to check that the returned node is acceptable.
     423
     424  There's quite a bit of suspect code here, much of it disabled in
     425  some way. The net effect at present is to return the top node on
     426  the heap after offering the node an opportunity to reevaluate itself.
     427  Documentation for checkIsCutoff() puts no restrictions on allowable
     428  changes. -- lh, 100921 --
     429*/
    226430CbcNode *
    227431CbcTree::bestNode(double cutoff)
    228432{
     433# if CBC_DEBUG_HEAP > 0
     434  validateHeap() ;
     435# endif
     436/*
     437  This code is problematic. As of 100921, there's really no loop.
     438  If front() == null, an assert will trigger. checkIsCutoff seems to be
     439  work in progress; comments assert that it can make pretty much arbitrary
     440  changes to best. If best can change its objective, there's a good
     441  possibility the heap is invalid.
     442*/
    229443    CbcNode * best = NULL;
    230444    while (!best && nodes_.size()) {
     
    251465        }
    252466    }
    253     // switched off for now
    254     if (best && comparison_.test_->fullScan() && false) {
     467/*
     468  See if the comparison object wants us to do a full scan with the
     469  alternative criteria. The net effect is to confirm best by the
     470  alternative criteria, or identify a competitor and erase it.
     471
     472  This code is problematic. Nulling an arbitrary node will in general
     473  break the heap property. Disabled some time ago, as noted in several
     474  places.
     475*/
     476    if (false && best && comparison_.test_->fullScan()) {
    255477        CbcNode * saveBest = best;
    256         int n = nodes_.size();
    257         int iBest = -1;
    258         for (int i = 0; i < n; i++) {
     478        size_t n = nodes_.size();
     479        size_t iBest = -1;
     480        for (size_t i = 0; i < n; i++) {
    259481            // temp
    260482            assert (nodes_[i]);
     
    278500        }
    279501    } else if (best) {
     502#       if CBC_DEBUG_HEAP > 2
     503        CbcNode *node = nodes_.front() ;
     504        CbcNodeInfo *info = node->nodeInfo() ;
     505        assert(info) ;
     506        std::cout
     507          << "  bestNode: Popping node " << node->nodeNumber()
     508          << "(" << std::hex << node << std::dec
     509          << ") obj " << node->objectiveValue()
     510          << ", ref " << info->decrement(0)
     511          << ", todo " << info->numberBranchesLeft()
     512          << ", refd by " << info->numberPointingToThis() << "." << std::endl ;
     513#       endif
    280514        // take off
    281515        std::pop_heap(nodes_.begin(), nodes_.end(), comparison_);
    282516        nodes_.pop_back();
    283517    }
    284 #ifdef DEBUG_CBC_HEAP
    285     if (best) {
    286         int n = nodes_.size();
    287         bool good = true;
    288         for (int i = 0; i < n; i++) {
    289             // temp
    290             assert (nodes_[i]);
    291             if (!comparison_.compareNodes(nodes_[i], best)) {
    292                 good = false;
    293                 CbcNode * x = nodes_[i];
    294                 printf("i=%d x is better nun %d depth %d obj %g, best nun %d depth %d obj %g\n", i,
    295                        x->numberUnsatisfied(), x->depth(), x->objectiveValue(),
    296                        best->numberUnsatisfied(), best->depth(), best->objectiveValue());
    297             }
    298         }
    299         if (!good) {
    300             // compare best to all
    301             int i;
    302             for (i = 0; i < n; i++) {
    303                 CbcNode * x = nodes_[i];
    304                 printf("i=%d x is nun %d depth %d obj %g", i,
    305                        x->numberUnsatisfied(), x->depth(), x->objectiveValue());
    306                 if (!comparison_.compareNodes(x, best)) {
    307                     printf(" - best is worse!\n");
    308                 } else {
    309                     printf("\n");
    310                 }
    311             }
    312             // Now compare amongst rest
    313             for (i = 0; i < n; i++) {
    314                 CbcNode * x = nodes_[i];
    315                 printf("For i=%d ", i);
    316                 for (int j = i + 1; j < n; j++) {
    317                     CbcNode * y = nodes_[j];
    318                     if (!comparison_.compareNodes(x, y)) {
    319                         printf(" b %d", j);
    320                     } else {
    321                         printf(" w %d", j);
    322                     }
    323                 }
    324                 printf("\n");
    325             }
    326             assert(good);
    327         }
    328     }
     518#if CBC_DEBUG_HEAP > 0
     519    validateHeap() ;
    329520#endif
    330521    if (best)
     
    346537/*! \brief Prune the tree using an objective function cutoff
    347538
    348   This routine removes all nodes with objective worst than the
     539  This routine removes all nodes with objective worse than the
    349540  specified cutoff value.
    350541*/
     
    353544CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
    354545{
     546#   if CBC_DEBUG_HEAP > 1
     547    std::cout << " cleanTree: beginning clean." << std::endl ;
     548#   endif
     549#   if CBC_DEBUG_HEAP > 0
     550    validateHeap() ;
     551#   endif
    355552    int j;
    356553    int nNodes = size();
     
    389586        push(nodeArray[j]);
    390587    }
     588#   if CBC_DEBUG_HEAP > 1
     589    std::cout << " cleanTree: finished rebuild." << std::endl ;
     590#   endif
     591#   if CBC_DEBUG_HEAP > 0
     592    validateHeap() ;
     593#   endif
    391594    /*
    392595      Sort the list of nodes to be deleted, nondecreasing.
     
    450653CbcTree::bestAlternate()
    451654{
    452     int n = nodes_.size();
     655    size_t n = nodes_.size();
    453656    CbcNode * best = NULL;
    454657    if (n) {
    455658        best = nodes_[0];
    456         for (int i = 1; i < n; i++) {
     659        for (size_t i = 1; i < n; i++) {
    457660            if (comparison_.alternateTest(best, nodes_[i])) {
    458661                best = nodes_[i];
     
    463666}
    464667
    465 #ifdef JJF_ZERO // not used, referenced removed in CbcModel.cpp
     668#ifdef JJF_ZERO // not used, reference removed in CbcModel.cpp
    466669CbcTreeArray::CbcTreeArray()
    467670        : CbcTree(),
     
    505708{
    506709    comparison_.test_ = &compare;
    507     std::make_heap(nodes_.begin(), nodes_.end(), comparison_);
     710    rebuild() ;
    508711}
    509712
     
    8381041}
    8391042#endif
    840 #else
     1043
     1044#else  // defined(CBC_DUBIOUS_HEAP)
     1045
     1046/*
     1047  Unclear whether this code is useful any longer. Likely stale. See
     1048  note in CbcCompareDefault.hpp re. CBC_DUBIOUS_HEAP.
     1049  -- lh, 100921 --
     1050*/
     1051
    8411052// Set comparison function and resort heap
    8421053void
  • trunk/Cbc/src/CbcTree.hpp

    r1393 r1506  
    1313#include "CbcCompare.hpp"
    1414
    15 /*! \class tree
    16     \brief Implementation of live set as a heap.
    17 
    18     This class is used to hold the set of live nodes in the search tree.
     15/*! \brief Using MS heap implementation
     16
     17  It's unclear if this is needed any longer, or even if it should be allowed.
     18  Cbc occasionally tries to do things to the tree (typically tweaking the
     19  comparison predicate) that can cause a violation of the heap property (parent better
     20  than either child). In a debug build, Microsoft's heap implementation does checks that
     21  detect this and fail. This symbol switched to an alternate implementation of CbcTree,
     22  and there are clearly differences, but no explanation as to why or what for.
     23
     24  As of 100921, the code is cleaned up to make it through `cbc -unitTest' without
     25  triggering `Invalid heap' in an MSVS debug build. The method validateHeap() can
     26  be used for debugging if this turns up again.
    1927*/
    2028//#define CBC_DUBIOUS_HEAP
     
    2331#endif
    2432#ifndef CBC_DUBIOUS_HEAP
     33
     34/*! \brief Controls search tree debugging
     35
     36  In order to have validateHeap() available, set CBC_DEBUG_HEAP
     37  to 1 or higher.
     38
     39  - 1 calls validateHeap() after each change to the heap
     40  - 2 will print a line for major operations (clean, set comparison, etc.)
     41  - 3 will print information about each push and pop
     42
     43#define CBC_DEBUG_HEAP 1
     44*/
     45
     46
     47/*! \class CbcTree
     48    \brief Implementation of the live set as a heap.
     49
     50    This class is used to hold the set of live nodes in the search tree.
     51*/
    2552class CbcTree {
    2653
    2754public:
    28 
    29     // Default Constructor
     55    /*! \name Constructors and related */
     56//@{
     57    /// Default Constructor
    3058    CbcTree ();
    3159
    32     // Copy constructor
    33     CbcTree ( const CbcTree & rhs);
    34     // = operator
    35     CbcTree & operator=(const CbcTree & rhs);
    36 
     60    /// Copy constructor
     61    CbcTree (const CbcTree &rhs);
     62
     63    /// = operator
     64    CbcTree & operator=(const CbcTree &rhs);
     65
     66    /// Destructor
    3767    virtual ~CbcTree();
    3868
    3969    /// Clone
    4070    virtual CbcTree * clone() const;
     71
    4172    /// Create C++ lines to get to current state
    42     virtual void generateCpp( FILE * ) {}
     73    virtual void generateCpp(FILE *) {}
     74//@}
    4375
    4476    /*! \name Heap access and maintenance methods */
    4577//@{
    46 
    4778    /// Set comparison function and resort heap
    48     void setComparison(CbcCompareBase  &compare);
     79    void setComparison(CbcCompareBase &compare);
    4980
    5081    /// Return the top node of the heap
     
    5283
    5384    /// Add a node to the heap
    54     virtual void push(CbcNode * x);
     85    virtual void push(CbcNode *x);
    5586
    5687    /// Remove the top node from the heap
    5788    virtual void pop() ;
    58     /// Gets best node and takes off heap
     89
     90    /*! \brief Gets best node and takes off heap
     91
     92      Before returning the node from the top of the heap, the node
     93      is offered an opportunity to reevaluate itself. Callers should
     94      be prepared to check that the node returned is suitable for use.
     95    */
    5996    virtual CbcNode * bestNode(double cutoff);
    6097
    61 //@}
    62     /*! \name vector methods */
    63 //@{
    64 
    65     /// Test if empty *** note may be overridden
     98    /*! \brief Rebuild the heap */
     99    virtual void rebuild() ;
     100//@}
     101
     102    /*! \name Direct node access methods */
     103//@{
     104    /// Test for an empty tree
    66105    virtual bool empty() ;
    67106
    68107    /// Return size
    69     virtual int size() const {
    70         return nodes_.size();
    71     }
    72     /// [] operator
    73     inline CbcNode * operator [] (int i) const {
    74         return nodes_[i];
    75     }
     108    virtual int size() const { return static_cast<int>(nodes_.size()); }
    76109
    77110    /// Return a node pointer
    78     inline CbcNode * nodePointer (int i) const {
    79         return nodes_[i];
    80     }
    81 
    82 
     111    inline CbcNode * operator [] (int i) const { return nodes_[i]; }
     112
     113    /// Return a node pointer
     114    inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
    83115//@}
    84116
    85117    /*! \name Search tree maintenance */
    86118//@{
    87 
    88119    /*! \brief Prune the tree using an objective function cutoff
    89120
    90       This routine removes all nodes with objective worst than the
    91       specified cutoff value.
    92       It also sets bestPossibleObjective to best
    93       of all on tree before deleting.
    94     */
    95 
     121      This routine removes all nodes with objective worse than the
     122      specified cutoff value. It also sets bestPossibleObjective to
     123      the best objective over remaining nodes.
     124    */
    96125    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    97126
     
    104133    /// Get best possible objective function in the tree
    105134    virtual double getBestPossibleObjective();
     135
    106136    /// Reset maximum node number
    107     inline void resetNodeNumbers() {
    108         maximumNodeNumber_ = 0;
    109     }
     137    inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
     138
    110139    /// Get maximum node number
    111     inline int maximumNodeNumber() const {
    112         return maximumNodeNumber_;
    113     }
     140    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
     141
    114142    /// Set number of branches
    115     inline void setNumberBranching(int value) {
    116         numberBranching_ = value;
    117     }
     143    inline void setNumberBranching(int value) { numberBranching_ = value; }
     144
    118145    /// Get number of branches
    119     inline int getNumberBranching() const {
    120         return numberBranching_;
    121     }
     146    inline int getNumberBranching() const { return numberBranching_; }
     147
    122148    /// Set maximum branches
    123     inline void setMaximumBranching(int value) {
    124         maximumBranching_ = value;
    125     }
     149    inline void setMaximumBranching(int value) { maximumBranching_ = value; }
     150
    126151    /// Get maximum branches
    127     inline int getMaximumBranching() const {
    128         return maximumBranching_;
    129     }
     152    inline int getMaximumBranching() const { return maximumBranching_; }
     153
    130154    /// Get branched variables
    131     inline unsigned int * branched() const {
    132         return branched_;
    133     }
     155    inline unsigned int * branched() const { return branched_; }
     156
    134157    /// Get bounds
    135     inline int * newBounds() const {
    136         return newBound_;
    137     }
     158    inline int * newBounds() const { return newBound_; }
     159
    138160    /// Adds branching information to complete state
    139161    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
     
    143165    void increaseSpace();
    144166//@}
     167
     168# if CBC_DEBUG_HEAP > 0
     169  /*! \name Debugging methods */
     170  //@{
     171    /*! \brief Check that the heap property is satisfied. */
     172    void validateHeap() ;
     173  //@}
     174# endif
     175
    145176protected:
     177    /// Storage vector for the heap
    146178    std::vector <CbcNode *> nodes_;
    147     CbcCompare comparison_;     ///> Sort function for heap ordering.
     179          /// Sort predicate for heap ordering.
     180    CbcCompare comparison_;
    148181    /// Maximum "node" number so far to split ties
    149182    int maximumNodeNumber_;
     
    160193    int * newBound_;
    161194};
    162 /*! \class tree
    163     \brief Implementation of live set as a managed array.
     195
     196#ifdef JJF_ZERO // not used
     197/*! \brief Implementation of live set as a managed array.
    164198
    165199    This class is used to hold the set of live nodes in the search tree.
    166200*/
    167 
    168 #ifdef JJF_ZERO // not used
    169201class CbcTreeArray : public CbcTree {
    170202
     
    326358#endif
    327359#else
     360/* CBC_DUBIOUS_HEAP is defined
     361
     362  See note at top of file. This code is highly suspect.
     363  -- lh, 100921 --
     364*/
    328365class CbcTree {
    329366
Note: See TracChangeset for help on using the changeset viewer.