Changeset 884 for branches/heur


Ignore:
Timestamp:
Feb 29, 2008 3:40:25 PM (11 years ago)
Author:
jpgoncal
Message:

Draft code for heuristic to control heuristics.

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

Legend:

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

    r863 r884  
    3131   feasibilityPumpOptions_(-1),
    3232   fractionSmall_(1.0),
    33    heuristicName_("Unknown")
     33   heuristicName_("Unknown"),
     34   howOften_(100),
     35   decayFactor_(0.5)
    3436{
    3537  // As CbcHeuristic virtual need to modify .cpp if above change
     
    4446  feasibilityPumpOptions_(-1),
    4547  fractionSmall_(1.0),
    46   heuristicName_("Unknown")
    47 {
    48   // As CbcHeuristic virtual need to modify .cpp if above change
    49 }
     48  heuristicName_("Unknown"),
     49  howOften_(100),
     50  decayFactor_(0.5)
     51{}
     52
    5053// Copy constructor
    5154CbcHeuristic::CbcHeuristic(const CbcHeuristic & rhs)
     
    5760  fractionSmall_(rhs.fractionSmall_),
    5861  randomNumberGenerator_(rhs.randomNumberGenerator_),
    59   heuristicName_(rhs.heuristicName_)
    60 {
    61 }
     62  heuristicName_(rhs.heuristicName_),
     63  howOften_(rhs.howOften_),
     64  decayFactor_(rhs.howOften_),
     65  runNodes_(rhs.runNodes_)
     66{}
     67
    6268// Assignment operator
    6369CbcHeuristic &
     
    7278    randomNumberGenerator_ = rhs.randomNumberGenerator_;
    7379    heuristicName_ = rhs.heuristicName_ ;
     80    howOften_ = rhs.howOften_;
     81    decayFactor_ = rhs.howOften_;
     82    runNodes_ = rhs.runNodes_;
    7483  }
    7584  return *this;
     
    8190{
    8291  model_=model;
    83 }
     92  }
    8493// Set seed
    8594void
     
    459468  return returnCode;
    460469}
     470
     471//#######################################################################################
     472
     473inline int compare3BranchingObjects(const OsiBranchingObject* br0,
     474                                    const OsiBranchingObject* br1)
     475{
     476  const int t0 = br0->type();
     477  const int t1 = br1->type();
     478  if (t0 < t1) {
     479    return -1;
     480  }
     481  if (t0 > t1) {
     482    return 1;
     483  }
     484  return br0->compareBaseObject(br1);
     485}
     486
     487//=======================================================================================
     488
     489inline bool compareBranchingObjects(const OsiBranchingObject* br0,
     490                                    const OsiBranchingObject* br1)
     491{
     492  return compare3BranchingObjects(br0, br1) < 0;
     493}
     494
     495//=======================================================================================
     496
     497CbcHeuristicNode::CbcHeuristicNode(CbcModel& model)
     498{
     499  CbcNode* node = model->currentNode();
     500  int depth = node->depth();
     501  numObjects_ = depth; //??
     502  brObj_ = new int[numObjects_];
     503  CbcNodeInfo* nodeInfo = node->nodeInfo();
     504  int depth = 0;
     505  while (nodeInfo) {
     506    brObj_[depth++] = nodeInfo->branchingObject()->clone();
     507    nodeInfo = nodeInfo->parent();
     508  }
     509  std::sort(brObj_, brObj_+depth, compareBranchingObjects);
     510  cnt = 0;
     511  OsiBranchingObject* br;
     512  for (int i = 1; i < depth; ++i) {
     513    if (compare3BranchingObjects(brObj_[cnt], brObj_[i]) == 0) {
     514      int comp = brObj_[cnt]->compareBranchingObject(brObj_[i], &br);
     515      switch (comp) {
     516      case 0: // disjoint decisions
     517        // should not happen! we are on a chain!
     518        abort();
     519      case 1: // brObj_[cnt] is a subset of brObj_[i]
     520        delete brObj_[i];
     521        break;
     522      case 2: // brObj_[i] is a subset of brObj_[cnt]
     523        delete brObj_[cnt];
     524        brObj_[cnt] = brObj_[i];
     525        break;
     526      case 3: // overlap
     527        delete brObj_[i];
     528        delete brObj_[cnt];
     529        brObj_[cnt] = br;
     530        break;
     531      }
     532      continue;
     533    } else {
     534      brObj_[++cnt] = brObj_[i];
     535    }
     536  }
     537  numObjects_ = cnt + 1;
     538}
     539
     540//=======================================================================================
     541
     542double
     543CbcHeuristicNode::distance(const CbcHeuristicNode* node) const
     544{
     545  const double disjointWeight = 1;
     546  const double overlapWeight = 0.2;
     547  const double subsetWeight = 0.1;
     548  int i = 0;
     549  int j = 0;
     550  double dist = 0.0;
     551  while( i < numObjects_ && j < node.numObjects_) {
     552    const OsiBranchingObject* br0 = brObj_[i];
     553    const OsiBranchingObject* br1 = node.brObj_[j];
     554    const int brComp = compare3BranchingObjects(br0, br1);
     555    switch (brcomp) {
     556    case -1:
     557      distance += subsetWeight;
     558      ++i;
     559      break;
     560    case 1:
     561      distance += subsetWeight;
     562      ++j;
     563      break;
     564    case 0:
     565      {
     566        const int comp = brObj_[cnt]->compareBranchingObject(brObj_[i], NULL);
     567        switch (comp) {
     568        case 0: // disjoint decisions
     569          distance += disjointWeight;
     570          break;
     571        case 1: // subset one way or another
     572        case 2:
     573          distance += subsetWeight;
     574          break;
     575        case 3: // overlap
     576          distance += overlapWeight;
     577          break;
     578        }
     579      }
     580      break;
     581    }
     582  }
     583  distance += subsetWeight * (numObjects_ - i + node.numObjects_ - j);
     584  return distance;
     585}
     586
     587//=======================================================================================
     588
     589CbcHeuristicNode::~CbcHeuristicNode()
     590{
     591  for (int i = 0; i < numObjects_; ++i) {
     592    delete brObj_[i];
     593  }
     594}
     595
     596//=======================================================================================
     597
     598bool
     599CbcHeuristicNodeList::farFrom(const CbcHeuristicNode* node)
     600{
     601 
     602 
     603  // Get Hamming distance to last node where a solution was found
     604  double
     605    CbcHeuristic::getHammingDistance(const OsiSolverInterface* solver) const
     606  {
     607    double hammingDistance = 0.0;
     608    int numberIntegers = model_->numberIntegers();
     609    const double * lower = solver->getColLower();
     610    const double * upper = solver->getColUpper();
     611    const int * integerVariable = model_->integerVariable();
     612    for (int i=0; i<numberIntegers; i++) {
     613      int iColumn = integerVariable[i];
     614      if(lowerBoundLastNode_[i] != lower[iColumn] ||
     615         upperBoundLastNode_[i] != upper[iColumn])
     616        hammingDistance += 1.0;
     617    }
     618    return hammingDistance;
     619  }
     620}
     621
     622//#######################################################################################
    461623
    462624// Default Constructor
  • branches/heur/Cbc/src/CbcHeuristic.hpp

    r854 r884  
    1515
    1616//#############################################################################
     17
     18/** A class describing the branching decisions that were made to get
     19    to the node where a heuristics was invoked from */
     20
     21class CbcHeuristicNode {
     22private::
     23  /// The number of branching decisions made
     24  int numObjects_;
     25  /** The indices of the branching objects. Note: an index may be
     26      listed multiple times. E.g., a general integer variable that has
     27      been branched on multiple times. */
     28  OsiBranchingObject** brObj_;
     29public:
     30  inline swap(CbcHeuristicNode& node) {
     31    ::swap(numObjects_, node.numObjects_);
     32    ::swap(objects_, node.objects_);
     33    ::swap(bounds_, node.bounds_);
     34  }
     35};
     36
     37class CbcHeuristicNodeList {
     38private:
     39  std::vector<CbcHeuristicNode*> nodes_;
     40public:
     41  CbcHeuristicNodeList() {}
     42  CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
     43  CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
     44  ~CbcHeuristicNodeList() {
     45    for (int i = nodes_.size() - 1; i >= 0; --i) {
     46      delete nodes_[i];
     47    }
     48  }
     49
     50  bool farFrom(const CbcHeuristicNode& node);
     51  void append(CbcHeuristicNode*& node) {
     52    nodes_.push_back(node);
     53    node = NULL;
     54  }
     55  void append(CbcHeuristicNodeList& nodes) {
     56    nodes_.insert(nodes_.end(), nodes.begin(), nodes.end());
     57    nodes.clear();
     58  }
     59};
     60
     61//#############################################################################
    1762/** Heuristic base class */
    1863
     
    4893  */
    4994  virtual int solution(double & objectiveValue,
    50                        double * newSolution)=0;
     95                       double * newSolution,
     96                       CbcHeuristicInfo* info = NULL)=0;
    5197
    5298  /** returns 0 if no solution, 1 if valid solution, -1 if just
     
    59105  virtual int solution(double & objectiveValue,
    60106                       double * newSolution,
    61                        OsiCuts & cs) {return 0;}
     107                       OsiCuts & cs,
     108                       CbcHeuristicInfo* info = NULL) {return 0;}
    62109
    63110  /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
     
    140187  /// Name for printing
    141188  std::string heuristicName_;
    142  
     189  /// How often to do (code can change)
     190  int howOften_;
     191  /// How much to increase how often
     192  double decayFactor_;
     193  /// The description of the nodes where this heuristic has been applied
     194  CbcHeuristicNode* runNodes_;
     195#if 0
     196  /// Lower bounds of last node where the heuristic found a solution
     197  double * lowerBoundLastNode_;
     198  /// Upper bounds of last node where the heuristic found a solution
     199  double * upperBoundLastNode_;
     200#endif
    143201};
    144202/** Rounding class
  • branches/heur/Cbc/src/CbcHeuristicDiveCoefficient.cpp

    r873 r884  
    3434  if (matrix) {
    3535    matrix_ = *matrix;
     36    validate();
    3637  }
    3738  percentageToFix_ = 0.2;
     
    143144                                     double * betterSolution)
    144145{
    145 
     146  if (model_->getCurrentPassNumber() != 1) {
     147    return NULL;
     148  }
     149 
     150  const int nodeCount = model_->getNodeCount();  // FIXME: check that this is correct in parallel
     151  CbcHeuristicNode* nodeDesc = NULL;
     152  if (nodeCount != 0) {
     153    if (nodeCount - lastRun_ < howOften_) {
     154      return NULL;
     155    }
     156
     157    // Get where we are and create the appropriate CbcHeuristicNode object
     158    nodeDesc = new CbcHeuristicNode(model_);
     159    if (!nodes_.farFrom(nodeDesc)) {
     160      delete nodeDesc;
     161      return NULL;
     162    }
     163  }
     164
     165#if 0
    146166  // See if to do
    147167  if (!when()||(when()%10==1&&model_->phase()!=1)||
    148168      (when()%10==2&&(model_->phase()!=2&&model_->phase()!=3)))
    149169    return 0; // switched off
     170#endif
    150171
    151172  double time1 = CoinCpuTime();
     
    366387  }
    367388
     389  bool updateHowOften = false;
     390  // Good question when... every time the heur was run? every time it
     391  // has found a solution? every time it has found a better solution?
     392  // for now update every time
     393  updateHowOften = true;
    368394
    369395  double * rowActivity = new double[numberRows];
     
    417443      //printf("** Solution of %g found by CbcHeuristicDiveCoefficient\n",newSolutionValue);
    418444      returnCode=1;
    419     } else {
    420       // Can easily happen
    421       //printf("Debug CbcHeuristicDiveCoefficient giving bad solution\n");
    422     }
    423   }
     445
     446      setCurrentNode(model_->solver());
     447    }
     448  }
     449
     450  if (updateHowOften) {
     451    howOften_ += (int) (howOften_*decayFactor_);
     452  }
     453   
    424454
    425455  delete [] newSolution;
     
    429459  delete [] rowActivity;
    430460  delete solver;
     461  delete nodeDesc;
    431462  return returnCode;
    432463}
Note: See TracChangeset for help on using the changeset viewer.