Ignore:
Timestamp:
Apr 10, 2008 1:55:10 PM (13 years ago)
Author:
ladanyi
Message:

Incorporated changes from branches/heur

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcHeuristic.cpp

    r904 r912  
    1313#include <cfloat>
    1414
     15//#define PRINT_DEBUG
    1516#ifdef COIN_HAS_CLP
    1617#include "OsiClpSolverInterface.hpp"
     
    2425#include "OsiAuxInfo.hpp"
    2526#include "OsiPresolve.hpp"
     27#include "CbcBranchActual.hpp"
     28//==============================================================================
     29
     30CbcHeuristicNode::CbcHeuristicNode(const CbcHeuristicNode& rhs)
     31{
     32  numObjects_ = rhs.numObjects_;
     33  brObj_ = new CbcBranchingObject*[numObjects_];
     34  for (int i = 0; i < numObjects_; ++i) {
     35    brObj_[i] = rhs.brObj_[i]->clone();
     36  }
     37}
     38
     39void
     40CbcHeuristicNodeList::gutsOfDelete()
     41{
     42  for (int i = nodes_.size() - 1; i >= 0; --i) {
     43    delete nodes_[i];
     44  }
     45}
     46
     47void
     48CbcHeuristicNodeList::gutsOfCopy(const CbcHeuristicNodeList& rhs)
     49{
     50  append(rhs);
     51}
     52
     53CbcHeuristicNodeList::CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs)
     54{
     55  gutsOfCopy(rhs);
     56}
     57
     58CbcHeuristicNodeList& CbcHeuristicNodeList::operator=
     59(const CbcHeuristicNodeList& rhs)
     60{
     61  if (this != &rhs) {
     62    gutsOfDelete();
     63    gutsOfCopy(rhs);
     64  }
     65  return *this;
     66}
     67
     68CbcHeuristicNodeList::~CbcHeuristicNodeList()
     69{
     70  gutsOfDelete();
     71}
     72
     73void
     74CbcHeuristicNodeList::append(CbcHeuristicNode*& node)
     75{
     76  nodes_.push_back(node);
     77  node = NULL;
     78}
     79
     80void
     81CbcHeuristicNodeList::append(const CbcHeuristicNodeList& nodes)
     82{
     83  nodes_.reserve(nodes_.size() + nodes.size());
     84  for (int i = 0; i < nodes.size(); ++i) {
     85    CbcHeuristicNode* node = new CbcHeuristicNode(*nodes.node(i));
     86    append(node);
     87  }
     88}
     89
     90//==============================================================================
    2691
    2792// Default Constructor
    28 CbcHeuristic::CbcHeuristic()
    29   :model_(NULL),
    30    when_(2),
    31    numberNodes_(200),
    32    feasibilityPumpOptions_(-1),
    33    fractionSmall_(1.0),
    34    heuristicName_("Unknown")
     93CbcHeuristic::CbcHeuristic() :
     94  model_(NULL),
     95  when_(2),
     96  numberNodes_(200),
     97  feasibilityPumpOptions_(-1),
     98  fractionSmall_(1.0),
     99  heuristicName_("Unknown"),
     100  howOften_(1),
     101  decayFactor_(0.0),
     102  shallowDepth_(1),
     103  howOftenShallow_(1),
     104  numInvocationsInShallow_(0),
     105  numInvocationsInDeep_(0),
     106  lastRunDeep_(0),
     107  numRuns_(0),
     108  minDistanceToRun_(1),
     109  runNodes_(),
     110  numCouldRun_(0)
    35111{
    36112  // As CbcHeuristic virtual need to modify .cpp if above change
     
    38114
    39115// Constructor from model
    40 CbcHeuristic::CbcHeuristic(CbcModel & model)
    41 :
     116CbcHeuristic::CbcHeuristic(CbcModel & model) :
    42117  model_(&model),
    43118  when_(2),
     
    45120  feasibilityPumpOptions_(-1),
    46121  fractionSmall_(1.0),
    47   heuristicName_("Unknown")
    48 {
    49   // As CbcHeuristic virtual need to modify .cpp if above change
     122  heuristicName_("Unknown"),
     123  howOften_(1),
     124  decayFactor_(0.0),
     125  shallowDepth_(1),
     126  howOftenShallow_(1),
     127  numInvocationsInShallow_(0),
     128  numInvocationsInDeep_(0),
     129  lastRunDeep_(0),
     130  numRuns_(0),
     131  minDistanceToRun_(1),
     132  runNodes_(),
     133  numCouldRun_(0)
     134{}
     135
     136void
     137CbcHeuristic::gutsOfCopy(const CbcHeuristic & rhs)
     138{
     139  model_ = rhs.model_;
     140  when_ = rhs.when_;
     141  numberNodes_ = rhs.numberNodes_;
     142  feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_;
     143  fractionSmall_ = rhs.fractionSmall_;
     144  randomNumberGenerator_ = rhs.randomNumberGenerator_;
     145  heuristicName_ = rhs.heuristicName_;
     146  howOften_ = rhs.howOften_;
     147  decayFactor_ = rhs.howOften_;
     148  shallowDepth_= rhs.shallowDepth_;
     149  howOftenShallow_= rhs.howOftenShallow_;
     150  numInvocationsInShallow_ = rhs.numInvocationsInShallow_;
     151  numInvocationsInDeep_ = rhs.numInvocationsInDeep_;
     152  lastRunDeep_ = rhs.lastRunDeep_;
     153  numRuns_ = rhs.numRuns_;
     154  numCouldRun_ = rhs.numCouldRun_;
     155  minDistanceToRun_ = rhs.minDistanceToRun_;
     156  runNodes_ = rhs.runNodes_;
    50157}
    51158// Copy constructor
    52159CbcHeuristic::CbcHeuristic(const CbcHeuristic & rhs)
    53 :
    54   model_(rhs.model_),
    55   when_(rhs.when_),
    56   numberNodes_(rhs.numberNodes_),
    57   feasibilityPumpOptions_(rhs.feasibilityPumpOptions_),
    58   fractionSmall_(rhs.fractionSmall_),
    59   randomNumberGenerator_(rhs.randomNumberGenerator_),
    60   heuristicName_(rhs.heuristicName_)
    61 {
    62 }
     160{
     161  gutsOfCopy(rhs);
     162}
     163
    63164// Assignment operator
    64165CbcHeuristic &
     
    66167{
    67168  if (this!=&rhs) {
    68     model_ = rhs.model_;
    69     when_ = rhs.when_;
    70     numberNodes_ = rhs.numberNodes_;
    71     feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_;
    72     fractionSmall_ = rhs.fractionSmall_;
    73     randomNumberGenerator_ = rhs.randomNumberGenerator_;
    74     heuristicName_ = rhs.heuristicName_ ;
     169    gutsOfDelete();
     170    gutsOfCopy(rhs);
    75171  }
    76172  return *this;
     173}
     174
     175void CbcHeurDebugNodes(CbcModel* model_)
     176{
     177  CbcNode* node = model_->currentNode();
     178  CbcNodeInfo* nodeInfo = node->nodeInfo();
     179  std::cout << "===============================================================\n";
     180  while (nodeInfo) {
     181    const CbcNode* node = nodeInfo->owner();
     182    printf("nodeinfo: node %i\n", nodeInfo->nodeNumber());
     183    {
     184      const CbcIntegerBranchingObject* brPrint =
     185        dynamic_cast<const CbcIntegerBranchingObject*>(nodeInfo->parentBranch());
     186      if (!brPrint) {
     187        printf("    parentBranch: NULL\n");
     188      } else {
     189        const double* downBounds = brPrint->downBounds();
     190        const double* upBounds = brPrint->upBounds();
     191        int variable = brPrint->variable();
     192        int way = brPrint->way();
     193        printf("   parentBranch: var %i downBd [%i,%i] upBd [%i,%i] way %i\n",
     194               variable, (int)downBounds[0], (int)downBounds[1],
     195               (int)upBounds[0], (int)upBounds[1], way);
     196      }
     197    }
     198    if (! node) {
     199      printf("    owner: NULL\n");
     200    } else {
     201      printf("    owner: node %i depth %i onTree %i active %i",
     202             node->nodeNumber(), node->depth(), node->onTree(), node->active());
     203      const OsiBranchingObject* osibr =
     204        nodeInfo->owner()->branchingObject();
     205      const CbcBranchingObject* cbcbr =
     206        dynamic_cast<const CbcBranchingObject*>(osibr);
     207      const CbcIntegerBranchingObject* brPrint =
     208        dynamic_cast<const CbcIntegerBranchingObject*>(cbcbr);
     209      if (!brPrint) {
     210        printf("        ownerBranch: NULL\n");
     211      } else {
     212        const double* downBounds = brPrint->downBounds();
     213        const double* upBounds = brPrint->upBounds();
     214        int variable = brPrint->variable();
     215        int way = brPrint->way();
     216        printf("        ownerbranch: var %i downBd [%i,%i] upBd [%i,%i] way %i\n",
     217               variable, (int)downBounds[0], (int)downBounds[1],
     218               (int)upBounds[0], (int)upBounds[1], way);
     219      }
     220    }
     221    nodeInfo = nodeInfo->parent();
     222  }
     223}
     224
     225void
     226CbcHeuristic::debugNodes()
     227{
     228  CbcHeurDebugNodes(model_);
     229}
     230
     231void
     232CbcHeuristic::printDistanceToNodes()
     233{
     234  const CbcNode* currentNode = model_->currentNode();
     235  if (currentNode != NULL) {
     236    CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_);
     237    for (int i = runNodes_.size() - 1; i >= 0; --i) {
     238      nodeDesc->distance(runNodes_.node(i));
     239    }
     240    runNodes_.append(nodeDesc);
     241  }
     242}
     243
     244bool
     245CbcHeuristic::shouldHeurRun()
     246{
     247
     248#if 0
     249  const CbcNode* currentNode = model_->currentNode();
     250  if (currentNode == NULL) {
     251    return false;
     252  }
     253
     254  debugNodes();
     255//   return false;
     256
     257  const int depth = currentNode->depth();
     258#else
     259  int depth = 0;
     260  const CbcNode* currentNode = model_->currentNode();
     261  if (currentNode != NULL) {
     262    depth = currentNode->depth();
     263#ifdef PRINT_DEBUG
     264    debugNodes();
     265#endif
     266  }
     267#endif
     268
     269  const int nodeCount = model_->getNodeCount();  // FIXME: check that this is
     270                                                 // correct in parallel
     271
     272  if (nodeCount == 0 || depth <= shallowDepth_) {
     273    // what to do when we are in the shallow part of the tree
     274    if (model_->getCurrentPassNumber() == 1) {
     275      // first time in the node...
     276      numInvocationsInShallow_ = 0;
     277    }
     278    ++numInvocationsInShallow_;
     279    // Very large howOftenShallow_ will give the original test:
     280    // (model_->getCurrentPassNumber() != 1)
     281    //    if ((numInvocationsInShallow_ % howOftenShallow_) != 1) {
     282    if ((numInvocationsInShallow_ % howOftenShallow_) != 0) {
     283      return false;
     284    }
     285    // LL: should we save these nodes in the list of nodes where the heur was
     286    // LL: run?
     287#if 1
     288    if (currentNode != NULL) {
     289      // Get where we are and create the appropriate CbcHeuristicNode object
     290      CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_);
     291      runNodes_.append(nodeDesc);
     292    }
     293#endif
     294  } else {
     295    // deeper in the tree
     296    if (model_->getCurrentPassNumber() == 1) {
     297      // first time in the node...
     298      ++numInvocationsInDeep_;
     299    }
     300    if (numInvocationsInDeep_ - lastRunDeep_ < howOften_) {
     301      return false;
     302    }
     303    if (model_->getCurrentPassNumber() != 1) {
     304      // Run the heuristic only when first entering the node.
     305      // LL: I don't think this is right. It should run just before strong
     306      // LL: branching, I believe.
     307      return false;
     308    }
     309    // Get where we are and create the appropriate CbcHeuristicNode object
     310    CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_);
     311    //#ifdef PRINT_DEBUG
     312#if 1
     313    double minDistance = nodeDesc->minDistance(runNodes_);
     314    double minDistanceToRun = 1.5 * log((double)depth) / log((double)2);
     315    std::cout<<"minDistance = "<<minDistance
     316             <<", minDistanceToRun = "<<minDistanceToRun<<std::endl;
     317    if (minDistance < minDistanceToRun) {
     318#else
     319    if (nodeDesc->minDistance(runNodes_) < minDistanceToRun_) {
     320#endif
     321      delete nodeDesc;
     322      return false;
     323    }
     324    runNodes_.append(nodeDesc);
     325    lastRunDeep_ = numInvocationsInDeep_;
     326    //    ++lastRunDeep_;
     327  }
     328  ++numRuns_;
     329  return true;
     330}
     331
     332bool
     333CbcHeuristic::shouldHeurRun_randomChoice()
     334{
     335  int depth = 0;
     336  const CbcNode* currentNode = model_->currentNode();
     337  if (currentNode != NULL) {
     338    depth = currentNode->depth();
     339  }
     340
     341  if(depth != 0) {
     342    const double numerator = depth * depth;
     343    const double denominator = exp(depth * log((double)2));
     344    double probability = numerator / denominator;
     345    double randomNumber = randomNumberGenerator_.randomDouble();
     346    if (randomNumber>probability)
     347      return false;
     348   
     349    if (model_->getCurrentPassNumber() > 1)
     350      return false;
     351  }
     352  ++numRuns_;
     353  return true;
    77354}
    78355
     
    82359{
    83360  model_=model;
    84 }
     361  }
    85362// Set seed
    86363void
     
    460737  return returnCode;
    461738}
     739
     740//##############################################################################
     741
     742inline int compare3BranchingObjects(const CbcBranchingObject* br0,
     743                                    const CbcBranchingObject* br1)
     744{
     745  const int t0 = br0->type();
     746  const int t1 = br1->type();
     747  if (t0 < t1) {
     748    return -1;
     749  }
     750  if (t0 > t1) {
     751    return 1;
     752  }
     753  return br0->compareOriginalObject(br1);
     754}
     755
     756//==============================================================================
     757
     758inline bool compareBranchingObjects(const CbcBranchingObject* br0,
     759                                    const CbcBranchingObject* br1)
     760{
     761  return compare3BranchingObjects(br0, br1) < 0;
     762}
     763
     764//==============================================================================
     765
     766void
     767CbcHeuristicNode::gutsOfConstructor(CbcModel& model)
     768{
     769  //  CbcHeurDebugNodes(&model);
     770  CbcNode* node = model.currentNode();
     771  brObj_ = new CbcBranchingObject*[node->depth()];
     772  CbcNodeInfo* nodeInfo = node->nodeInfo();
     773  int cnt = 0;
     774  while (nodeInfo->parentBranch() != NULL) {
     775    brObj_[cnt++] = nodeInfo->parentBranch()->clone();
     776    nodeInfo = nodeInfo->parent();
     777  }
     778  std::sort(brObj_, brObj_+cnt, compareBranchingObjects);
     779  if (cnt <= 1) {
     780    numObjects_ = cnt;
     781  } else {
     782    numObjects_ = 0;
     783    CbcBranchingObject* br;
     784    for (int i = 1; i < cnt; ++i) {
     785      if (compare3BranchingObjects(brObj_[numObjects_], brObj_[i]) == 0) {
     786        int comp = brObj_[numObjects_]->compareBranchingObject(brObj_[i], &br);
     787        switch (comp) {
     788        case CbcRangeSame: // the same range
     789        case CbcRangeDisjoint: // disjoint decisions
     790          // should not happen! we are on a chain!
     791          abort();
     792        case CbcRangeSubset: // brObj_[numObjects_] is a subset of brObj_[i]
     793          delete brObj_[i];
     794          break;
     795        case CbcRangeSuperset: // brObj_[i] is a subset of brObj_[numObjects_]
     796          delete brObj_[numObjects_];
     797          brObj_[numObjects_] = brObj_[i];
     798          break;
     799        case CbcRangeOverlap: // overlap
     800          delete brObj_[i];
     801          delete brObj_[numObjects_];
     802          brObj_[numObjects_] = br;
     803          break;
     804      }
     805        continue;
     806      } else {
     807        brObj_[++numObjects_] = brObj_[i];
     808      }
     809    }
     810    ++numObjects_;
     811  }
     812}
     813
     814//==============================================================================
     815
     816CbcHeuristicNode::CbcHeuristicNode(CbcModel& model)
     817{
     818  gutsOfConstructor(model);
     819}
     820
     821//==============================================================================
     822
     823double
     824CbcHeuristicNode::distance(const CbcHeuristicNode* node) const
     825{
     826
     827  const double disjointWeight = 1;
     828  const double overlapWeight = 0.4;
     829  const double subsetWeight = 0.2;
     830  int countDisjointWeight = 0;
     831  int countOverlapWeight = 0;
     832  int countSubsetWeight = 0;
     833  int i = 0;
     834  int j = 0;
     835  double dist = 0.0;
     836#ifdef PRINT_DEBUG
     837  printf(" numObjects_ = %i, node->numObjects_ = %i\n",
     838         numObjects_, node->numObjects_);
     839#endif
     840  while( i < numObjects_ && j < node->numObjects_) {
     841    CbcBranchingObject* br0 = brObj_[i];
     842    const CbcBranchingObject* br1 = node->brObj_[j];
     843#ifdef PRINT_DEBUG
     844    const CbcIntegerBranchingObject* brPrint0 =
     845      dynamic_cast<const CbcIntegerBranchingObject*>(br0);
     846    const double* downBounds = brPrint0->downBounds();
     847    const double* upBounds = brPrint0->upBounds();
     848    int variable = brPrint0->variable();
     849    int way = brPrint0->way();
     850    printf("   br0: var %i downBd [%i,%i] upBd [%i,%i] way %i\n",
     851           variable, (int)downBounds[0], (int)downBounds[1],
     852           (int)upBounds[0], (int)upBounds[1], way);
     853    const CbcIntegerBranchingObject* brPrint1 =
     854      dynamic_cast<const CbcIntegerBranchingObject*>(br1);
     855    downBounds = brPrint1->downBounds();
     856    upBounds = brPrint1->upBounds();
     857    variable = brPrint1->variable();
     858    way = brPrint1->way();
     859    printf("   br1: var %i downBd [%i,%i] upBd [%i,%i] way %i\n",
     860           variable, (int)downBounds[0], (int)downBounds[1],
     861           (int)upBounds[0], (int)upBounds[1], way);
     862#endif
     863    const int brComp = compare3BranchingObjects(br0, br1);
     864    if (brComp < 0) {
     865      dist += subsetWeight;
     866      countSubsetWeight++;
     867      ++i;
     868    }
     869    else if (brComp > 0) {
     870      dist += subsetWeight;
     871      countSubsetWeight++;
     872      ++j;
     873    }
     874    else {
     875      const int comp = br0->compareBranchingObject(br1, false);
     876      switch (comp) {
     877      case CbcRangeSame:
     878        // do nothing
     879        break;
     880      case CbcRangeDisjoint: // disjoint decisions
     881        dist += disjointWeight;
     882        countDisjointWeight++;
     883        break;
     884      case CbcRangeSubset: // subset one way or another
     885      case CbcRangeSuperset:
     886        dist += subsetWeight;
     887        countSubsetWeight++;
     888        break;
     889      case CbcRangeOverlap: // overlap
     890        dist += overlapWeight;
     891        countOverlapWeight++;
     892        break;
     893      }
     894      ++i;
     895      ++j;
     896    }
     897  }
     898  dist += subsetWeight * (numObjects_ - i + node->numObjects_ - j);
     899  countSubsetWeight += (numObjects_ - i + node->numObjects_ - j);
     900  printf("subset = %i, overlap = %i, disjoint = %i\n", countSubsetWeight,
     901         countOverlapWeight, countDisjointWeight);
     902  return dist;
     903}
     904
     905//==============================================================================
     906
     907CbcHeuristicNode::~CbcHeuristicNode()
     908{
     909  for (int i = 0; i < numObjects_; ++i) {
     910    delete brObj_[i];
     911  }
     912  delete [] brObj_;
     913}
     914
     915//==============================================================================
     916
     917double
     918CbcHeuristicNode::minDistance(const CbcHeuristicNodeList& nodeList)
     919{
     920  double minDist = COIN_DBL_MAX;
     921  for (int i = nodeList.size() - 1; i >= 0; --i) {
     922    minDist = CoinMin(minDist, distance(nodeList.node(i)));
     923  }
     924  return minDist;
     925}
     926
     927//==============================================================================
     928
     929double
     930CbcHeuristicNode::avgDistance(const CbcHeuristicNodeList& nodeList)
     931{
     932  if (nodeList.size() == 0) {
     933    return COIN_DBL_MAX;
     934  }
     935  double sumDist = 0;
     936  for (int i = nodeList.size() - 1; i >= 0; --i) {
     937    sumDist += distance(nodeList.node(i));
     938  }
     939  return sumDist/nodeList.size();
     940}
     941
     942//##############################################################################
    462943
    463944// Default Constructor
Note: See TracChangeset for help on using the changeset viewer.