Ignore:
Timestamp:
Jan 11, 2011 2:04:34 PM (9 years ago)
Author:
forrest
Message:

add some more heuristics

File:
1 edited

Legend:

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

    r1582 r1585  
    9999    const double * currentSolution = newSolver->getColSolution();
    100100    int type = rensType_&15;
    101     if (type<11)
     101    if (type<12)
    102102      newSolver->resolve();
    103103    double direction = newSolver->getObjSense();
     
    108108    double tolerance;
    109109    newSolver->getDblParam(OsiDualTolerance, tolerance) ;
    110     if ((gap > 0.0 || !newSolver->isProvenOptimal())&&type<11) {
     110    if ((gap > 0.0 || !newSolver->isProvenOptimal())&&type<12) {
    111111      gap += 100.0 * tolerance;
    112112      int nFix = newSolver->reducedCostFix(gap);
     
    118118          << CoinMessageEol;
    119119      }
    120     } else if (type<11) {
     120    } else if (type<12) {
    121121      return 0; // finished?
    122122    }
     
    146146        delete basis;
    147147      }
    148     } else if (type>=5&&type<=11) {
     148    } else if (type>=5&&type<=12) {
    149149      /* 5 fix sets at one
    150150         6 fix on dj but leave unfixed SOS slacks
     
    153153         9 as 8 but only fix all at zero if just one in set nonzero
    154154         10 fix all "stable" ones
    155          11 layered approach
     155         11 fix all "stable" ones - approach 2
     156         12 layered approach
    156157      */
    157158      // SOS type fixing
    158       bool fixSets = (type==5)||(type==7)||(type==10);
     159      bool fixSets = (type==5)||(type==7)||(type==10)||(type==11);
    159160      CoinWarmStartBasis * basis =
    160161        dynamic_cast<CoinWarmStartBasis *>(solver->getWarmStart()) ;
     
    250251        double * sort = new double [numberRows];
    251252        const double * pi = newSolver->getRowPrice();
    252         if (type==11) {
     253        if (type==12) {
    253254          contribution = new double [numberRows];
    254255          for (int i=0;i<numberRows;i++) {
     
    407408            numberFixed=numberColumns;
    408409            djTolerance = 1.0e30;
     410          } else if (type==11) {
     411            double * saveUpper = CoinCopyOfArray(newSolver->getRowUpper(),numberRows);
     412            char * mark = new char [numberColumns];
     413            char * nonzero = new char [numberColumns];
     414            // save basis and solution
     415            CoinWarmStartBasis * basis = dynamic_cast<CoinWarmStartBasis*>(newSolver->getWarmStart()) ;
     416            assert(basis != NULL);
     417            double * saveSolution =
     418              CoinCopyOfArray(newSolver->getColSolution(),
     419                              numberColumns);
     420            double factors[] = {1.1,1.05,1.01,0.98};
     421            int nPass = (sizeof(factors)/sizeof(double))-1;
     422            double factor=factors[0];
     423            double proportion = fractionSmall_;
     424            fractionSmall_ = 0.5;
     425            // loosen up
     426            for (int i=0;i<numberRows;i++) {
     427              if (bestDj[i]>=1.0e30) {
     428                newSolver->setRowUpper(i,factor*saveUpper[i]);
     429              }
     430            }
     431            bool takeHint;
     432            OsiHintStrength strength;
     433            newSolver->getHintParam(OsiDoDualInResolve, takeHint, strength);
     434            newSolver->setHintParam(OsiDoDualInResolve, false, OsiHintDo);
     435            newSolver->resolve();
     436            newSolver->setHintParam(OsiDoDualInResolve, true, OsiHintDo);
     437            const double * solution = newSolver->getColSolution();
     438            for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
     439              mark[iColumn]=0;
     440              nonzero[iColumn]=0;
     441              if (colUpper[iColumn]>colLower[iColumn]&&
     442                  solution[iColumn]>0.9999)
     443                mark[iColumn]=1;
     444              else if (solution[iColumn]>0.00001)
     445                nonzero[iColumn]=1;
     446            }
     447            int nCheck=2;
     448            for (int iPass=0;iPass<nPass;iPass++) {
     449              // smaller
     450              factor = factors[iPass+1];
     451              for (int i=0;i<numberRows;i++) {
     452                if (bestDj[i]>=1.0e30) {
     453                  newSolver->setRowUpper(i,saveUpper[i]*factor);
     454                }
     455              }
     456              newSolver->resolve();
     457              if (newSolver->isProvenOptimal()) {
     458                nCheck++;
     459                for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
     460                  if (colUpper[iColumn]>colLower[iColumn]&&
     461                      solution[iColumn]>0.9999)
     462                    mark[iColumn]++;
     463                  else if (solution[iColumn]>0.00001)
     464                    nonzero[iColumn]++;
     465                }
     466              }
     467            }
     468            // correct values
     469            for (int i=0;i<numberRows;i++) {
     470              if (bestDj[i]>=1.0e30) {
     471                newSolver->setRowUpper(i,saveUpper[i]);
     472              }
     473            }
     474            newSolver->setColSolution(saveSolution);
     475            delete [] saveSolution;
     476            newSolver->setWarmStart(basis);
     477            delete basis ;
     478            newSolver->setHintParam(OsiDoDualInResolve, takeHint, strength);
     479            newSolver->resolve();
     480            for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
     481              if (colUpper[iColumn]>colLower[iColumn]&&
     482                  solution[iColumn]>0.9999)
     483                mark[iColumn]++;
     484              else if (solution[iColumn]>0.00001)
     485                nonzero[iColumn]++;
     486            }
     487            int nFixed=0;
     488            int numberSetsToFix = static_cast<int>(nSOS*(1.0-proportion));
     489            int * mixed = new int[numberRows];
     490            memset(mixed,0,numberRows*sizeof(int));
     491            for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
     492              if (colUpper[iColumn]>colLower[iColumn]) {
     493                int iSOS=-1;
     494                for (CoinBigIndex j = columnStart[iColumn];
     495                     j < columnStart[iColumn] + columnLength[iColumn]; j++) {
     496                  int iRow = row[j];
     497                  if (bestDj[iRow]<1.0e25) {
     498                    iSOS=iRow;
     499                    break;
     500                  }
     501                }
     502                if (iSOS>=0) {
     503                  int numberTimesAtOne = mark[iColumn];
     504                  int numberTimesNonZero = nonzero[iColumn]+
     505                    numberTimesAtOne;
     506                  if (numberTimesAtOne<nCheck&&
     507                      numberTimesNonZero) {
     508                    mixed[iSOS]+=
     509                      CoinMin(numberTimesNonZero,
     510                              nCheck-numberTimesNonZero);
     511                  }
     512                }
     513              }
     514            }
     515            int nFix=0;
     516            for (int i=0;i<numberRows;i++) {
     517              if (bestDj[i]<1.0e25) {
     518                sort[nFix] = -bestDj[i]+1.0e8*mixed[i];
     519                mixed[nFix++]=i;
     520              }
     521            }
     522            CoinSort_2(sort,sort+nFix,mixed);
     523            nFix = CoinMin(nFix,numberSetsToFix);
     524            memset(sort,0,sizeof(double)*numberRows);
     525            for (int i=0;i<nFix;i++)
     526              sort[mixed[i]]=1.0;
     527            delete [] mixed;
     528            for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
     529              if (colUpper[iColumn]>colLower[iColumn]) {
     530                if (solution[iColumn]>0.9999) {
     531                  int iSOS=-1;
     532                  for (CoinBigIndex j = columnStart[iColumn];
     533                       j < columnStart[iColumn] + columnLength[iColumn]; j++) {
     534                    int iRow = row[j];
     535                    if (bestDj[iRow]<1.0e25) {
     536                      iSOS=iRow;
     537                      break;
     538                    }
     539                  }
     540                  if (iSOS>=0&&sort[iSOS]) {
     541                    newSolver->setColLower(iColumn,1.0);
     542                    nFixed++;
     543                  }
     544                }
     545              }
     546            }
     547            char line[100];
     548            sprintf(line,"Heuristic %s fixed %d to one",
     549                    heuristicName(),
     550                    nFixed);
     551            model_->messageHandler()->message(CBC_FPUMP1, model_->messages())
     552              << line
     553              << CoinMessageEol;
     554            delete [] mark;
     555            delete [] nonzero;
     556            delete [] saveUpper;
     557            numberFixed=numberColumns;
     558            djTolerance = 1.0e30;
    409559          }
    410560        }
     
    433583      djTolerance = CoinMax(sort[last],1.0e-5);
    434584      delete [] sort;
    435     } else if (type==11) {
     585    } else if (type==12) {
    436586      // Do layered in a different way
    437587      int numberRows = solver->getNumRows();
Note: See TracChangeset for help on using the changeset viewer.