Ignore:
Timestamp:
Mar 16, 2009 6:30:25 AM (10 years ago)
Author:
forrest
Message:

chnages to try and make faster

File:
1 edited

Legend:

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

    r1121 r1132  
    496496extern bool getHistoryStatistics_;
    497497#endif
     498static double sizeRatio(int numberRowsNow,int numberColumnsNow,
     499                        int numberRowsStart,int numberColumnsStart)
     500{
     501  double valueNow;
     502  if (numberRowsNow*10>numberColumnsNow||numberColumnsNow<200) {
     503    valueNow = 2*numberRowsNow+numberColumnsNow;
     504  } else {
     505    // long and thin - rows are more important
     506    if (numberRowsNow*40>numberColumnsNow)
     507      valueNow = 10*numberRowsNow+numberColumnsNow;
     508    else
     509      valueNow = 200*numberRowsNow+numberColumnsNow;
     510  }
     511  double valueStart;
     512  if (numberRowsStart*10>numberColumnsStart||numberColumnsStart<200) {
     513    valueStart = 2*numberRowsStart+numberColumnsStart;
     514  } else {
     515    // long and thin - rows are more important
     516    if (numberRowsStart*40>numberColumnsStart)
     517      valueStart = 10*numberRowsStart+numberColumnsStart;
     518    else
     519      valueStart = 200*numberRowsStart+numberColumnsStart;
     520  }
     521  //printf("sizeProblem Now %g, %d rows, %d columns\nsizeProblem Start %g, %d rows, %d columns\n",
     522  // valueNow,numberRowsNow,numberColumnsNow,
     523  // valueStart,numberRowsStart,numberColumnsStart);
     524  if (10*numberRowsNow<8*numberRowsStart)
     525    return valueNow/valueStart;
     526  else if (10*numberRowsNow<9*numberRowsStart)
     527    return 1.1*(valueNow/valueStart);
     528  else if (numberRowsNow<numberRowsStart)
     529    return 1.5*(valueNow/valueStart);
     530  else
     531    return 2.0*(valueNow/valueStart);
     532}
     533   
     534
    498535// Do mini branch and bound (return 1 if solution)
    499536int
     
    503540{
    504541  // size before
    505   double before = 2*solver->getNumRows()+solver->getNumCols();
     542  int shiftRows=0;
     543  if (numberNodes<0)
     544    shiftRows = solver->getNumRows()-numberNodes_;
     545  int numberRowsStart = solver->getNumRows()-shiftRows;
     546  int numberColumnsStart = solver->getNumCols();
    506547#ifdef CLP_INVESTIGATE
    507548  printf("%s has %d rows, %d columns\n",
     
    510551  // Use this fraction
    511552  double fractionSmall = fractionSmall_;
     553  double before = 2*numberRowsStart+numberColumnsStart;
    512554  if (before>40000.0) {
    513555    // fairly large - be more conservative
     
    582624#endif
    583625      delete presolvedModel;
     626      double ratio = sizeRatio(afterRows-shiftRows,afterCols,
     627                                 numberRowsStart,numberColumnsStart);
    584628      double after = 2*afterRows+afterCols;
    585       if (after>fractionSmall*before&&after>300&&numberNodes>=0) {
     629      if (ratio>fractionSmall&&after>300&&numberNodes>=0) {
    586630        // Need code to try again to compress further using used
    587631        const int * used =  model_->usedInSolution();
     
    634678            int afterCols2 = presolvedModel->getNumCols();
    635679            delete presolvedModel;
     680            double ratio = sizeRatio(afterRows2-shiftRows,afterCols2,
     681                                 numberRowsStart,numberColumnsStart);
    636682            double after = 2*afterRows2+afterCols2;
    637             if (after>fractionSmall*before&&(after>300||numberNodes<0)) {
     683            if (ratio>fractionSmall&&(after>300||numberNodes<0)) {
    638684              sprintf(generalPrint,"Full problem %d rows %d columns, reduced to %d rows %d columns - %d fixed gives %d, %d - still too large",
    639685                      solver->getNumRows(),solver->getNumCols(),
    640686                      afterRows,afterCols,nFix,afterRows2,afterCols2);
    641687              // If much too big - give up
    642               if (after>0.75*before)
     688              if (ratio>0.75)
    643689                returnCode=-1;
    644690            } else {
     
    654700          }
    655701        }
     702      } else if (ratio>fractionSmall&&after>300) {
     703        returnCode=-1;
    656704      }
    657705    } else {
     
    666714    getHistoryStatistics_=true;
    667715#endif
     716    //printf("small no good\n");
    668717    return returnCode;
    669718  }
     
    708757#endif
    709758      // see if too big
     759      double ratio = sizeRatio(solver2->getNumRows()-shiftRows,solver2->getNumCols(),
     760                                 numberRowsStart,numberColumnsStart);
    710761      double after = 2*solver2->getNumRows()+solver2->getNumCols();
    711       if (after>fractionSmall*before&&(after>300||numberNodes<0)) {
     762      if (ratio>fractionSmall&&(after>300||numberNodes<0)) {
    712763        sprintf(generalPrint,"Full problem %d rows %d columns, reduced to %d rows %d columns - too large",
    713764                solver->getNumRows(),solver->getNumCols(),
     
    717768          <<CoinMessageEol;
    718769        returnCode = -1;
     770        //printf("small no good2\n");
    719771      } else {
    720772        sprintf(generalPrint,"Full problem %d rows %d columns, reduced to %d rows %d columns",
     
    741793          model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
    742794          // Lightweight
    743           CbcStrategyDefaultSubTree strategy(model_,true,5,1,0);
     795          CbcStrategyDefaultSubTree strategy(model_,1,5,1,0);
    744796          model.setStrategy(strategy);
    745797          model.solver()->setIntParam(OsiMaxNumIterationHotStart,10);
     
    775827          model_->solver()->getHintParam(OsiDoReducePrint,takeHint,strength);
    776828          model.solver()->setHintParam(OsiDoReducePrint,takeHint,strength);
    777           CbcStrategyDefault strategy(true,model_->numberStrong(),
     829          CbcStrategyDefault strategy(1,model_->numberStrong(),
    778830                                      model_->numberBeforeTrust());
    779831          // Set up pre-processing - no
     
    787839            model.addCutGenerator(&cuts,1,"Stored from first");
    788840          }
    789         }
    790         if (inputSolution_) {
    791           // translate and add a serendipity heuristic
    792           int numberColumns = solver2->getNumCols();
    793           const int * which = process.originalColumns();
    794           OsiSolverInterface * solver3 = solver2->clone();
    795           for (int i=0;i<numberColumns;i++) {
    796             if (solver3->isInteger(i)) {
    797               int k=which[i];
    798               double value = inputSolution_[k];
    799               solver3->setColLower(i,value);
    800               solver3->setColUpper(i,value);
    801             }
    802           }
    803           solver3->setDblParam(OsiDualObjectiveLimit,COIN_DBL_MAX);
    804           solver3->resolve();
    805           if (solver3->isProvenOptimal()) {
    806             // good
    807             CbcSerendipity heuristic(model);
    808             double value = solver3->getObjSense()*solver3->getObjValue();
    809             heuristic.setInputSolution(solver3->getColSolution(),value);
    810             model.setCutoff(value+1.0e-7*(1.0+fabs(value)));
    811             model.addHeuristic(&heuristic,"previous solution");
    812           }
    813           delete solver3;
    814841        }
    815842        // Do search
     
    844871          if (!gotPump) {
    845872            CbcHeuristicFPump heuristic4;
    846             heuristic4.setMaximumPasses(30);
     873            heuristic4.setMaximumPasses(10);
    847874            int pumpTune=feasibilityPumpOptions_;
    848875            if (pumpTune>0) {
     
    904931          }
    905932        }
     933        //printf("sol %x\n",inputSolution_);
     934        if (inputSolution_) {
     935          // translate and add a serendipity heuristic
     936          int numberColumns = solver2->getNumCols();
     937          const int * which = process.originalColumns();
     938          OsiSolverInterface * solver3 = solver2->clone();
     939          for (int i=0;i<numberColumns;i++) {
     940            if (solver3->isInteger(i)) {
     941              int k=which[i];
     942              double value = inputSolution_[k];
     943              //if (value)
     944              //printf("orig col %d now %d val %g\n",
     945              //       k,i,value);
     946              solver3->setColLower(i,value);
     947              solver3->setColUpper(i,value);
     948            }
     949          }
     950          solver3->setDblParam(OsiDualObjectiveLimit,COIN_DBL_MAX);
     951          solver3->resolve();
     952          if (!solver3->isProvenOptimal()) {
     953            // Try just setting nonzeros
     954            OsiSolverInterface * solver4 = solver2->clone();
     955            for (int i=0;i<numberColumns;i++) {
     956              if (solver4->isInteger(i)) {
     957                int k=which[i];
     958                double value = floor(inputSolution_[k]+0.5);
     959                if (value) {
     960                  solver3->setColLower(i,value);
     961                  solver3->setColUpper(i,value);
     962                }
     963              }
     964            }
     965            solver4->setDblParam(OsiDualObjectiveLimit,COIN_DBL_MAX);
     966            solver4->resolve();
     967            int nBad=-1;
     968            if (solver4->isProvenOptimal()) {
     969              nBad=0;
     970              const double * solution = solver4->getColSolution();
     971              for (int i=0;i<numberColumns;i++) {
     972                if (solver4->isInteger(i)) {
     973                  double value = floor(solution[i]+0.5);
     974                  if (fabs(value-solution[i])>1.0e-6)
     975                    nBad++;
     976                }
     977              }
     978            }
     979            if (nBad) {
     980              delete solver4;
     981            } else {
     982              delete solver3;
     983              solver3=solver4;
     984            }
     985          }
     986          if (solver3->isProvenOptimal()) {
     987            // good
     988            CbcSerendipity heuristic(model);
     989            double value = solver3->getObjSense()*solver3->getObjValue();
     990            heuristic.setInputSolution(solver3->getColSolution(),value);
     991            model.setCutoff(value+1.0e-7*(1.0+fabs(value)));
     992            model.addHeuristic(&heuristic,"Previous solution",0);
     993            //printf("added seren\n");
     994          } else {
     995#ifdef CLP_INVESTIGATE
     996            printf("NOT added seren\n");
     997#endif
     998            solver3->writeMps("bad_seren");
     999            solver->writeMps("orig_seren");
     1000          }
     1001          delete solver3;
     1002        }
    9061003        if (model_->searchStrategy()==2) {
    9071004          model.setNumberStrong(5);
     
    9151012            // Not fast stuff
    9161013            model.setFastNodeDepth(-1);
     1014          } else if (model.fastNodeDepth()>=1000000) {
     1015            // already set
     1016            model.setFastNodeDepth(model.fastNodeDepth()-1000000);
    9171017          }
     1018          model.setWhenCuts(999998);
    9181019          model.branchAndBound();
    9191020#ifdef COIN_DEVELOP
     
    9711072#endif
    9721073          process.postProcess(*model.solver());
    973           if (solver->isProvenOptimal()) {
     1074          if (solver->isProvenOptimal()&&solver->getObjValue()<cutoff) {
    9741075            // Solution now back in solver
    9751076            int numberColumns = solver->getNumCols();
Note: See TracChangeset for help on using the changeset viewer.