Changeset 1160


Ignore:
Timestamp:
Apr 24, 2009 1:10:46 PM (11 years ago)
Author:
forrest
Message:

parallel heuristics

Location:
trunk/Cbc/src
Files:
3 edited

Legend:

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

    r1158 r1160  
    488488  OsiSolverInterface * solver = model_->solver();
    489489  double bestPossibleObjective = solver->getObjValue()*solver->getObjSense();
    490   double testGap = CoinMax(model_->getAllowableGap(),
     490  double absGap = CoinMax(model_->getAllowableGap(),
     491                          model_->getHeuristicGap());
     492  double fracGap = CoinMax(model_->getAllowableFractionGap(),
     493                          model_->getHeuristicFractionGap());
     494  double testGap = CoinMax(absGap,fracGap*
    491495                           CoinMax(fabs(bestObjective),
    492                                    fabs(bestPossibleObjective))
    493                            *model_->getAllowableFractionGap());
     496                                   fabs(bestPossibleObjective)));
     497
    494498  if (bestObjective-bestPossibleObjective < testGap
    495499      && model_->getCutoffIncrement()>=0.0) {
  • trunk/Cbc/src/CbcModel.cpp

    r1158 r1160  
    18411841      if (numberUnsatisfied)   {
    18421842        // User event
    1843         if (!eventHappened_)
     1843        if (!eventHappened_&&feasible)
    18441844          feasible = solveWithCuts(cuts,maximumCutPassesAtRoot_,
    18451845                                   NULL);
     
    41784178  dblParam_[CbcAllowableGap] = 1.0e-10;
    41794179  dblParam_[CbcAllowableFractionGap] = 0.0;
     4180  dblParam_[CbcHeuristicGap] = 0.0;
     4181  dblParam_[CbcHeuristicFractionGap] = 0.0;
    41804182  dblParam_[CbcMaximumSeconds] = 1.0e100;
    41814183  dblParam_[CbcCurrentCutoff] = 1.0e100;
     
    43384340  dblParam_[CbcAllowableGap] = 1.0e-10;
    43394341  dblParam_[CbcAllowableFractionGap] = 0.0;
     4342  dblParam_[CbcHeuristicGap] = 0.0;
     4343  dblParam_[CbcHeuristicFractionGap] = 0.0;
    43404344  dblParam_[CbcMaximumSeconds] = 1.0e100;
    43414345  dblParam_[CbcCurrentCutoff] = 1.0e100;
     
    1293412938    // Modify based on size etc
    1293512939    adjustHeuristics();
     12940    // See if already withing allowable gap
     12941    bool exitNow=false;
     12942    for (i = 0;i<numberHeuristics_;i++) {
     12943      if (heuristic_[i]->exitNow(bestObjective_))
     12944        exitNow=true;
     12945    }
     12946    if (!exitNow) {
    1293612947#ifdef CBC_THREAD
    12937     if ((threadMode_&8)!=0) {
    12938       typedef struct
    12939       {
    12940         double solutionValue;
    12941         CbcModel * model;
    12942         double * solution;
    12943         int foundSol;
    12944       } argBundle;
    12945       int chunk;
    12946       if (!numberThreads_)
    12947         chunk=numberHeuristics_;
    12948       else
    12949         chunk=numberThreads_;
    12950       for (int iChunk=0;iChunk<numberHeuristics_;iChunk+=chunk) {
    12951         Coin_pthread_t * threadId = new Coin_pthread_t [chunk];
    12952         argBundle * parameters = new argBundle [chunk];
    12953         for (int i=0;i<chunk;i++)
    12954           parameters[i].model=NULL;
    12955         for (int i=iChunk;i<CoinMin(numberHeuristics_,iChunk+chunk);i++) {
     12948      if ((threadMode_&8)!=0) {
     12949        typedef struct
     12950        {
     12951          double solutionValue;
     12952          CbcModel * model;
     12953          double * solution;
     12954          int foundSol;
     12955        } argBundle;
     12956        int chunk;
     12957        if (!numberThreads_)
     12958          chunk=numberHeuristics_;
     12959        else
     12960          chunk=numberThreads_;
     12961        for (int iChunk=0;iChunk<numberHeuristics_;iChunk+=chunk) {
     12962          Coin_pthread_t * threadId = new Coin_pthread_t [chunk];
     12963          argBundle * parameters = new argBundle [chunk];
     12964          for (int i=0;i<chunk;i++)
     12965            parameters[i].model=NULL;
     12966          for (int i=iChunk;i<CoinMin(numberHeuristics_,iChunk+chunk);i++) {
     12967#if MODEL3
     12968            // skip if can't run here
     12969            if (!heuristic_[i]->shouldHeurRun())
     12970              continue;
     12971#endif
     12972            parameters[i-iChunk].solutionValue=heuristicValue;
     12973            CbcModel * newModel = new CbcModel(*this);
     12974            assert (!newModel->continuousSolver_);
     12975            if (continuousSolver_)
     12976              newModel->continuousSolver_ = continuousSolver_->clone();
     12977            else
     12978              newModel->continuousSolver_ = solver_->clone();
     12979            parameters[i-iChunk].model = newModel;
     12980            parameters[i-iChunk].solution = new double [numberColumns];;
     12981            parameters[i-iChunk].foundSol=0;
     12982            //newModel->gutsOfCopy(*this,-1);
     12983            for (int j=0;j<numberHeuristics_;j++)
     12984              delete newModel->heuristic_[j];
     12985            //newModel->heuristic_ = new CbcHeuristic * [1];
     12986            newModel->heuristic_[0]=heuristic_[i]->clone();
     12987            newModel->heuristic_[0]->setModel(newModel);
     12988            newModel->heuristic_[0]->resetModel(newModel);
     12989            newModel->numberHeuristics_=1;
     12990            pthread_create(&(threadId[i-iChunk].thr),NULL,doHeurThread,
     12991                           parameters+i-iChunk);
     12992          }
     12993          // now wait
     12994          for (int i=0;i<chunk;i++) {
     12995            if (parameters[i].model)
     12996              pthread_join(threadId[i].thr,NULL);
     12997          }
     12998          double cutoff=heuristicValue;
     12999          for (int i=0;i<chunk;i++) {
     13000            if (parameters[i].model) {
     13001              if (parameters[i].foundSol>0&&
     13002                  parameters[i].solutionValue<heuristicValue) {
     13003                memcpy(newSolution,parameters[i].solution,
     13004                       numberColumns*sizeof(double));
     13005                lastHeuristic_ = heuristic_[i+iChunk];
     13006                double value = parameters[i].solutionValue;
     13007                setBestSolution(CBC_ROUNDING,value,newSolution) ;
     13008                // Double check valid
     13009                if (getCutoff()<cutoff) {
     13010                  cutoff=getCutoff();
     13011                  heuristicValue=value;
     13012                  heuristic_[i+iChunk]->incrementNumberSolutionsFound();
     13013                  incrementUsed(newSolution);
     13014                  // increment number of solutions so other heuristics can test
     13015                  numberSolutions_++;
     13016                  numberHeuristicSolutions_++;
     13017                  found = i+iChunk ;
     13018                }
     13019              }
     13020              if (heuristic_[i+iChunk]->exitNow(bestObjective_)||
     13021                  (parameters[i].model->heuristic(0)->switches()&2048)!=0)
     13022                exitNow=true;
     13023              delete parameters[i].solution;
     13024              delete parameters[i].model;
     13025            }
     13026          }
     13027          delete [] threadId;
     13028          delete [] parameters;
     13029          if (exitNow)
     13030            break;
     13031        }
     13032      } else {
     13033#endif
     13034        for (i = 0;i<numberHeuristics_;i++) {
    1295613035#if MODEL3
    1295713036          // skip if can't run here
     
    1295913038            continue;
    1296013039#endif
    12961           parameters[i-iChunk].solutionValue=heuristicValue;
    12962           CbcModel * newModel = new CbcModel(*this);
    12963           assert (!newModel->continuousSolver_);
    12964           if (continuousSolver_)
    12965             newModel->continuousSolver_ = continuousSolver_->clone();
    12966           else
    12967             newModel->continuousSolver_ = solver_->clone();
    12968           parameters[i-iChunk].model = newModel;
    12969           parameters[i-iChunk].solution = new double [numberColumns];;
    12970           parameters[i-iChunk].foundSol=0;
    12971           //newModel->gutsOfCopy(*this,-1);
    12972           for (int j=0;j<numberHeuristics_;j++)
    12973           delete newModel->heuristic_[j];
    12974           //newModel->heuristic_ = new CbcHeuristic * [1];
    12975           newModel->heuristic_[0]=heuristic_[i]->clone();
    12976           newModel->heuristic_[0]->setModel(newModel);
    12977           newModel->heuristic_[0]->resetModel(newModel);
    12978           newModel->numberHeuristics_=1;
    12979           pthread_create(&(threadId[i-iChunk].thr),NULL,doHeurThread,
    12980                          parameters+i-iChunk);
    12981         }
    12982         // now wait
    12983         for (int i=0;i<chunk;i++) {
    12984           if (parameters[i].model)
    12985             pthread_join(threadId[i].thr,NULL);
    12986         }
    12987         double cutoff=heuristicValue;
    12988         bool exitNow=false;
    12989         for (int i=0;i<chunk;i++) {
    12990           if (parameters[i].model) {
    12991             if (parameters[i].foundSol>0&&
    12992                 parameters[i].solutionValue<heuristicValue) {
    12993               memcpy(newSolution,parameters[i].solution,
    12994                      numberColumns*sizeof(double));
    12995               lastHeuristic_ = heuristic_[i+iChunk];
    12996               double value = parameters[i].solutionValue;
    12997               setBestSolution(CBC_ROUNDING,value,newSolution) ;
    12998               // Double check valid
    12999               if (getCutoff()<cutoff) {
    13000                 cutoff=getCutoff();
    13001                 heuristicValue=value;
    13002                 heuristic_[i+iChunk]->incrementNumberSolutionsFound();
    13003                 incrementUsed(newSolution);
    13004                 // increment number of solutions so other heuristics can test
    13005                 numberSolutions_++;
    13006                 numberHeuristicSolutions_++;
    13007                 found = i+iChunk ;
    13008               }
    13009             }
    13010             if (heuristic_[i+iChunk]->exitNow(bestObjective_)||
    13011                 (parameters[i].model->heuristic(0)->switches()&2048)!=0)
    13012               exitNow=true;
    13013             delete parameters[i].solution;
    13014             delete parameters[i].model;
     13040          // see if heuristic will do anything
     13041          double saveValue = heuristicValue ;
     13042          int ifSol = heuristic_[i]->solution(heuristicValue,
     13043                                              newSolution);
     13044          if (ifSol>0) {
     13045            // better solution found
     13046            heuristic_[i]->incrementNumberSolutionsFound();
     13047            found = i ;
     13048            incrementUsed(newSolution);
     13049            // increment number of solutions so other heuristics can test
     13050            numberSolutions_++;
     13051            numberHeuristicSolutions_++;
     13052            lastHeuristic_ = heuristic_[i];
     13053            setBestSolution(CBC_ROUNDING,heuristicValue,newSolution) ;
     13054            if (heuristic_[i]->exitNow(bestObjective_))
     13055              break;
     13056          } else {
     13057            heuristicValue = saveValue ;
    1301513058          }
    1301613059        }
    13017         delete [] threadId;
    13018         delete [] parameters;
    13019         if (exitNow)
    13020           break;
    13021       }
    13022     } else {
    13023 #endif
    13024     for (i = 0;i<numberHeuristics_;i++) {
    13025 #if MODEL3
    13026       // skip if can't run here
    13027       if (!heuristic_[i]->shouldHeurRun())
    13028         continue;
    13029 #endif
    13030       // see if heuristic will do anything
    13031       double saveValue = heuristicValue ;
    13032       int ifSol = heuristic_[i]->solution(heuristicValue,
    13033                                           newSolution);
    13034       if (ifSol>0) {
    13035         // better solution found
    13036         heuristic_[i]->incrementNumberSolutionsFound();
    13037         found = i ;
    13038         incrementUsed(newSolution);
    13039         // increment number of solutions so other heuristics can test
    13040         numberSolutions_++;
    13041         numberHeuristicSolutions_++;
    13042         lastHeuristic_ = heuristic_[i];
    13043         setBestSolution(CBC_ROUNDING,heuristicValue,newSolution) ;
    13044         if (heuristic_[i]->exitNow(bestObjective_))
    13045           break;
    13046       } else {
    13047         heuristicValue = saveValue ;
    13048       }
    13049     }
    1305013060#ifdef CBC_THREAD
    13051     }
    13052 #endif
     13061      }
     13062#endif
     13063    }
    1305313064    currentPassNumber_ = 0;
    1305413065    /*
  • trunk/Cbc/src/CbcModel.hpp

    r1158 r1160  
    155155             So that other pieces of code can access */
    156156  CbcStartSeconds,
     157  /** Stop doing heuristics when the gap between the objective value of the
     158      best known solution and the best bound on the objective of any solution
     159      is less than this.
     160 
     161    This is an absolute value. Conversion from a percentage is left to the
     162    client.
     163  */
     164  CbcHeuristicGap,
     165  /** Stop doing heuristics when the gap between the objective value of the
     166      best known solution and the best bound on the objective of any solution
     167      is less than this fraction of of the absolute value of best known
     168      solution.
     169 
     170    Code stops if either this test or CbcAllowableGap test succeeds
     171  */
     172  CbcHeuristicFractionGap,
    157173  /** Just a marker, so that a static sized array can store parameters. */
    158174  CbcLastDblParam
     
    621637  inline double getAllowablePercentageGap() const {
    622638    return 100.0*getDblParam(CbcAllowableFractionGap);
     639  }
     640  /** Set the \link CbcModel::CbcHeuristicGap heuristic gap \endlink
     641      between the best known solution and the best possible solution.
     642  */
     643  inline bool setHeuristicGap( double value) {
     644    return setDblParam(CbcHeuristicGap,value);
     645  }
     646  /** Get the \link CbcModel::CbcHeuristicGap heuristic gap \endlink
     647      between the best known solution and the best possible solution.
     648  */
     649  inline double getHeuristicGap() const {
     650    return getDblParam(CbcHeuristicGap);
     651  }
     652
     653  /** Set the \link CbcModel::CbcHeuristicFractionGap fraction heuristic gap \endlink
     654      between the best known solution and the best possible solution.
     655  */
     656  inline bool setHeuristicFractionGap( double value) {
     657    return setDblParam(CbcHeuristicFractionGap,value);
     658  }
     659  /** Get the \link CbcModel::CbcHeuristicFractionGap fraction heuristic gap \endlink
     660      between the best known solution and the best possible solution.
     661  */
     662  inline double getHeuristicFractionGap() const {
     663    return getDblParam(CbcHeuristicFractionGap);
    623664  }
    624665  /** Set the
Note: See TracChangeset for help on using the changeset viewer.