Changeset 901 for branches/heur


Ignore:
Timestamp:
Mar 17, 2008 3:33:54 PM (11 years ago)
Author:
jpgoncal
Message:

latest version with random choice.

Location:
branches/heur/Cbc/src
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/heur/Cbc/src/CbcHeuristic.cpp

    r897 r901  
    1212#include <cfloat>
    1313
     14#define PRINT_DEBUG
    1415#ifdef COIN_HAS_CLP
    1516#include "OsiClpSolverInterface.hpp"
     
    9798  heuristicName_("Unknown"),
    9899  howOften_(1),
    99   decayFactor_(0.5),
    100   shallowDepth_(0),
     100  decayFactor_(0.0),
     101  shallowDepth_(1),
    101102  howOftenShallow_(1),
    102103  numInvocationsInShallow_(0),
     
    104105  lastRunDeep_(0),
    105106  numRuns_(0),
    106   minDistanceToRun_(4),
     107  numCouldRun_(0),
     108  minDistanceToRun_(1),
    107109  runNodes_()
    108110{
     
    119121  heuristicName_("Unknown"),
    120122  howOften_(1),
    121   decayFactor_(0.5),
    122   shallowDepth_(0),
     123  decayFactor_(0.0),
     124  shallowDepth_(1),
    123125  howOftenShallow_(1),
    124126  numInvocationsInShallow_(0),
     
    126128  lastRunDeep_(0),
    127129  numRuns_(0),
    128   minDistanceToRun_(4),
     130  numCouldRun_(0),
     131  minDistanceToRun_(1),
    129132  runNodes_()
    130133{}
     
    148151  lastRunDeep_ = rhs.lastRunDeep_;
    149152  numRuns_ = rhs.numRuns_;
     153  numCouldRun_ = rhs.numCouldRun_;
    150154  minDistanceToRun_ = rhs.minDistanceToRun_;
    151155  runNodes_ = rhs.runNodes_;
     
    228232{
    229233
     234#if 0
    230235  const CbcNode* currentNode = model_->currentNode();
    231236  if (currentNode == NULL) {
     
    233238  }
    234239
    235 //   debugNodes();
     240  debugNodes();
    236241//   return false;
    237242
    238243  const int depth = currentNode->depth();
     244#else
     245  int depth = 0;
     246  const CbcNode* currentNode = model_->currentNode();
     247  if (currentNode != NULL) {
     248    depth = currentNode->depth();
     249#ifdef PRINT_DEBUG
     250    debugNodes();
     251#endif
     252  }
     253#endif
    239254
    240255  const int nodeCount = model_->getNodeCount();  // FIXME: check that this is
     
    250265    // Very large howOftenShallow_ will give the original test:
    251266    // (model_->getCurrentPassNumber() != 1)
    252     if ((numInvocationsInShallow_ % howOftenShallow_) != 1) {
     267    //    if ((numInvocationsInShallow_ % howOftenShallow_) != 1) {
     268    if ((numInvocationsInShallow_ % howOftenShallow_) != 0) {
    253269      return false;
    254270    }
    255271    // LL: should we save these nodes in the list of nodes where the heur was
    256272    // LL: run?
     273#if 1
     274    if (currentNode != NULL) {
     275      // Get where we are and create the appropriate CbcHeuristicNode object
     276      CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_);
     277      runNodes_.append(nodeDesc);
     278    }
     279#endif
    257280  } else {
    258281    // deeper in the tree
     
    272295    // Get where we are and create the appropriate CbcHeuristicNode object
    273296    CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_);
    274     std::cout<<"minDistance = "<<nodeDesc->minDistance(runNodes_)<<std::endl;
     297#ifdef PRINT_DEBUG
     298    double minDistance = nodeDesc->minDistance(runNodes_);
     299    double minDistanceToRun = log(depth) / log(2);
     300    std::cout<<"minDistance = "<<minDistance
     301             <<", minDistanceToRun = "<<minDistanceToRun<<std::endl;
     302    if (minDistance < minDistanceToRun) {
     303#else
    275304    if (nodeDesc->minDistance(runNodes_) < minDistanceToRun_) {
     305#endif
    276306      delete nodeDesc;
    277307      return false;
    278308    }
    279309    runNodes_.append(nodeDesc);
    280     ++lastRunDeep_;
     310    lastRunDeep_ = numInvocationsInDeep_;
     311    //    ++lastRunDeep_;
    281312  }
    282313  ++numRuns_;
     
    284315}
    285316
     317bool
     318CbcHeuristic::shouldHeurRun_randomChoice()
     319{
     320  int depth = 0;
     321  const CbcNode* currentNode = model_->currentNode();
     322  if (currentNode != NULL) {
     323    depth = currentNode->depth();
     324  }
     325
     326  if(depth != 0) {
     327
     328    double probability = depth / pow(2,depth);
     329    double randomNumber = randomNumberGenerator_.randomDouble();
     330    if (randomNumber>probability)
     331      return false;
     332   
     333    if (model_->getCurrentPassNumber() > 1)
     334      return false;
     335  }
     336  ++numRuns_;
     337  return true;
     338}
    286339
    287340// Resets stuff if model changes
     
    755808CbcHeuristicNode::distance(const CbcHeuristicNode* node) const
    756809{
     810
    757811  const double disjointWeight = 1;
    758812  const double overlapWeight = 0.4;
     
    761815  int j = 0;
    762816  double dist = 0.0;
     817#ifdef PRINT_DEBUG
     818  printf(" numObjects_ = %i, node->numObjects_ = %i\n",
     819         numObjects_, node->numObjects_);
     820#endif
    763821  while( i < numObjects_ && j < node->numObjects_) {
    764822    CbcBranchingObject* br0 = brObj_[i];
    765823    const CbcBranchingObject* br1 = node->brObj_[j];
     824#ifdef PRINT_DEBUG
     825    const CbcIntegerBranchingObject* brPrint0 =
     826      dynamic_cast<const CbcIntegerBranchingObject*>(br0);
     827    const double* downBounds = brPrint0->downBounds();
     828    const double* upBounds = brPrint0->upBounds();
     829    int variable = brPrint0->variable();
     830    int way = brPrint0->way();
     831    printf("   br0: var %i downBd [%i,%i] upBd [%i,%i] way %i\n",
     832           variable, (int)downBounds[0], (int)downBounds[1],
     833           (int)upBounds[0], (int)upBounds[1], way);
     834    const CbcIntegerBranchingObject* brPrint1 =
     835      dynamic_cast<const CbcIntegerBranchingObject*>(br1);
     836    downBounds = brPrint1->downBounds();
     837    upBounds = brPrint1->upBounds();
     838    variable = brPrint1->variable();
     839    way = brPrint1->way();
     840    printf("   br1: var %i downBd [%i,%i] upBd [%i,%i] way %i\n",
     841           variable, (int)downBounds[0], (int)downBounds[1],
     842           (int)upBounds[0], (int)upBounds[1], way);
     843#endif
    766844    const int brComp = compare3BranchingObjects(br0, br1);
    767845    if (brComp < 0) {
  • branches/heur/Cbc/src/CbcHeuristic.hpp

    r896 r901  
    179179  /** Check whether the heuristic should run */
    180180  bool shouldHeurRun();
     181  bool shouldHeurRun_randomChoice();
    181182  void debugNodes();
    182183
     
    229230  CbcHeuristicNodeList runNodes_;
    230231
     232  /// How many times the heuristic could run
     233  int numCouldRun_;
     234
     235
    231236#if 0
    232237  /// Lower bounds of last node where the heuristic found a solution
  • branches/heur/Cbc/src/CbcHeuristicDiveCoefficient.cpp

    r886 r901  
    55#  pragma warning(disable:4786)
    66#endif
     7
     8#define PRINT_DEBUG
    79
    810#include "CbcHeuristicDiveCoefficient.hpp"
     
    144146                                      double * betterSolution)
    145147{
    146   if (! shouldHeurRun()) {
     148  ++numCouldRun_;
     149
     150  //  bool runHeuristic = shouldHeurRun();
     151  bool runHeuristic = shouldHeurRun_randomChoice();
     152  //  std::cout<<"shouldHeurRun = "<<runHeuristic<<std::endl;
     153
     154#ifdef PRINT_DEBUG
     155  std::cout<<"numCouldRun_ = "<<numCouldRun_
     156           <<", numRuns_ = "<<numRuns_;
     157#endif
     158
     159
     160  if (! runHeuristic) {
     161#ifdef PRINT_DEBUG
     162    std::cout<<", solutionFound = 0"<<std::endl;
     163#endif
    147164    return 0;
    148165  }
     
    433450  }
    434451
     452#if 0
    435453  if (updateHowOften) {
    436454    howOften_ += (int) (howOften_*decayFactor_);
    437455  }
    438    
     456#endif
     457
     458#ifdef PRINT_DEBUG
     459  std::cout<<", solutionFound = "<<returnCode<<std::endl;
     460#endif
    439461
    440462  delete [] newSolution;
Note: See TracChangeset for help on using the changeset viewer.