Changeset 1156


Ignore:
Timestamp:
Apr 23, 2009 11:04:50 AM (10 years ago)
Author:
forrest
Message:

add parallel heuristics (simple way)

Location:
trunk/Cbc
Files:
1 added
5 edited

Legend:

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

    r1132 r1156  
    3737   artificialCost_(COIN_DBL_MAX),
    3838   iterationRatio_(0.0),
     39   reducedCostMultiplier_(1.0),
    3940   maximumPasses_(100),
    4041   maximumRetries_(1),
     
    6061   artificialCost_(COIN_DBL_MAX),
    6162   iterationRatio_(0.0),
     63   reducedCostMultiplier_(1.0),
    6264   maximumPasses_(100),
    6365   maximumRetries_(1),
     
    149151  artificialCost_(rhs.artificialCost_),
    150152  iterationRatio_(rhs.iterationRatio_),
     153  reducedCostMultiplier_(rhs.reducedCostMultiplier_),
    151154  maximumPasses_(rhs.maximumPasses_),
    152155  maximumRetries_(rhs.maximumRetries_),
     
    173176    artificialCost_ = rhs.artificialCost_;
    174177    iterationRatio_ = rhs.iterationRatio_;
     178    reducedCostMultiplier_ = rhs.reducedCostMultiplier_;
    175179    maximumPasses_ = rhs.maximumPasses_;
    176180    maximumRetries_ = rhs.maximumRetries_;
     
    369373    }
    370374  }
     375#define RAND_RAND
     376#ifdef RAND_RAND
     377  double * randomFactor = new double [numberColumns];
     378  for (int i=0;i<numberColumns;i++) {
     379    double value = floor(1.0e3*randomNumberGenerator_.randomDouble());
     380    randomFactor[i] = value*1.0e-3;
     381  }
     382#endif
    371383  // guess exact multiple of objective
    372384  double exactMultiple = model_->getCutoffIncrement();
     
    416428      if (gap>0.0&&(fixOnReducedCosts_==1||(numberTries==1&&fixOnReducedCosts_==2))) {
    417429        gap += 100.0*tolerance;
     430        gap *= reducedCostMultiplier_;
    418431        int nFix=solver->reducedCostFix(gap);
    419432        if (nFix) {
     
    850863            }
    851864          }
    852           if (newValue!=oldObjective[iColumn])
     865#ifdef RAND_RAND
     866          newValue *= randomFactor[iColumn];
     867#endif
     868          if (newValue!=oldObjective[iColumn]) {
    853869            numberChanged++;
     870          }
    854871          solver->setObjCoeff(iColumn,newValue);
    855872          offset += costValue*newSolution[iColumn];
     
    953970          OsiHintStrength strength;
    954971          solver->getHintParam(OsiDoDualInResolve,takeHint,strength);
    955           if (dualPass) {
     972          if (dualPass&&numberChanged>2) {
    956973            solver->setHintParam(OsiDoDualInResolve,true); // dual may be better
    957             if (dualPass==1) {
     974            if (dualPass==1&&2*numberChanged<numberColumns) {
    958975              // but we need to make infeasible
    959976              CoinWarmStartBasis * basis =
     
    969986                for (i=0;i<numberIntegersOrig;i++) {
    970987                  int iColumn=integerVariableOrig[i];
     988#ifdef RAND_RAND
     989                  if (nChanged>numberChanged)
     990                    break;
     991#endif
    971992                  if (objective[iColumn]>0.0) {
    972993                    if (basis->getStructStatus(iColumn)==
     
    17941815    }
    17951816  }
     1817#ifdef RAND_RAND
     1818  delete [] randomFactor;
     1819#endif
    17961820  delete solver; // probably NULL but do anyway
    17971821  if (!finalReturnCode&&closestSolution&&closestObjectiveValue <= 10.0&&usedColumn) {
  • trunk/Cbc/src/CbcHeuristicFPump.hpp

    r1121 r1156  
    144144  inline int fixOnReducedCosts() const
    145145  { return fixOnReducedCosts_;}
     146  /**  Set reduced cost multiplier
     147       1.0 as normal
     148       <1.0 (x) - pretend gap is x* actual gap - just for fixing
     149  */
     150  inline void setReducedCostMultiplier(double value)
     151  { reducedCostMultiplier_=value;}
     152  /// Get reduced cost multiplier
     153  inline double reducedCostMultiplier() const
     154  { return reducedCostMultiplier_;}
    146155
    147156protected:
     
    170179      test is iterations > ratio*(2*nrow+ncol) */
    171180  double iterationRatio_;
     181  /**  Reduced cost multiplier
     182       1.0 as normal
     183       <1.0 (x) - pretend gap is x* actual gap - just for fixing
     184  */
     185  double reducedCostMultiplier_;
    172186  /// Maximum number of passes
    173187  int maximumPasses_;
  • trunk/Cbc/src/CbcHeuristicRINS.cpp

    r1121 r1156  
    177177 
    178178    const double * currentSolution = solver->getColSolution();
    179     OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
     179    OsiSolverInterface * newSolver = model_->continuousSolver() ?
     180      model_->continuousSolver()->clone() : solver->clone();
    180181    //const double * colLower = newSolver->getColLower();
    181182    //const double * colUpper = newSolver->getColUpper();
     
    308309 
    309310  const double * currentSolution = solver->getColSolution();
    310   OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
     311  OsiSolverInterface * newSolver = model_->continuousSolver() ?
     312    model_->continuousSolver()->clone() : solver->clone();
    311313  const double * colLower = newSolver->getColLower();
    312314  const double * colUpper = newSolver->getColUpper();
     
    560562    while(status) {
    561563      status=0;
    562       OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
     564      OsiSolverInterface * newSolver = model_->continuousSolver() ?
     565        model_->continuousSolver()->clone() : solver->clone();
    563566      const double * colLower = solver->getColLower();
    564567      const double * colUpper = solver->getColUpper();
  • trunk/Cbc/src/CbcModel.cpp

    r1149 r1156  
    160160static void * doNodesThread(void * voidInfo);
    161161static void * doCutsThread(void * voidInfo);
     162static void * doHeurThread(void * voidInfo);
    162163#endif
    163164/* Various functions local to CbcModel.cpp */
     
    1293712938    // Modify based on size etc
    1293812939    adjustHeuristics();
     12940#ifdef CBC_THREAD
     12941    if ((threadMode_&8)!=0) {
     12942      typedef struct
     12943      {
     12944        double solutionValue;
     12945        CbcModel * model;
     12946        double * solution;
     12947        int foundSol;
     12948      } argBundle;
     12949      int chunk;
     12950      if (!numberThreads_)
     12951        chunk=numberHeuristics_;
     12952      else
     12953        chunk=numberThreads_;
     12954      for (int iChunk=0;iChunk<numberHeuristics_;iChunk+=chunk) {
     12955        Coin_pthread_t * threadId = new Coin_pthread_t [chunk];
     12956        argBundle * parameters = new argBundle [chunk];
     12957        for (int i=0;i<chunk;i++)
     12958          parameters[i].model=NULL;
     12959        for (int i=iChunk;i<CoinMin(numberHeuristics_,iChunk+chunk);i++) {
     12960#if MODEL3
     12961          // skip if can't run here
     12962          if (!heuristic_[i]->shouldHeurRun())
     12963            continue;
     12964#endif
     12965          parameters[i-iChunk].solutionValue=heuristicValue;
     12966          CbcModel * newModel = new CbcModel(*this);
     12967          //delete newModel->solver_;
     12968          //newModel->solver_ = solver_->clone();
     12969          parameters[i-iChunk].model = newModel;
     12970          parameters[i-iChunk].solution = new double [numberColumns];;
     12971          parameters[i-iChunk].foundSol=0;
     12972          //newModel->gutsOfCopy(*this,-1);
     12973          for (int j=0;j<numberHeuristics_;j++)
     12974          delete newModel->heuristic_[j];
     12975          //newModel->heuristic_ = new CbcHeuristic * [1];
     12976          newModel->heuristic_[0]=heuristic_[i]->clone();
     12977          newModel->heuristic_[0]->setModel(newModel);
     12978          newModel->heuristic_[0]->resetModel(newModel);
     12979          newModel->numberHeuristics_=1;
     12980          pthread_create(&(threadId[i-iChunk].thr),NULL,doHeurThread,
     12981                         parameters+i-iChunk);
     12982        }
     12983        // now wait
     12984        for (int i=0;i<chunk;i++) {
     12985          if (parameters[i].model)
     12986            pthread_join(threadId[i].thr,NULL);
     12987        }
     12988        double cutoff=heuristicValue;
     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                if (heuristic_[i+iChunk]->exitNow(bestObjective_))
     13009                  break;
     13010              }
     13011            }
     13012            delete parameters[i].solution;
     13013            delete parameters[i].model;
     13014          }
     13015        }
     13016        delete [] threadId;
     13017        delete [] parameters;
     13018      }
     13019    } else {
     13020#endif
    1293913021    for (i = 0;i<numberHeuristics_;i++) {
    1294013022#if MODEL3
     
    1296313045      }
    1296413046    }
     13047#ifdef CBC_THREAD
     13048    }
     13049#endif
    1296513050    currentPassNumber_ = 0;
    1296613051    /*
     
    1489014975  return NULL;
    1489114976}
     14977static void * doHeurThread(void * voidInfo)
     14978{
     14979  typedef struct {
     14980    double solutionValue;
     14981    CbcModel * model;
     14982    double * solution;
     14983    int foundSol;
     14984  } argBundle;
     14985  argBundle * stuff = reinterpret_cast<argBundle *> (voidInfo);
     14986  stuff->foundSol =
     14987    stuff->model->heuristic(0)->solution(stuff->solutionValue,
     14988                                          stuff->solution);
     14989  pthread_exit(NULL);
     14990  return NULL;
     14991}
    1489214992static void * doCutsThread(void * voidInfo)
    1489314993{
  • trunk/Cbc/src/CbcModel.hpp

    r1132 r1156  
    12011201      2 set then use numberThreads for root cuts
    12021202      4 set then use numberThreads in root mini branch and bound
     1203      8 set and numberThreads - do heuristics numberThreads at a time
     1204      8 set and numberThreads==0 do all heuristics at once
    12031205      default is 0
    12041206  */
Note: See TracChangeset for help on using the changeset viewer.