Changeset 1010


Ignore:
Timestamp:
Jul 17, 2008 10:27:44 AM (11 years ago)
Author:
forrest
Message:

update feasibility pump

File:
1 edited

Legend:

Unmodified
Added
Removed
  • stable/2.1/Cbc/src/CbcHeuristicFPump.cpp

    r942 r1010  
    215215  int numberIntegers = model_->numberIntegers();
    216216  const int * integerVariableOrig = model_->integerVariable();
    217 
     217#ifdef COIN_DEVELOP
     218  double totalNumberIterations=0.0;
     219#endif
    218220  // 1. initially check 0-1
    219221  int i,j;
     
    324326    int numberPasses=0;
    325327    artificialFactor *= 10.0;
     328    int lastMove= (!numberTries) ? -10 : 1000000;
     329    double lastSumInfeas=COIN_DBL_MAX;
    326330    numberTries++;
    327331    // Clone solver - otherwise annoys root node computations
     
    468472      }
    469473      if (numberPasses>=maximumPasses_) {
    470         break;
     474        // If going well then keep going if maximumPasses_ small
     475        if (lastMove<numberPasses-4||lastMove==1000000)
     476          break;
     477        if (maximumPasses_>20||numberPasses>=40)
     478          break;
    471479      }
    472480      if (maximumTime_>0.0&&CoinCpuTime()>=startTime_+maximumTime_) break;
     
    519527            }
    520528            if (numberLeft) {
     529              sprintf(pumpPrint,"Branch and bound needed to clear up %d general integers",numberLeft);
     530              model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
     531                << pumpPrint
     532                <<CoinMessageEol;
    521533              returnCode = smallBranchAndBound(solver,numberNodes_,newSolution,newSolutionValue,
    522534                                               solutionValue,"CbcHeuristicFpump");
     
    548560                model_->setBestSolution(betterSolution,numberColumns,newSolutionValue);
    549561                int action = handler->event(CbcEventHandler::heuristicSolution);
    550                 if (saveOldSolution) {
     562                if (saveOldSolution&&saveObjectiveValue<model_->getMinimizationObjValue())
    551563                  model_->setBestSolution(saveOldSolution,numberColumns,saveObjectiveValue);
    552                   delete [] saveOldSolution;
    553                 }
     564                delete [] saveOldSolution;
    554565                if (!action||model_->getCurrentSeconds()>model_->getMaximumSeconds()) {
    555566                  exitAll=true; // exit
     
    578589        } else {
    579590          sprintf(pumpPrint,"After further testing solution no better than previous of %g",solutionValue);
    580 
    581591          model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    582592            << pumpPrint
     
    781791                  model_->setBestSolution(betterSolution,numberColumns,newSolutionValue);
    782792                  int action = handler->event(CbcEventHandler::heuristicSolution);
    783                   if (saveOldSolution) {
     793                  if (saveOldSolution&&saveObjectiveValue<model_->getMinimizationObjValue())
    784794                    model_->setBestSolution(saveOldSolution,numberColumns,saveObjectiveValue);
    785                     delete [] saveOldSolution;
    786                   }
     795                  delete [] saveOldSolution;
    787796                  if (!action||model_->getCurrentSeconds()>model_->getMaximumSeconds()) {
    788797                    exitAll=true; // exit
     
    855864            }
    856865            newTrueSolutionValue *= direction;
    857             OsiSolverInterface * saveSolver = model_->swapSolver(solver);
    858             CbcRounding heuristic1(*model_);
    859             heuristic1.setHeuristicName("rounding in feaspump!");
    860             heuristic1.setWhen(1);
    861             double testObjectiveValue = CoinMin(solutionValue,roundingObjective);
    862             int returnCode = heuristic1.solution(testObjectiveValue,roundingSolution,newTrueSolutionValue) ;
    863             if (returnCode==1) {
    864               assert(testObjectiveValue < CoinMin(solutionValue,roundingObjective));
    865               roundingObjective = testObjectiveValue;
    866             }
    867             model_->swapSolver(saveSolver);
    868866          }
    869867          if (!solver->isProvenOptimal()) {
     
    952950          }
    953951        }
     952        if (lastMove!=1000000) {
     953          if (newSumInfeas<lastSumInfeas) {
     954            lastMove=numberPasses;
     955            lastSumInfeas=newSumInfeas;
     956          } else if (newSumInfeas>lastSumInfeas+1.0e-5) {
     957            lastMove=1000000; // going up
     958          }
     959        }
     960#ifdef COIN_DEVELOP
     961        totalNumberIterations += solver->getIterationCount();
     962#endif
    954963        if (solver->getNumRows()<3000)
    955964          sprintf(pumpPrint,"Pass %3d: suminf. %10.5f obj. %g iterations %d", numberPasses+totalNumberPasses,
     
    983992      sprintf(pumpPrint,"Rounding solution of %g is better than previous of %g !\n",
    984993              roundingObjective,solutionValue);
     994      model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
     995        << pumpPrint
     996        <<CoinMessageEol;
    985997      solutionValue=roundingObjective;
    986998      memcpy(betterSolution,roundingSolution,numberColumns*sizeof(double));
     
    10751087        <<CoinMessageEol;
    10761088      double saveValue = newSolutionValue;
    1077       returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,newSolutionValue,
    1078                                        cutoff,"CbcHeuristicLocalAfterFPump");
     1089      if (newSolutionValue-model_->getCutoffIncrement()
     1090          >continuousObjectiveValue-1.0e-7) {
     1091        // Give branch and bound a bit more freedom
     1092        double cutoff2=newSolutionValue-model_->getCutoffIncrement();
     1093        returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,newSolutionValue,
     1094                                         cutoff2,"CbcHeuristicLocalAfterFPump");
     1095      } else {
     1096        // no need
     1097        exitAll=true;
     1098        returnCode=0;
     1099      }
    10791100      if (returnCode<0) {
    10801101        if (returnCode==-2)
     
    10851106        // could add cut
    10861107        returnCode &= ~2;
     1108      }
     1109      // recompute solution value
     1110      if (returnCode&&true) {
     1111        delete newSolver;
     1112        newSolver = model_->continuousSolver()->clone();
     1113        newSolutionValue = -saveOffset;
     1114        double newSumInfeas=0.0;
     1115        const double * obj = newSolver->getObjCoefficients();
     1116        for (int i=0 ; i<numberColumns ; i++ ) {
     1117          if (newSolver->isInteger(i)) {
     1118            double value = newSolution[i];
     1119            double nearest = floor(value+0.5);
     1120            newSumInfeas += fabs(value-nearest);
     1121          }
     1122          newSolutionValue += obj[i]*newSolution[i];
     1123        }
     1124        newSolutionValue *= direction;
    10871125      }
    10881126      if (returnCode&&newSolutionValue<saveValue) {
     
    11411179            model_->setBestSolution(betterSolution,numberColumns,newSolutionValue);
    11421180            int action = handler->event(CbcEventHandler::heuristicSolution);
    1143             if (saveOldSolution) {
     1181            //printf("cutoff %g\n",model_->getCutoff());
     1182            if (saveOldSolution&&saveObjectiveValue<model_->getMinimizationObjValue())
    11441183              model_->setBestSolution(saveOldSolution,numberColumns,saveObjectiveValue);
    1145               delete [] saveOldSolution;
    1146             }
     1184            delete [] saveOldSolution;
    11471185            if (!action||model_->getCurrentSeconds()>model_->getMaximumSeconds()) {
    11481186              exitAll=true; // exit
     
    11611199    }
    11621200    if (solutionFound) finalReturnCode=1;
    1163     cutoff = CoinMin(cutoff,solutionValue);
     1201    cutoff = CoinMin(cutoff,solutionValue-model_->getCutoffIncrement());
    11641202    if (numberTries>=maximumRetries_||!solutionFound||exitAll||cutoff<continuousObjectiveValue+1.0e-7) {
    11651203      break;
     
    12501288    model_->setNumberHeuristicSolutions(1);
    12511289  }
     1290#ifdef COIN_DEVELOP
     1291  {
     1292    double ncol = model_->solver()->getNumCols();
     1293    double nrow = model_->solver()->getNumRows();
     1294    printf("XXX total iterations %g ratios - %g %g %g\n",
     1295           totalNumberIterations,
     1296           totalNumberIterations/nrow,
     1297           totalNumberIterations/ncol,
     1298           totalNumberIterations/(2*nrow+2*ncol));
     1299  }
     1300#endif
    12521301  return finalReturnCode;
    12531302}
Note: See TracChangeset for help on using the changeset viewer.