Changeset 54


Ignore:
Timestamp:
Jan 28, 2005 10:55:35 AM (16 years ago)
Author:
forrest
Message:

add getBestPossibleObjective for Matt Galati

Location:
trunk
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcMessage.cpp

    r49 r54  
    2121  {CBC_MAXSOLS,19,1,"Exiting on maximum solutions"},
    2222  {CBC_SOLUTION,4,1,"Integer solution of %g found after %d iterations and %d nodes"},
    23   {CBC_END,5,1,"Partial search - best objective %g, took %d iterations and %d nodes"},
     23  {CBC_END,5,1,"Partial search - best objective %g (best possible %g), took %d iterations and %d nodes"},
    2424  {CBC_INFEAS,6,1,"The LP relaxation is infeasible or too expensive"},
    2525  {CBC_STRONG,7,3,"Strong branching on %d (%d), down %g (%d) up %g (%d) value %g"},
  • trunk/CbcModel.cpp

    r53 r54  
    422422  // Save objective (just so user can access it)
    423423  originalContinuousObjective_ = solver_->getObjValue();
     424  bestPossibleObjective_=originalContinuousObjective_;
    424425
    425426# ifdef CBC_DEBUG
     
    722723  { if (cutoff > getCutoff()) {
    723724      // Do from deepest
    724       tree_->cleanTree(this, getCutoff()) ;
     725      tree_->cleanTree(this, getCutoff(),bestPossibleObjective_) ;
    725726      if (!nodeCompare_) {
    726727        if (!compareDefault.getWeight()) {
     
    760761      int j ;
    761762      int nNodes = tree_->size() ;
    762       bestValue = 1.0e100 ;
     763      bestPossibleObjective_ = 1.0e100 ;
    763764      for (j = 0;j < nNodes;j++) {
    764765        CbcNode * node = tree_->nodePointer(j) ;
    765         if (node->objectiveValue() < bestValue)
    766           bestValue = node->objectiveValue() ;
     766        if (node->objectiveValue() < bestPossibleObjective_)
     767          bestPossibleObjective_ = node->objectiveValue() ;
    767768      }
    768769      messageHandler()->message(CBC_STATUS,messages())
    769         << numberNodes_<< nNodes<< bestObjective_<< bestValue
     770        << numberNodes_<< nNodes<< bestObjective_<< bestPossibleObjective_
    770771        << CoinMessageEol ;
    771772    }
    772773    // See if can stop on gap
    773774    double testGap = CoinMax(dblParam_[CbcAllowableGap],
    774                              CoinMax(fabs(bestObjective_),fabs(bestValue))
     775                             CoinMax(fabs(bestObjective_),fabs(bestPossibleObjective_))
    775776                             *dblParam_[CbcAllowableFractionGap]);
    776     if (bestObjective_-bestValue < testGap) {
     777    if (bestObjective_-bestPossibleObjective_ < testGap) {
    777778      stoppedOnGap = true ;
    778779    }
     
    10611062      else
    10621063      {
    1063         tree_->cleanTree(this,-COIN_DBL_MAX) ;
     1064        tree_->cleanTree(this,-COIN_DBL_MAX,bestPossibleObjective_) ;
    10641065        delete nextRowCut_;
    10651066        // We need to get rid of node if is has already been popped from tree
     
    10681069        if (stoppedOnGap)
    10691070        { messageHandler()->message(CBC_GAP,messages())
    1070             << bestObjective_-bestValue
     1071            << bestObjective_-bestPossibleObjective_
    10711072            << dblParam_[CbcAllowableGap]
    10721073            << dblParam_[CbcAllowableFractionGap]*100.0
     
    11161117  if ( numberStoppedSubTrees_)
    11171118    status_=1;
    1118   if (!status_)
     1119  if (!status_) {
     1120    bestPossibleObjective_=bestObjective_;
    11191121    handler_->message(CBC_END_GOOD,messages_)
    11201122      << bestObjective_ << numberIterations_ << numberNodes_
    11211123      << CoinMessageEol ;
    1122   else
     1124  } else {
    11231125    handler_->message(CBC_END,messages_)
    1124       << bestObjective_ << numberIterations_ << numberNodes_
     1126      << bestObjective_ <<bestPossibleObjective_
     1127      << numberIterations_ << numberNodes_
    11251128      << CoinMessageEol ;
     1129  }
    11261130/*
    11271131  If we think we have a solution, restore and confirm it with a call to
     
    12331237  basis_(NULL),
    12341238  bestObjective_(COIN_DBL_MAX),
     1239  bestPossibleObjective_(COIN_DBL_MAX),
    12351240  bestSolution_(NULL),
    12361241  currentSolution_(NULL),
     
    13091314  basis_(NULL) ,
    13101315  bestObjective_(COIN_DBL_MAX),
     1316  bestPossibleObjective_(COIN_DBL_MAX),
    13111317  minimumDrop_(1.0e-4),
    13121318  numberSolutions_(0),
     
    14721478  basis_(NULL),
    14731479  bestObjective_(rhs.bestObjective_),
     1480  bestPossibleObjective_(rhs.bestPossibleObjective_),
    14741481  minimumDrop_(rhs.minimumDrop_),
    14751482  numberSolutions_(rhs.numberSolutions_),
     
    16111618    continuousInfeasibilities_=INT_MAX;
    16121619    maximumNumberCuts_=0;
    1613     tree_->cleanTree(this,-COIN_DBL_MAX);
     1620    tree_->cleanTree(this,-COIN_DBL_MAX,bestPossibleObjective_);
     1621    bestPossibleObjective_ = COIN_DBL_MAX;
    16141622  }
    16151623  // These are only used as temporary arrays so need not be filled
     
    16701678
    16711679    bestObjective_ = rhs.bestObjective_;
     1680    bestPossibleObjective_=rhs.bestPossibleObjective_;
    16721681    delete [] bestSolution_;
    16731682    if (rhs.bestSolution_) {
     
    51985207  bestObjective_=objectiveValue;
    51995208}
     5209double
     5210CbcModel::getBestPossibleObjValue() const
     5211{
     5212  return CoinMin(bestPossibleObjective_,bestObjective_) * solver_->getObjSense() ;
     5213}
  • trunk/CbcTree.cpp

    r2 r54  
    7575
    7676void
    77 CbcTree::cleanTree(CbcModel * model, double cutoff)
     77CbcTree::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
    7878{
    7979  int j;
     
    8383  int k=0;
    8484  int kDelete=nNodes;
     85  bestPossibleObjective = 1.0e100 ;
    8586/*
    8687    Destructively scan the heap. Nodes to be retained go into the front of
     
    9192    CbcNode * node = top();
    9293    pop();
    93     if (node->objectiveValue() >= cutoff) {
     94    double value = node->objectiveValue();
     95    bestPossibleObjective = CoinMin(bestPossibleObjective,value);
     96    if (value >= cutoff) {
    9497      nodeArray[--kDelete] = node;
    9598      depth[kDelete] = node->depth();
  • trunk/Samples/CbcTreeLocal.cpp

    r23 r54  
    402402  }
    403403  // get rid of all nodes (safe even if already done)
    404   cleanTree(model_,-COIN_DBL_MAX);
     404  double bestPossibleObjective;
     405  cleanTree(model_,-COIN_DBL_MAX,bestPossibleObjective);
    405406
    406407  double increment = model_->getDblParam(CbcModel::CbcCutoffIncrement) ;
  • trunk/include/CbcModel.hpp

    r53 r54  
    761761  inline double getObjValue() const
    762762  { return bestObjective_ * solver_->getObjSense() ; } ;
     763  /** Get best possible objective function value.
     764      This is better of best possible left on tree
     765      and best solution found.
     766      If called from within branch and cut may be optimistic.
     767  */
     768  double getBestPossibleObjValue() const;
    763769  /// Set best objective function value
    764770  inline void setObjValue(double value)
     
    11591165  /// Best objective
    11601166  double bestObjective_;
     1167  /// Best possible objective
     1168  double bestPossibleObjective_;
    11611169
    11621170  /// Array holding the incumbent (best) solution.
  • trunk/include/CbcTree.hpp

    r2 r54  
    7474  This routine removes all nodes with objective worst than the
    7575  specified cutoff value.
     76  It also sets bestPossibleObjective to best
     77  of all on tree before deleting.
    7678*/
    7779
    78   void cleanTree(CbcModel * model, double cutoff);
     80  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    7981
    8082  /// We may have got an intelligent tree so give it one more chance
Note: See TracChangeset for help on using the changeset viewer.