Changeset 944


Ignore:
Timestamp:
May 16, 2008 4:24:59 PM (11 years ago)
Author:
jpgoncal
Message:

Added reduced cost fixing.

Location:
trunk/Cbc/src
Files:
10 edited

Legend:

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

    r920 r944  
    1010#include  "CoinTime.hpp"
    1111
     12#ifdef COIN_HAS_CLP
     13#include "OsiClpSolverInterface.hpp"
     14#endif
     15
    1216//#define DIVE_FIX_BINARY_VARIABLES
     17//#define DIVE_DEBUG
    1318
    1419// Default Constructor
     
    2126  percentageToFix_ = 0.2;
    2227  maxIterations_ = 100;
    23   maxTime_ = 60;
     28  maxTime_ = 600;
    2429}
    2530
     
    4146  percentageToFix_ = 0.2;
    4247  maxIterations_ = 100;
    43   maxTime_ = 60;
     48  maxTime_ = 600;
    4449}
    4550
     
    6570  else
    6671    fprintf(fp,"4  %s.setMaxIterations(%d);\n",heuristic,maxIterations_);
    67   if (maxTime_!=60)
     72  if (maxTime_!=600)
    6873    fprintf(fp,"3  %s.setMaxTime(%.2f);\n",heuristic,maxTime_);
    6974  else
     
    170175                           double * betterSolution)
    171176{
     177#ifdef DIVE_DEBUG
     178  std::cout<<"solutionValue = "<<solutionValue<<std::endl;
     179#endif
    172180  ++numCouldRun_;
    173181
     
    181189      (when()%10==2&&(model_->phase()!=2&&model_->phase()!=3)))
    182190    return 0; // switched off
     191#endif
     192
     193#ifdef DIVE_DEBUG
     194  int nRoundInfeasible = 0;
     195  int nRoundFeasible = 0;
     196  int reasonToStop = 0;
    183197#endif
    184198
     
    246260
    247261    // select a fractional variable to bound
    248     int bestColumn;
     262    int bestColumn = -1;
    249263    int bestRound; // -1 rounds down, +1 rounds up
    250     selectVariableToBranch(solver, newSolution, bestColumn, bestRound);
    251 
    252     bool canRoundSolution = true;
    253     // if it selected a variable to branch it is because that variable
    254     // cannot be trivially rounded (i.e., it has down and up locks)
    255     if(bestColumn != -1)
    256       canRoundSolution = false;
     264    bool canRound = selectVariableToBranch(solver, newSolution,
     265                                           bestColumn, bestRound);
     266
     267    // if the solution is not trivially roundable, we don't try to round;
     268    // if the solution is trivially roundable, we try to round. However,
     269    // if the rounded solution is worse than the current incumbent,
     270    // then we don't round and proceed normally. In this case, the
     271    // bestColumn will be a trivially roundable variable
     272    if(canRound) {
     273      // check if by rounding all fractional variables
     274      // we get a solution with an objective value
     275      // better than the current best integer solution
     276      double delta = 0.0;
     277      for (int i=0; i<numberIntegers; i++) {
     278        int iColumn = integerVariable[i];
     279        double value=newSolution[iColumn];
     280        if (fabs(floor(value+0.5)-value)>integerTolerance) {
     281          assert(downLocks_[i]==0 || upLocks_[i]==0);
     282          double obj = objective[iColumn];
     283          if(downLocks_[i]==0 && upLocks_[i]==0) {
     284            if(direction * obj >= 0.0)
     285              delta += (floor(value) - value) * obj;
     286            else
     287              delta += (ceil(value) - value) * obj;
     288          }
     289          else if(downLocks_[i]==0)
     290            delta += (floor(value) - value) * obj;
     291          else
     292            delta += (ceil(value) - value) * obj;
     293        }
     294      }
     295      if(direction*(solver->getObjValue()+delta) < solutionValue) {
     296#ifdef DIVE_DEBUG
     297        nRoundFeasible++;
     298#endif
     299        // Round all the fractional variables
     300        for (int i=0; i<numberIntegers; i++) {
     301          int iColumn = integerVariable[i];
     302          double value=newSolution[iColumn];
     303          if (fabs(floor(value+0.5)-value)>integerTolerance) {
     304            assert(downLocks_[i]==0 || upLocks_[i]==0);
     305            if(downLocks_[i]==0 && upLocks_[i]==0) {
     306              if(direction * objective[iColumn] >= 0.0)
     307                newSolution[iColumn] = floor(value);
     308              else
     309                newSolution[iColumn] = ceil(value);
     310            }
     311            else if(downLocks_[i]==0)
     312              newSolution[iColumn] = floor(value);
     313            else
     314              newSolution[iColumn] = ceil(value);
     315          }
     316        }
     317        break;
     318      }
     319#ifdef DIVE_DEBUG
     320      else
     321        nRoundInfeasible++;
     322#endif
     323    }
     324
     325    // do reduced cost fixing
     326    int numberFixed = reducedCostFix(solver);
     327#ifdef DIVE_DEBUG
     328    std::cout<<"numberReducedCostFixed = "<<numberFixed<<std::endl;
     329#endif
    257330     
     331    int numberAtBoundFixed = 0;
     332#ifdef DIVE_FIX_BINARY_VARIABLES
    258333    // fix binary variables based on pseudo reduced cost
    259     int numberAtBoundFixed = 0;
    260 #if 0
    261     // This version uses generalized upper bounds. It doesn't seem to be working.
    262334    if(binVarIndex_.size()) {
    263335      int cnt = 0;
     
    268340        if(fabs(value)<=integerTolerance &&
    269341           lower[iColumn1] != upper[iColumn1]) {
    270           //      std::cout<<"iColumn1 = "<<iColumn1<<", value = "<<value<<std::endl;
     342#ifdef DIVE_DEBUG
     343          std::cout<<"iColumn1 = "<<iColumn1<<", value = "<<value<<std::endl;
     344#endif
    271345          int iRow = vbRowIndex_[j];
    272346          for (int k=rowStart[iRow];k<rowStart[iRow]+rowLength[iRow];k++) {
    273347            int iColumn2 = column[k];
    274             //      std::cout<<"iColumn2 = "<<iColumn2<<std::endl;
     348#ifdef DIVE_DEBUG
     349            std::cout<<"iColumn2 = "<<iColumn2<<std::endl;
     350#endif
    275351            if(iColumn1 != iColumn2) {
    276352              double pseudoReducedCost = fabs(reducedCost[iColumn2] *
    277353                                              elementByRow[iColumn2] /
    278354                                              elementByRow[iColumn1]);
    279               //              std::cout<<"reducedCost["<<iColumn2<<"] = "
    280               //                       <<reducedCost[iColumn2]
    281               //                       <<", elementByRow["<<iColumn2<<"] = "<<elementByRow[iColumn2]
    282               //                       <<", elementByRow["<<iColumn1<<"] = "<<elementByRow[iColumn1]
    283               //                       <<", pseudoRedCost = "<<pseudoReducedCost
    284               //                       <<std::endl;
     355#ifdef DIVE_DEBUG
     356              std::cout<<"reducedCost["<<iColumn2<<"] = "
     357                       <<reducedCost[iColumn2]
     358                       <<", elementByRow["<<iColumn2<<"] = "<<elementByRow[iColumn2]
     359                       <<", elementByRow["<<iColumn1<<"] = "<<elementByRow[iColumn1]
     360                       <<", pseudoRedCost = "<<pseudoReducedCost
     361                       <<std::endl;
     362#endif
    285363              if(pseudoReducedCost > maxPseudoReducedCost)
    286364                maxPseudoReducedCost = pseudoReducedCost;
    287365            }
    288366          }
    289           //      std::cout<<", maxPseudoRedCost = "<<maxPseudoReducedCost<<std::endl;
     367#ifdef DIVE_DEBUG
     368          std::cout<<", maxPseudoRedCost = "<<maxPseudoReducedCost<<std::endl;
     369#endif
    290370          candidate[cnt].var = iColumn1;
    291371          candidate[cnt++].pseudoRedCost = maxPseudoReducedCost;
    292372        }
    293373      }
    294       //      std::cout<<"candidates for rounding = "<<cnt<<std::endl;
     374#ifdef DIVE_DEBUG
     375      std::cout<<"candidates for rounding = "<<cnt<<std::endl;
     376#endif
    295377      std::sort(candidate, candidate+cnt, compareBinaryVars);
    296378      for (int i=0; i<cnt; i++) {
     
    307389      }
    308390    }
    309 #else
    310 // THIS ONLY USES variable upper bound constraints with 1 continuous variable
    311     if(binVarIndex_.size()) {
    312       int cnt = 0;
    313       for (int j=0; j<(int)binVarIndex_.size(); j++) {
    314         int iColumn = binVarIndex_[j];
    315         double value = newSolution[iColumn];
    316         double pseudoReducedCost = 0.0;
    317         if(fabs(value)<=integerTolerance &&
    318            lower[iColumn] != upper[iColumn]) {
    319           //      std::cout<<"iColumn = "<<iColumn<<", value = "<<value<<std::endl;
    320           int iRow = vbRowIndex_[j];
    321           assert(rowLength[iRow]==2);
    322           int k=rowStart[iRow];
    323           if(iColumn == column[k]) {
    324             pseudoReducedCost = fabs(reducedCost[column[k+1]] *
    325                                      elementByRow[k+1] /
    326                                      elementByRow[k]);
    327             //      std::cout<<"reducedCost["<<column[k+1]<<"] = "
    328             //               <<reducedCost[column[k+1]]
    329             //               <<", elementByRow["<<k+1<<"] = "<<elementByRow[k+1]
    330             //               <<", elementByRow["<<k<<"] = "<<elementByRow[k];
    331           }
    332           else {
    333             pseudoReducedCost = fabs(reducedCost[column[k]] *
    334                                      elementByRow[k] /
    335                                      elementByRow[k+1]);
    336             //      std::cout<<"reducedCost["<<column[k]<<"] = "
    337             //               <<reducedCost[column[k]]
    338             //               <<", elementByRow["<<k<<"] = "<<elementByRow[k]
    339             //               <<", elementByRow["<<k+1<<"] = "<<elementByRow[k+1];
    340           }
    341           //      std::cout<<", pseudoRedCost = "<<pseudoReducedCost<<std::endl;
    342           candidate[cnt].var = iColumn;
    343           candidate[cnt++].pseudoRedCost = pseudoReducedCost;
    344         }
    345       }
    346       //      std::cout<<"candidates for rounding = "<<cnt<<std::endl;
    347       std::sort(candidate, candidate+cnt, compareBinaryVars);
    348       for (int i=0; i<cnt; i++) {
    349         int iColumn = candidate[i].var;
    350         if (numberAtBoundFixed < maxNumberAtBoundToFix) {
    351           columnFixed[numberAtBoundFixed] = iColumn;
    352           originalBound[numberAtBoundFixed] = upper[iColumn];
    353           fixedAtLowerBound[numberAtBoundFixed] = true;
    354           solver->setColUpper(iColumn, lower[iColumn]);
    355           numberAtBoundFixed++;
    356           if(numberAtBoundFixed == maxNumberAtBoundToFix)
    357             break;
    358         }
    359       }
    360     }
    361 #endif
    362     //    std::cout<<"numberAtBoundFixed = "<<numberAtBoundFixed<<std::endl;
    363 
    364     // fix other integer variables that are at there bounds
     391#endif
     392
     393    // fix other integer variables that are at their bounds
    365394    for (int i=0; i<numberIntegers; i++) {
    366395      int iColumn = integerVariable[i];
     
    389418      }
    390419    }
    391 
    392     if(canRoundSolution) {
    393       // Round all the fractional variables
    394       for (int i=0; i<numberIntegers; i++) {
    395         int iColumn = integerVariable[i];
    396         double value=newSolution[iColumn];
    397         if (fabs(floor(value+0.5)-value)>integerTolerance) {
    398           if(downLocks_[i]==0 || upLocks_[i]==0) {
    399             if(downLocks_[i]==0 && upLocks_[i]==0) {
    400               if(direction * objective[iColumn] >= 0.0)
    401                 newSolution[iColumn] = floor(value);
    402               else
    403                 newSolution[iColumn] = ceil(value);
    404             }
    405             else if(downLocks_[i]==0)
    406               newSolution[iColumn] = floor(value);
    407             else
    408               newSolution[iColumn] = ceil(value);
    409           }
    410           else
    411             break;
    412         }
    413       }
    414       break;
    415     }
    416 
     420#ifdef DIVE_DEBUG
     421    std::cout<<"numberAtBoundFixed = "<<numberAtBoundFixed<<std::endl;
     422#endif
    417423
    418424    double originalBoundBestColumn;
     
    465471
    466472    if(!solver->isProvenOptimal() ||
    467        direction*solver->getObjValue() >= solutionValue)
     473       direction*solver->getObjValue() >= solutionValue) {
     474#ifdef DIVE_DEBUG
     475      reasonToStop = 1;
     476#endif
    468477      break;
     478    }
    469479
    470480    if(iteration > maxIterations_) {
     481#ifdef DIVE_DEBUG
     482      reasonToStop = 2;
     483#endif
    471484      break;
    472485    }
    473486
    474487    if(CoinCpuTime()-time1 > maxTime_) {
     488#ifdef DIVE_DEBUG
     489      reasonToStop = 3;
     490#endif
    475491      break;
    476492    }
     
    544560    }
    545561  }
     562
     563#ifdef DIVE_DEBUG
     564  std::cout<<"nRoundInfeasible = "<<nRoundInfeasible
     565           <<", nRoundFeasible = "<<nRoundFeasible
     566           <<", returnCode = "<<returnCode
     567           <<", reasonToStop = "<<reasonToStop
     568           <<", iterations = "<<iteration<<std::endl;
     569#endif
    546570
    547571  delete [] newSolution;
     
    613637}
    614638
    615 #if 0
    616 // This version uses generalized upper bounds. It doesn't seem to be working.
    617 
    618639// Select candidate binary variables for fixing
    619640void
     
    646667
    647668  for(int i=0; i<numberRows; i++) {
    648     int binVar = -1;
    649     int numIntegers = 0;
    650     int numContinuous = 0;
     669    int positiveBinary = -1;
     670    int negativeBinary = -1;
     671    int nPositiveOther = 0;
     672    int nNegativeOther = 0;
    651673    for (int k=rowStart[i];k<rowStart[i]+rowLength[i];k++) {
    652674      int iColumn = column[k];
    653       if(model_->solver()->isInteger(iColumn)) {
    654         numIntegers++;
    655         if(numIntegers > 1)
    656           break;
    657         if(lower[iColumn] == 0.0 && upper[iColumn] == 1.0 &&
    658            objective[iColumn] == 0.0)
    659           binVar = iColumn;
    660       }
    661       else
    662         numContinuous++;
    663     }
    664     if(numIntegers == 1 && binVar >= 0 && numContinuous > 0 &&
    665        ((rowLower[i] == 0.0 && rowUpper[i] > 1.0e30) ||
    666         (rowLower[i] < -1.0e30 && rowUpper[i] == 0))) {
     675      if(model_->solver()->isInteger(iColumn) &&
     676         lower[iColumn] == 0.0 && upper[iColumn] == 1.0 &&
     677         objective[iColumn] == 0.0 &&
     678         elementByRow[k] > 0.0 &&
     679         positiveBinary < 0)
     680        positiveBinary = iColumn;
     681      else if(model_->solver()->isInteger(iColumn) &&
     682              lower[iColumn] == 0.0 && upper[iColumn] == 1.0 &&
     683              objective[iColumn] == 0.0 &&
     684              elementByRow[k] < 0.0 &&
     685              negativeBinary < 0)
     686        negativeBinary = iColumn;
     687      else if((elementByRow[k]> 0.0 &&
     688               lower[iColumn] >= 0.0) ||
     689              (elementByRow[k] < 0.0 &&
     690               upper[iColumn] <= 0.0))
     691        nPositiveOther++;
     692      else if((elementByRow[k]> 0.0 &&
     693               lower[iColumn] <= 0.0) ||
     694              (elementByRow[k] < 0.0 &&
     695               upper[iColumn] >= 0.0))
     696        nNegativeOther++;
     697      if(nPositiveOther > 0 && nNegativeOther > 0)
     698        break;
     699    }
     700    int binVar = -1;
     701    if(positiveBinary >= 0 &&
     702       (negativeBinary >= 0 || nNegativeOther > 0) &&
     703       nPositiveOther == 0 &&
     704       rowLower[i] == 0.0 &&
     705       rowUpper[i] > 0.0)
     706      binVar = positiveBinary;
     707    else if(negativeBinary >= 0 &&
     708            (positiveBinary >= 0 || nPositiveOther > 0) &&
     709            nNegativeOther == 0 &&
     710            rowLower[i] < 0.0 &&
     711            rowUpper[i] == 0.0)
     712      binVar = negativeBinary;
     713    if(binVar >= 0) {
    667714      if(rowIndexes[binVar] == -1)
    668715        rowIndexes[binVar] = i;
     
    679726  }
    680727
     728#ifdef DIVE_DEBUG
    681729  std::cout<<"number vub Binary = "<<binVarIndex_.size()<<std::endl;
     730#endif
    682731
    683732  delete [] rowIndexes;
     
    685734}
    686735
    687 #else
    688 // THIS ONLY USES variable upper bound constraints with 1 continuous variable
    689 
    690 // Select candidate binary variables for fixing
    691 void
    692 CbcHeuristicDive::selectBinaryVariables()
    693 {
    694   // Row copy
    695   const double * elementByRow = matrixByRow_.getElements();
    696   const int * column = matrixByRow_.getIndices();
    697   const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
    698   const int * rowLength = matrixByRow_.getVectorLengths();
    699 
    700   const int numberRows = matrixByRow_.getNumRows();
    701   const int numberCols = matrixByRow_.getNumCols();
    702 
    703   const double * lower = model_->solver()->getColLower();
    704   const double * upper = model_->solver()->getColUpper();
    705   const double * rowLower = model_->solver()->getRowLower();
    706   const double * rowUpper = model_->solver()->getRowUpper();
    707 
    708   //  const char * integerType = model_->integerType();
    709  
    710 
    711   //  const int numberIntegers = model_->numberIntegers();
    712   //  const int * integerVariable = model_->integerVariable();
    713   const double * objective = model_->solver()->getObjCoefficients();
    714 
    715   // vector to store the row number of variable bound rows
    716   int* rowIndexes = new int [numberCols];
    717   memset(rowIndexes, -1, numberCols*sizeof(int));
    718 
    719   for(int i=0; i<numberRows; i++) {
    720     int binVar = -1;
    721     int numContinuous = 0;
    722     if(rowLength[i] == 2) {
    723       int k = rowStart[i];
    724       int iColumn1 = column[k++];
    725       int iColumn2 = column[k];
    726       if(model_->solver()->isInteger(iColumn1) &&
    727          lower[iColumn1] == 0.0 && upper[iColumn1] == 1.0 &&
    728          objective[iColumn1] == 0.0 &&
    729          model_->solver()->isContinuous(iColumn2))
    730         binVar = iColumn1;
    731       else if(model_->solver()->isInteger(iColumn2) &&
    732               lower[iColumn2] == 0.0 && upper[iColumn2] == 1.0 &&
    733               objective[iColumn2] == 0.0 &&
    734               model_->solver()->isContinuous(iColumn1))
    735         binVar = iColumn2;
    736     }
    737     if(binVar >= 0 &&
    738        ((rowLower[i] == 0.0 && rowUpper[i] > 1.0e30) ||
    739         (rowLower[i] < -1.0e30 && rowUpper[i] == 0))) {
    740       if(rowIndexes[binVar] == -1)
    741         rowIndexes[binVar] = i;
    742       else if(rowIndexes[binVar] >= 0)
    743         rowIndexes[binVar] = -2;
    744     }
    745   }
    746 
    747   for(int j=0; j<numberCols; j++) {
    748     if(rowIndexes[j] >= 0) {
    749       binVarIndex_.push_back(j);
    750       vbRowIndex_.push_back(rowIndexes[j]);
    751     }
    752   }
    753 
    754   std::cout<<"number vub Binary = "<<binVarIndex_.size()<<std::endl;
    755 
    756   delete [] rowIndexes;
    757    
    758 }
    759 #endif
     736/*
     737  Perform reduced cost fixing on integer variables.
     738
     739  The variables in question are already nonbasic at bound. We're just nailing
     740  down the current situation.
     741*/
     742
     743int CbcHeuristicDive::reducedCostFix (OsiSolverInterface* solver)
     744
     745{
     746#if 0
     747  if(!solverCharacteristics_->reducedCostsAccurate())
     748    return 0; //NLP
     749#endif
     750  double cutoff = model_->getCutoff() ;
     751#ifdef DIVE_DEBUG
     752  std::cout<<"cutoff = "<<cutoff<<std::endl;
     753#endif
     754  double direction = solver->getObjSense() ;
     755  double gap = cutoff - solver->getObjValue()*direction ;
     756  double tolerance;
     757  solver->getDblParam(OsiDualTolerance,tolerance) ;
     758  if (gap<=0.0)
     759    gap = tolerance; //return 0;
     760  gap += 100.0*tolerance;
     761  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
     762
     763  const double *lower = solver->getColLower() ;
     764  const double *upper = solver->getColUpper() ;
     765  const double *solution = solver->getColSolution() ;
     766  const double *reducedCost = solver->getReducedCost() ;
     767
     768  int numberIntegers = model_->numberIntegers();
     769  const int * integerVariable = model_->integerVariable();
     770
     771  int numberFixed = 0 ;
     772
     773# ifdef COIN_HAS_CLP
     774  OsiClpSolverInterface * clpSolver
     775    = dynamic_cast<OsiClpSolverInterface *> (solver);
     776  ClpSimplex * clpSimplex=NULL;
     777  if (clpSolver)
     778    clpSimplex = clpSolver->getModelPtr();
     779# endif
     780  for (int i = 0 ; i < numberIntegers ; i++) {
     781    int iColumn = integerVariable[i] ;
     782    double djValue = direction*reducedCost[iColumn] ;
     783    if (upper[iColumn]-lower[iColumn] > integerTolerance) {
     784      if (solution[iColumn] < lower[iColumn]+integerTolerance && djValue > gap) {
     785#ifdef COIN_HAS_CLP
     786        // may just have been fixed before
     787        if (clpSimplex) {
     788          if (clpSimplex->getColumnStatus(iColumn)==ClpSimplex::basic) {
     789#ifdef COIN_DEVELOP
     790            printf("DJfix %d has status of %d, dj of %g gap %g, bounds %g %g\n",
     791                   iColumn,clpSimplex->getColumnStatus(iColumn),
     792                   djValue,gap,lower[iColumn],upper[iColumn]);
     793#endif
     794          } else {         
     795            assert(clpSimplex->getColumnStatus(iColumn)==ClpSimplex::atLowerBound||
     796                   clpSimplex->getColumnStatus(iColumn)==ClpSimplex::isFixed);
     797          }
     798        }
     799#endif
     800        solver->setColUpper(iColumn,lower[iColumn]) ;
     801        numberFixed++ ;
     802      } else if (solution[iColumn] > upper[iColumn]-integerTolerance && -djValue > gap) {
     803#ifdef COIN_HAS_CLP
     804        // may just have been fixed before
     805        if (clpSimplex) {
     806          if (clpSimplex->getColumnStatus(iColumn)==ClpSimplex::basic) {
     807#ifdef COIN_DEVELOP
     808            printf("DJfix %d has status of %d, dj of %g gap %g, bounds %g %g\n",
     809                   iColumn,clpSimplex->getColumnStatus(iColumn),
     810                   djValue,gap,lower[iColumn],upper[iColumn]);
     811#endif
     812          } else {         
     813            assert(clpSimplex->getColumnStatus(iColumn)==ClpSimplex::atUpperBound||
     814                   clpSimplex->getColumnStatus(iColumn)==ClpSimplex::isFixed);
     815          }
     816        }
     817#endif
     818        solver->setColLower(iColumn,upper[iColumn]) ;
     819        numberFixed++ ;
     820      }
     821    }
     822  }
     823  return numberFixed;
     824}
  • trunk/Cbc/src/CbcHeuristicDive.hpp

    r916 r944  
    7474
    7575  /// Selects the next variable to branch on
    76   virtual void selectVariableToBranch(OsiSolverInterface* solver,
     76  /** Returns true if all the fractional variables can be trivially
     77      rounded. Returns false, if there is at least one fractional variable
     78      that is not trivially roundable. In this case, the bestColumn
     79      returned will not be trivially roundable.
     80  */
     81  virtual bool selectVariableToBranch(OsiSolverInterface* solver,
    7782                                      const double* newSolution,
    7883                                      int& bestColumn,
    7984                                      int& bestRound) = 0;
     85
     86  /// Perform reduced cost fixing on integer variables
     87  int reducedCostFix (OsiSolverInterface* solver);
    8088
    8189protected:
  • trunk/Cbc/src/CbcHeuristicDiveCoefficient.cpp

    r912 r944  
    6363}
    6464
    65 void
     65bool
    6666CbcHeuristicDiveCoefficient::selectVariableToBranch(OsiSolverInterface* solver,
    6767                                                    const double* newSolution,
     
    7777  double bestFraction = DBL_MAX;
    7878  int bestLocks = COIN_INT_MAX;
     79  bool allTriviallyRoundableSoFar = true;
    7980  for (int i=0; i<numberIntegers; i++) {
    8081    int iColumn = integerVariable[i];
     
    8586      int nDownLocks = downLocks_[i];
    8687      int nUpLocks = upLocks_[i];
    87       if(nDownLocks>0 && nUpLocks>0) {
     88      if(allTriviallyRoundableSoFar||(nDownLocks>0 && nUpLocks>0)) {
     89
     90        if(allTriviallyRoundableSoFar&&nDownLocks>0 && nUpLocks>0) {
     91          allTriviallyRoundableSoFar = false;
     92          bestFraction = DBL_MAX;
     93          int bestLocks = COIN_INT_MAX;
     94        }
     95
    8896        // the variable cannot be rounded
    8997        int nLocks = nDownLocks;
     
    117125    }
    118126  }
     127  return allTriviallyRoundableSoFar;
    119128}
  • trunk/Cbc/src/CbcHeuristicDiveCoefficient.hpp

    r912 r944  
    3434
    3535  /// Selects the next variable to branch on
    36   virtual void selectVariableToBranch(OsiSolverInterface* solver,
     36  /** Returns true if all the fractional variables can be trivially
     37      rounded. Returns false, if there is at least one fractional variable
     38      that is not trivially roundable. In this case, the bestColumn
     39      returned will not be trivially roundable.
     40  */
     41  virtual bool selectVariableToBranch(OsiSolverInterface* solver,
    3742                                      const double* newSolution,
    3843                                      int& bestColumn,
  • trunk/Cbc/src/CbcHeuristicDiveFractional.cpp

    r912 r944  
    6161}
    6262
    63 void
     63bool
    6464CbcHeuristicDiveFractional::selectVariableToBranch(OsiSolverInterface* solver,
    6565                                                   const double* newSolution,
     
    7474  bestRound = -1; // -1 rounds down, +1 rounds up
    7575  double bestFraction = DBL_MAX;
     76  bool allTriviallyRoundableSoFar = true;
    7677  for (int i=0; i<numberIntegers; i++) {
    7778    int iColumn = integerVariable[i];
     
    8081    int round = 0;
    8182    if (fabs(floor(value+0.5)-value)>integerTolerance) {
    82       if(downLocks_[i]>0&&upLocks_[i]>0) {
    83           // the variable cannot be rounded
     83      if (allTriviallyRoundableSoFar||(downLocks_[i]>0&&upLocks_[i]>0)) {
     84
     85        if (allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {
     86          allTriviallyRoundableSoFar = false;
     87          bestFraction = DBL_MAX;
     88        }
     89
     90        // the variable cannot be rounded
    8491        if(fraction < 0.5)
    8592          round = -1;
     
    9198        // if variable is not binary, penalize it
    9299        if(!solver->isBinary(iColumn))
    93             fraction *= 1000.0;
     100          fraction *= 1000.0;
    94101       
    95102        if(fraction < bestFraction) {
     
    101108    }
    102109  }
     110  return allTriviallyRoundableSoFar;
    103111}
  • trunk/Cbc/src/CbcHeuristicDiveFractional.hpp

    r912 r944  
    3434
    3535  /// Selects the next variable to branch on
    36   virtual void selectVariableToBranch(OsiSolverInterface* solver,
     36  /** Returns true if all the fractional variables can be trivially
     37      rounded. Returns false, if there is at least one fractional variable
     38      that is not trivially roundable. In this case, the bestColumn
     39      returned will not be trivially roundable.
     40  */
     41  virtual bool selectVariableToBranch(OsiSolverInterface* solver,
    3742                                      const double* newSolution,
    3843                                      int& bestColumn,
  • trunk/Cbc/src/CbcHeuristicDiveGuided.cpp

    r912 r944  
    7171}
    7272
    73 void
     73bool
    7474CbcHeuristicDiveGuided::selectVariableToBranch(OsiSolverInterface* solver,
    75                                                    const double* newSolution,
    76                                                    int& bestColumn,
    77                                                    int& bestRound)
     75                                               const double* newSolution,
     76                                               int& bestColumn,
     77                                               int& bestRound)
    7878{
    7979  double* bestIntegerSolution = model_->bestSolution();
     
    8686  bestRound = -1; // -1 rounds down, +1 rounds up
    8787  double bestFraction = DBL_MAX;
     88  bool allTriviallyRoundableSoFar = true;
    8889  for (int i=0; i<numberIntegers; i++) {
    8990    int iColumn = integerVariable[i];
     
    9293    int round = 0;
    9394    if (fabs(floor(value+0.5)-value)>integerTolerance) {
    94       if(downLocks_[i]>0&&upLocks_[i]>0) {
    95         // the variable cannot be rounded
     95      if(allTriviallyRoundableSoFar||(downLocks_[i]>0&&upLocks_[i]>0)) {
     96
     97        if(allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {
     98          allTriviallyRoundableSoFar = false;
     99          bestFraction = DBL_MAX;
     100        }
     101
    96102        if(value >= bestIntegerSolution[iColumn])
    97103          round = -1;
     
    113119    }
    114120  }
     121  return allTriviallyRoundableSoFar;
    115122}
  • trunk/Cbc/src/CbcHeuristicDiveGuided.hpp

    r912 r944  
    3737
    3838  /// Selects the next variable to branch on
    39   virtual void selectVariableToBranch(OsiSolverInterface* solver,
     39  /** Returns true if all the fractional variables can be trivially
     40      rounded. Returns false, if there is at least one fractional variable
     41      that is not trivially roundable. In this case, the bestColumn
     42      returned will not be trivially roundable.
     43  */
     44  virtual bool selectVariableToBranch(OsiSolverInterface* solver,
    4045                                      const double* newSolution,
    4146                                      int& bestColumn,
  • trunk/Cbc/src/CbcHeuristicDiveVectorLength.cpp

    r912 r944  
    6161}
    6262
    63 void
     63bool
    6464CbcHeuristicDiveVectorLength::selectVariableToBranch(OsiSolverInterface* solver,
    6565                                                   const double* newSolution,
     
    7878  bestRound = -1; // -1 rounds down, +1 rounds up
    7979  double bestScore = DBL_MAX;
     80  bool allTriviallyRoundableSoFar = true;
    8081  for (int i=0; i<numberIntegers; i++) {
    8182    int iColumn = integerVariable[i];
     
    8485    int round = 0;
    8586    if (fabs(floor(value+0.5)-value)>integerTolerance) {
    86       if(downLocks_[i]>0&&upLocks_[i]>0) {
     87      if(allTriviallyRoundableSoFar||(downLocks_[i]>0&&upLocks_[i]>0)) {
     88
     89        if (allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {
     90          allTriviallyRoundableSoFar = false;
     91          bestScore = DBL_MAX;
     92        }
     93
    8794        // the variable cannot be rounded
    8895        double obj = direction * objective[iColumn];
     
    112119    }
    113120  }
     121  return allTriviallyRoundableSoFar;
    114122}
  • trunk/Cbc/src/CbcHeuristicDiveVectorLength.hpp

    r912 r944  
    3434
    3535  /// Selects the next variable to branch on
    36   virtual void selectVariableToBranch(OsiSolverInterface* solver,
     36  /** Returns true if all the fractional variables can be trivially
     37      rounded. Returns false, if there is at least one fractional variable
     38      that is not trivially roundable. In this case, the bestColumn
     39      returned will not be trivially roundable.
     40  */
     41  virtual bool selectVariableToBranch(OsiSolverInterface* solver,
    3742                                      const double* newSolution,
    3843                                      int& bestColumn,
Note: See TracChangeset for help on using the changeset viewer.