Changeset 137


Ignore:
Timestamp:
May 19, 2005 3:02:30 PM (15 years ago)
Author:
forrest
Message:

fiddling with strong branching

Location:
trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcBranchDynamic.cpp

    r135 r137  
    237237    below = above -1;
    238238  }
     239#define INFEAS
     240#ifdef INFEAS
     241  double distanceToCutoff=0.0;
    239242  double objectiveValue = solver->getObjSense()*solver->getObjValue();
    240   double distanceToCutoff =  model_->getCutoff()<1.0e20 - objectiveValue;
     243  distanceToCutoff =  model_->getCutoff() - objectiveValue;
    241244  if (distanceToCutoff<1.0e20)
    242245    distanceToCutoff *= 10.0;
    243246  else
    244247    distanceToCutoff = 1.0e2 + fabs(objectiveValue);
     248#endif
    245249  double sum;
    246250  int number;
     
    248252  sum = sumDownCost();
    249253  number = numberTimesDown();
     254#ifdef INFEAS
    250255  sum += numberTimesDownInfeasible()*(distanceToCutoff/(downCost+1.0e-12));
     256#endif
    251257  if (number>0)
    252258    downCost *= sum / (double) number;
     
    256262  sum = sumUpCost();
    257263  number = numberTimesUp();
     264#ifdef INFEAS
    258265  sum += numberTimesUpInfeasible()*(distanceToCutoff/(upCost+1.0e-12));
     266#endif
    259267  if (number>0)
    260268    upCost *= sum / (double) number;
     
    391399    }
    392400    double objectiveValue = solver->getObjSense()*solver->getObjValue();
    393     double distanceToCutoff =  model_->getCutoff()<1.0e20 - objectiveValue;
     401    double distanceToCutoff =  model_->getCutoff() - objectiveValue;
    394402    if (distanceToCutoff<1.0e20)
    395403      distanceToCutoff *= 10.0;
  • trunk/CbcModel.cpp

    r136 r137  
    548548  int numberOldActiveCuts = 0 ;
    549549  int numberNewCuts = 0 ;
     550  // Array to mark solution
     551  usedInSolution_ = new int[numberColumns];
     552  CoinZeroN(usedInSolution_,numberColumns);
    550553  { int iObject ;
    551554    int preferredWay ;
     
    680683  if (newNode)
    681684  { continuousObjective_ = newNode->objectiveValue() ;
     685    continuousSolution_ = CoinCopyOfArray(solver_->getColSolution(),
     686                                             numberColumns);
    682687    continuousInfeasibilities_ = newNode->numberUnsatisfied() ; }
    683688/*
     
    10561061            { double saveValue = heurValue ;
    10571062              int ifSol = heuristic_[iHeur]->solution(heurValue,newSolution) ;
    1058               if (ifSol > 0)    // new solution found
    1059               { found = iHeur ; }
     1063              if (ifSol > 0) {
     1064                // new solution found
     1065                found = iHeur ;
     1066                incrementUsed(newSolution);
     1067              }
    10601068              else
    10611069              if (ifSol < 0)    // just returning an estimate
     
    10791087            setBestSolution(CBC_SOLUTION,objectiveValue,
    10801088                            solver_->getColSolution()) ;
     1089            incrementUsed(solver_->getColSolution());
    10811090            assert(nodeInfo->numberPointingToThis() <= 2) ;
    10821091            // avoid accidental pruning, if newNode was final branch arm
     
    12971306  currentNode_(NULL),
    12981307  integerVariable_(NULL),
     1308  continuousSolution_(NULL),
     1309  usedInSolution_(NULL),
    12991310  specialOptions_(0),
    13001311  subTreeModel_(NULL),
     
    13031314  numberStrong_(5),
    13041315  numberBeforeTrust_(0),
     1316  numberInfeasibleNodes_(0),
    13051317  problemType_(0),
    13061318  printFrequency_(0),
     
    13821394  numberStrong_(5),
    13831395  numberBeforeTrust_(0),
     1396  numberInfeasibleNodes_(0),
    13841397  problemType_(0),
    13851398  printFrequency_(0),
     
    14331446    // Space for current solution
    14341447    currentSolution_ = new double[numberColumns];
     1448    continuousSolution_ = new double[numberColumns];
     1449    usedInSolution_ = new int[numberColumns];
    14351450    for (iColumn=0;iColumn<numberColumns;iColumn++) {
    14361451      if( solver_->isInteger(iColumn))
     
    14401455    // empty model
    14411456    currentSolution_=NULL;
     1457    continuousSolution_=NULL;
     1458    usedInSolution_=NULL;
    14421459  }
    14431460  testSolution_=currentSolution_;
     
    15441561  numberStrong_(rhs.numberStrong_),
    15451562  numberBeforeTrust_(rhs.numberBeforeTrust_),
     1563  numberInfeasibleNodes_(rhs.numberInfeasibleNodes_),
    15461564  problemType_(rhs.problemType_),
    15471565  printFrequency_(rhs.printFrequency_),
     
    16461664    bestSolution_=NULL;
    16471665  }
    1648   if (rhs.currentSolution_&&!noTree) {
     1666  if (!noTree) {
    16491667    int numberColumns = solver_->getNumCols();
    1650     currentSolution_ = new double[numberColumns];
    1651     memcpy(currentSolution_,rhs.currentSolution_,numberColumns*sizeof(double));
     1668    currentSolution_ = CoinCopyOfArray(rhs.currentSolution_,numberColumns);
     1669    continuousSolution_ = CoinCopyOfArray(rhs.continuousSolution_,numberColumns);
     1670    usedInSolution_ = CoinCopyOfArray(rhs.usedInSolution_,numberColumns);
    16521671  } else {
    16531672    currentSolution_=NULL;
     1673    continuousSolution_=NULL;
     1674    usedInSolution_=NULL;
    16541675  }
    16551676  testSolution_=currentSolution_;
     
    17441765      bestSolution_=NULL;
    17451766    }
    1746     if (rhs.currentSolution_) {
    1747       int numberColumns = rhs.getNumCols();
    1748       currentSolution_ = new double[numberColumns];
    1749       memcpy(currentSolution_,rhs.currentSolution_,numberColumns*sizeof(double));
    1750     } else {
    1751       currentSolution_=NULL;
    1752     }
     1767    int numberColumns = solver_->getNumCols();
     1768    currentSolution_ = CoinCopyOfArray(rhs.currentSolution_,numberColumns);
     1769    continuousSolution_ = CoinCopyOfArray(rhs.continuousSolution_,numberColumns);
     1770    usedInSolution_ = CoinCopyOfArray(rhs.usedInSolution_,numberColumns);
    17531771    testSolution_=currentSolution_;
    17541772    minimumDrop_ = rhs.minimumDrop_;
     
    17661784    numberStrong_ = rhs.numberStrong_;
    17671785    numberBeforeTrust_ = rhs.numberBeforeTrust_;
     1786    numberInfeasibleNodes_ = rhs.numberInfeasibleNodes_;
    17681787    problemType_ = rhs.problemType_;
    17691788    printFrequency_ = rhs.printFrequency_;
     
    24052424  }
    24062425
    2407   if (!feasible) return (false) ;
     2426  if (!feasible) {
     2427    numberInfeasibleNodes_++;
     2428    return (false) ;
     2429  }
    24082430  sumChangeObjective1_ += solver_->getObjValue()*solver_->getObjSense()
    24092431    - objectiveValue ;
     
    25972619          // better solution found
    25982620          found = i ;
     2621          incrementUsed(newSolution);
    25992622        } else if (ifSol<0) {
    26002623          heuristicValue = saveValue ;
     
    26752698          // better solution found
    26762699          found = i ;
     2700          incrementUsed(newSolution);
    26772701        } else {
    26782702          heuristicValue = saveValue ;
     
    26892713    {
    26902714      phase_=4;
     2715      incrementUsed(newSolution);
    26912716      setBestSolution(CBC_ROUNDING,heuristicValue,newSolution) ; }
    26922717    delete [] newSolution ;
     
    29532978        // better solution found
    29542979        found = i ;
     2980        incrementUsed(newSolution);
    29552981      } else {
    29562982        heuristicValue = saveValue ;
     
    29602986    if (found >= 0) {
    29612987      phase_=4;
     2988      incrementUsed(newSolution);
    29622989      setBestSolution(CBC_ROUNDING,heuristicValue,newSolution) ;
    29632990    }
     
    48484875            // better solution found
    48494876            found=iHeuristic;
     4877            incrementUsed(newSolution);
    48504878          } else if (ifSol<0) {
    48514879            heuristicValue = saveValue;
     
    55425570  strategy_ = strategy.clone();
    55435571}
     5572// Increases usedInSolution for nonzeros
     5573void
     5574CbcModel::incrementUsed(const double * solution)
     5575{
     5576  // might as well mark all including continuous
     5577  int numberColumns = solver_->getNumCols();
     5578  for (int i=0;i<numberColumns;i++) {
     5579    if (solution[i])
     5580      usedInSolution_[i]++;
     5581  }
     5582}
  • trunk/CbcNode.cpp

    r135 r137  
    13581358                                       newObjectiveValue,
    13591359                                       solver->getColSolution()) ;
     1360              model->incrementUsed(solver->getColSolution());
    13601361              if (newObjectiveValue >= model->getCutoff())      //  *new* cutoff
    13611362                objectiveChange = 1.0e100 ;
     
    14411442                                       newObjectiveValue,
    14421443                                       solver->getColSolution()) ;
     1444              model->incrementUsed(solver->getColSolution());
    14431445              if (newObjectiveValue >= model->getCutoff())      //  *new* cutoff
    14441446                objectiveChange = 1.0e100 ;
     
    19581960        int canSkip = choice.possibleBranch->fillStrongInfo(choice);
    19591961        // For now always do
    1960         canSkip=false;
     1962        //canSkip=false;
    19611963        if (model->messageHandler()->logLevel()>3)
    19621964          dynamicObject->print(1,choice.possibleBranch->value());
     
    20062008                                       newObjectiveValue,
    20072009                                       solver->getColSolution()) ;
     2010                model->incrementUsed(solver->getColSolution());
    20082011                if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
    20092012                  objectiveChange = 1.0e100 ;
     
    20632066                                       newObjectiveValue,
    20642067                                       solver->getColSolution()) ;
     2068                model->incrementUsed(solver->getColSolution());
    20652069                if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
    20662070                  objectiveChange = 1.0e100 ;
  • trunk/include/CbcModel.hpp

    r135 r137  
    747747  /**@name Methods related to querying the solution */
    748748  //@{
     749  /// Holds solution at continuous (after cuts)
     750  inline double * continuousSolution() const
     751  { return continuousSolution_;};
     752  /** Array marked whenever a solution is found if non-zero.
     753      Code marks if heuristic returns better so heuristic
     754      need only mark if it wants to on solutions which
     755      are worse than current */
     756  inline int * usedInSolution() const
     757  { return usedInSolution_;};
     758  /// Increases usedInSolution for nonzeros
     759  void incrementUsed(const double * solution);
    749760  /// Record a new incumbent solution and update objectiveValue
    750761  void setBestSolution(CBC_Message how,
     
    13421353  /// Indices of integer variables
    13431354  int * integerVariable_;
     1355  /// Holds solution at continuous (after cuts)
     1356  double * continuousSolution_;
     1357  /// Array marked whenever a solution is found if non-zero
     1358  int * usedInSolution_;
    13441359  /// 0 bit - check if cuts valid (if on list)
    13451360  int specialOptions_;
     
    13741389      in dynamic strong branching. (0 off) */
    13751390  int numberBeforeTrust_;
     1391  /// Number of nodes infeasible by normal branching (before cuts)
     1392  int numberInfeasibleNodes_;
    13761393  /** Problem type as set by user or found by analysis.  This will be extended
    13771394      0 - not known
Note: See TracChangeset for help on using the changeset viewer.