Changeset 1946 for trunk


Ignore:
Timestamp:
Jul 29, 2013 12:02:43 PM (6 years ago)
Author:
forrest
Message:

modifications to heuristic

Location:
trunk/Cbc/src
Files:
2 edited

Legend:

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

    r1945 r1946  
    7979  bestSolution_=NULL;
    8080  continuousSolution_ = NULL;
     81  fixedDj_ = NULL;
    8182  saveLower_=NULL;
    8283  saveUpper_=NULL;
     
    107108  keepContinuous_=0;
    108109  phase_=0;
     110  pass_ = 0;
    109111  nNeededBase_=200;
    110112  nNodesBase_=500;
     
    135137  keepContinuous_ = rhs.keepContinuous_;
    136138  phase_ = rhs.phase_;
     139  pass_ = rhs.pass_;
    137140  nNeededBase_ = rhs.nNeededBase_;
    138141  nNodesBase_ = rhs.nNodesBase_;
     
    208211    continuousSolution_=NULL;
    209212  }
     213  if (rhs.fixedDj_) {
     214    int numberColumns = solver_->getNumCols();
     215    fixedDj_ = CoinCopyOfArray(rhs.fixedDj_,numberColumns);
     216  } else {
     217    fixedDj_=NULL;
     218  }
    210219}
    211220// Guts of delete
     
    217226  delete [] bestSolution_;
    218227  delete [] continuousSolution_;
     228  delete [] fixedDj_;
    219229  delete [] saveLower_;
    220230  delete [] saveUpper_;
     
    239249  bestSolution_=NULL;
    240250  continuousSolution_ = NULL;
     251  fixedDj_ = NULL;
    241252  saveLower_=NULL;
    242253  saveUpper_=NULL;
     
    353364  }
    354365  // data arrays
     366  // Block order for choosing (after sort)
    355367  int * whichBlock = new int [7*numberBlocks_];
    356368  memset(whichBlock,0,7*numberBlocks_*sizeof(int));
     369  // Count of number of times block chosen
    357370  int * doneBlock = whichBlock + numberBlocks_;
     371  // Pass at which block last used
    358372  int * whenBlock = doneBlock+numberBlocks_;
    359   int * priorityBlock = whenBlock+numberBlocks_;
     373  // Number of Big Djs' (? artificial costs) in block
     374  int * bigDjBlock = whenBlock+numberBlocks_;
     375  // Number of times block has helped improve solution
     376  int * goodBlock = bigDjBlock+numberBlocks_;
     377  int * priorityBlock = goodBlock+numberBlocks_;
    360378  int * orderBlock = priorityBlock+numberBlocks_;
    361   int * bigDjBlock = orderBlock+numberBlocks_;
    362   int * goodBlock = bigDjBlock+numberBlocks_;
     379  // Mixture of stuff to sort blocks on
    363380  double * blockSort = new double [4*numberBlocks_];
     381  // Reduced cost (d sub j was old notation) contribution
    364382  double * blockDj = blockSort + numberBlocks_;
     383  // Difference between current best and continuous solutions
    365384  double * blockDiff = blockDj+numberBlocks_;
     385  // Difference between current best and continuous solutions (just integers)
    366386  double * blockDiffInt = blockDiff+numberBlocks_;
    367   double * fixedDj = CoinCopyOfArray(dj,numberColumns);
     387  delete [] fixedDj_;
     388  fixedDj_ = CoinCopyOfArray(dj,numberColumns);
    368389  int numberImproving=0;
    369390  int * whenBetter = new int [numberPasses_];
     
    393414    }
    394415  }
    395   for (int iPass=0;iPass<numberPasses_;iPass++) {
     416  for (pass_=0;pass_<numberPasses_;pass_++) {
    396417    double endTime2 = CoinCpuTime();
    397418    double endTime2Elapsed = CoinGetTimeOfDay();
     
    399420#define SCALE_FACTOR 1.0
    400421#endif
    401     if (iPass)
     422    if (pass_)
    402423      printf("PASS %d changed objective from %g to %g in %g seconds (%g elapsed) - total %g (%g elapsed) - current needed %d nodes %d - %s\n",
    403              iPass,lastObjective_*SCALE_FACTOR,
     424             pass_,lastObjective_*SCALE_FACTOR,
    404425             bestObjective_*SCALE_FACTOR,endTime2-startTime2,
    405426             endTime2Elapsed-startTime2Elapsed,
     
    407428             nNeeded_,nNodes_,
    408429             lastObjective_>bestObjective_+1.0e-3 ? "improving" : "");
    409     if ((iPass%10)==9) {
     430    if ((pass_%10)==9) {
    410431      for (int iImp=1;iImp<numberImproving;iImp++) {
    411432        int * blocks = improvingBlocks[iImp];
     
    481502    if (goodSolution) {
    482503      int lastNumberDW=numberDW_;
     504      solver->setColSolution(bestSolution_);
    483505      solver->setHintParam(OsiDoReducePrint, false, OsiHintDo, 0) ;
    484506      if (basis) {
     
    497519        memcpy(blocks+1,whichBlock,numberBlocksUsed*sizeof(int));
    498520        improvingBlocks[numberImproving]=blocks;
    499         whenBetter[numberImproving]=iPass;
     521        whenBetter[numberImproving]=pass_;
    500522        improvement[numberImproving]=lastObjective_-bestObjective_;
    501523        numberImproving++;
    502524        lastObjective_=bestObjective_;
    503         if (iPass) {
     525        if (pass_) {
    504526          // update good
    505527          for (int i=0;i<numberBlocksUsed;i++)
     
    662684        if (solver->isInteger(iColumn)) {
    663685          if (bestSolution_[iColumn]<saveUpper_[iColumn]-1.0e-1) {
    664             if (fixedDj[iColumn]<-1.0e-5)
    665               blockDj[iBlock]+=fixedDj[iColumn];
    666             if (fixedDj[iColumn]<-1.0e4)
     686            if (fixedDj_[iColumn]<-1.0e-5)
     687              blockDj[iBlock]+=fixedDj_[iColumn];
     688            if (fixedDj_[iColumn]<-1.0e4)
    667689              bigDjBlock[iBlock]++;
    668690          }
    669691          if (bestSolution_[iColumn]>saveLower_[iColumn]+1.0e-1) {
    670             if (fixedDj[iColumn]>1.0e-5)
    671               blockDj[iBlock]-=fixedDj[iColumn];
    672             if (fixedDj[iColumn]>1.0e4)
     692            if (fixedDj_[iColumn]>1.0e-5)
     693              blockDj[iBlock]-=fixedDj_[iColumn];
     694            if (fixedDj_[iColumn]>1.0e4)
    673695              bigDjBlock[iBlock]++;
    674696          }
     
    676698      }
    677699    }
     700    // Get average dj and difference
     701    int numberInDj=0;
     702    double averageDj=1.0e-12;
     703    int numberInDiff=0;
     704    double averageDiff=1.0e-12;
     705    for (int i=0;i<numberBlocks_;i++) {
     706      assert (blockDj[i]<=0.0);
     707      if (blockDj[i]<0.0) {
     708        numberInDj++;
     709        averageDj -= blockDj[i];
     710      }
     711      assert (blockDiff[i]>=0.0);
     712      if (blockDiff[i]>0.0) {
     713        numberInDiff++;
     714        averageDiff += blockDiff[i];
     715      }
     716    }
     717    if (numberInDj)
     718      averageDj /= static_cast<double>(numberInDj);
     719    if (numberInDiff)
     720      averageDiff /= static_cast<double>(numberInDiff);
     721    double ratioDiff = averageDj/averageDiff;
     722    // downplay
     723    ratioDiff *= 1.0e-3;
    678724    for (int i=0;i<numberBlocks_;i++) {
    679725      whichBlock[i]=i;
     
    684730      blockSort[i] *= CoinDrand48() + 5.0e-1;
    685731#elif TRY_ADJUST == 2
    686       blockSort[i] -= 1.0e7* blockDiff[i];
     732      blockSort[i] -= ratioDiff* blockDiff[i];
    687733#elif TRY_ADJUST == 3
    688       blockSort[i] -= 1.0e7* blockDiff[i];
     734      blockSort[i] -= ratioDiff* blockDiff[i];
    689735      blockSort[i] *= 0.1*CoinDrand48() + 0.9;
    690736#endif
    691737      if (phase_==99)
    692         blockSort[i] -= 1.0e7*goodBlock[i];
     738        blockSort[i] -= 2.0*averageDj*goodBlock[i];
    693739      blockSort[i] /= static_cast<double>(intsInBlock_[i]);
    694740      //blockSort[i] /= sqrt(static_cast<double>(intsInBlock_[i]));
    695741      if (doneBlock[i]) {
    696742        blockSort[i] /= static_cast<double>(doneBlock[i]+1);
    697         if (whenBlock[i]>iPass-10)
    698           blockSort[i]+= 1.0e9;
     743        if (whenBlock[i]>pass_-10)
     744          blockSort[i]+= 1.0e2*averageDj;
    699745      }
    700746    }
     
    729775          numberBlocksIn++;
    730776          doneBlock[iBlock]++;
    731           whenBlock[iBlock]=iPass;
     777          whenBlock[iBlock]=pass_;
    732778          nFreed += intsInBlock_[iBlock];
    733779          for (int j=startColumnBlock_[iBlock];
     
    805851      columnUpper[i]=saveUpper_[i];
    806852      int kBlock = whichColumnBlock_[i];
    807       if (kBlock>=0&&solver->isInteger(i)&&whenBlock[kBlock]!=iPass) {
     853      if (kBlock>=0&&solver->isInteger(i)&&whenBlock[kBlock]!=pass_) {
    808854        columnLower[i]=bestSolution_[i];
    809855        columnUpper[i]=bestSolution_[i];
     
    823869      // trouble
    824870      for (int i=0;i<numberBlocks_;i++) {
    825         if (whenBlock[i]==iPass) {
     871        if (whenBlock[i]==pass_) {
    826872          printf("Block %d free\n",i);
    827873        }
     
    844890    for ( int i=0 ; i<numberColumns ; ++i ) {
    845891      int kBlock = whichColumnBlock_[i];
    846       if (kBlock>=0&&!solver->isInteger(i)&&whenBlock[kBlock]!=iPass) {
     892      if (kBlock>=0&&!solver->isInteger(i)&&whenBlock[kBlock]!=pass_) {
    847893        columnLower[i]=tempSol[i];
    848894        columnUpper[i]=tempSol[i];
     
    904950            int iColumn=originalColumns[i];
    905951            hot[i]=bestSolution_[iColumn];
    906             hotWeight[i]=-fabs(fixedDj[iColumn]);
     952            hotWeight[i]=-fabs(fixedDj_[iColumn]);
    907953            if (bestSolution_[i]<saveLower_[iColumn]+1.0e-6) {
    908               if (fixedDj[i]>0.0)
    909                 hotWeight[i]=fixedDj[iColumn];
     954              if (fixedDj_[i]>0.0)
     955                hotWeight[i]=fixedDj_[iColumn];
    910956            } else if (bestSolution_[i]>saveUpper_[iColumn]-1.0e-6) {
    911               if (fixedDj[i]<0.0)
    912                 hotWeight[i]=-fixedDj[iColumn];
     957              if (fixedDj_[i]<0.0)
     958                hotWeight[i]=-fixedDj_[iColumn];
    913959            }
    914960            if (solution[i]<saveLower_[iColumn]+1.0e-6) {
     
    10221068            delete basis;
    10231069          basis = solver->getWarmStart();
    1024           memcpy(fixedDj,solver->getReducedCost(),
     1070          memcpy(fixedDj_,solver->getReducedCost(),
    10251071                 numberColumns*sizeof(double));
    10261072          solver->setHintParam(OsiDoReducePrint, true, OsiHintDo, 0) ;
     
    10691115  delete [] whichBlock;
    10701116  delete [] blockSort;
    1071   delete [] fixedDj;
    10721117  delete [] whenBetter;
    10731118  delete [] improvement;
  • trunk/Cbc/src/CbcHeuristicDW.hpp

    r1945 r1946  
    9090    /// Best solution found so far
    9191    inline const double * bestSolution() const
    92   { return bestSolution_;}
     92    { return bestSolution_;}
     93    /// Continuous solution
     94    inline const double * continuousSolution() const
     95    { return continuousSolution_;}
     96    /// Reduced costs of fixed solution
     97    inline const double * fixedDj() const
     98    { return fixedDj_;}
    9399    /// Objective at which DW updated
    94100    inline const double * objectiveDW() const
     
    125131    inline const double * initialUpper() const
    126132    { return saveUpper_;}
     133    /// Local integer arrays (each numberBlocks_ long)
     134    inline int * intArrays() const
     135    { return intArray_;}
     136    /// Local double arrays (each numberBlocks_ long)
     137    inline double * doubleArrays() const
     138    { return doubleArray_;}
     139    /// Phase of solution
     140    inline int phase() const
     141    { return phase_;}
     142    /// Pass number
     143    inline int pass() const
     144    { return pass_;}
     145    /// Which columns are in block
     146    inline const int * columnsInBlock() const
     147    { return columnsInBlock_;}
     148    /// Starts for columnsInBlock
     149    inline const int * startColumnBlock() const
     150    { return startColumnBlock_;}
     151    /// Number of integer variables in each block
     152    inline const int * intsInBlock() const
     153    { return intsInBlock_;}
    127154    /// Objective value (could also check validity)
    128155    double objectiveValue(const double * solution);
     
    170197    /// Continuous solution
    171198    double * continuousSolution_;
     199    /// Reduced costs of fixed solution
     200    double * fixedDj_;
    172201    /// Original lower bounds
    173202    double * saveLower_;
     
    232261    /// Phase of solution
    233262    int phase_;
     263    /// Pass number
     264    int pass_;
    234265    /// Base number of integers needed
    235266    int nNeededBase_;
Note: See TracChangeset for help on using the changeset viewer.