Ignore:
Timestamp:
Aug 14, 2007 6:36:36 AM (12 years ago)
Author:
forrest
Message:

try and speed up feasibility pump

File:
1 edited

Legend:

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

    r747 r750  
    4040#include "OsiRowCutDebugger.hpp"
    4141#include "OsiChooseVariable.hpp"
     42#include "OsiAuxInfo.hpp"
    4243//#define USER_HAS_FAKE_CLP
    4344//#define USER_HAS_FAKE_CBC
     
    14311432  parameters[whichParam(COMBINE,numberParameters,parameters)].setCurrentOption("on");
    14321433  parameters[whichParam(RINS,numberParameters,parameters)].setCurrentOption("off");
     1434  parameters[whichParam(LOCALTREE,numberParameters,parameters)].setCurrentOption("off");
    14331435  parameters[whichParam(COSTSTRATEGY,numberParameters,parameters)].setCurrentOption("off");
    14341436}
     1437/* 1 - add heuristics to model
     1438   2 - do heuristics (and set cutoff and best solution)
     1439   3 - for miplib test so skip some
     1440*/
     1441static int doHeuristics(CbcModel * model,int type)
     1442{
     1443  bool anyToDo=false;
     1444  int logLevel = parameters[whichParam(LOGLEVEL,numberParameters,parameters)].intValue();
     1445  int useFpump = parameters[whichParam(FPUMP,numberParameters,parameters)].currentOptionAsInteger();
     1446  int useRounding = parameters[whichParam(ROUNDING,numberParameters,parameters)].currentOptionAsInteger();
     1447  int useGreedy = parameters[whichParam(GREEDY,numberParameters,parameters)].currentOptionAsInteger();
     1448  int useCombine = parameters[whichParam(COMBINE,numberParameters,parameters)].currentOptionAsInteger();
     1449  int useRINS = parameters[whichParam(RINS,numberParameters,parameters)].currentOptionAsInteger();
     1450  // FPump done first as it only works if no solution
     1451  int kType = (type<3) ? type : 1;
     1452  if (useFpump>=kType) {
     1453    anyToDo=true;
     1454    CbcHeuristicFPump heuristic4(*model);
     1455    heuristic4.setFractionSmall(0.6);
     1456    heuristic4.setMaximumPasses(parameters[whichParam(FPUMPITS,numberParameters,parameters)].intValue());
     1457    int pumpTune=parameters[whichParam(FPUMPTUNE,numberParameters,parameters)].intValue();
     1458    if (pumpTune>0) {
     1459      /*
     1460        >=10000000 for using obj
     1461        >=1000000 use as accumulate switch
     1462        >=1000 use index+1 as number of large loops
     1463        >=100 use 0.05 objvalue as increment
     1464        >=10 use +0.1 objvalue for cutoff (add)
     1465        1 == fix ints at bounds, 2 fix all integral ints, 3 and continuous at bounds
     1466        4 and static continuous, 5 as 3 but no internal integers
     1467        6 as 3 but all slack basis!
     1468      */
     1469      double value = model->solver()->getObjSense()*model->solver()->getObjValue();
     1470      int w = pumpTune/10;
     1471      int c = w % 10;
     1472      w /= 10;
     1473      int i = w % 10;
     1474      w /= 10;
     1475      int r = w;
     1476      int accumulate = r/1000;
     1477      r -= 1000*accumulate;
     1478      if (accumulate>=10) {
     1479        int which = accumulate/10;
     1480        accumulate -= 10*which;
     1481        which--;
     1482        // weights and factors
     1483        double weight[]={0.1,0.1,0.5,0.5,1.0,1.0,5.0,5.0};
     1484        double factor[] = {0.1,0.5,0.1,0.5,0.1,0.5,0.1,0.5};
     1485        heuristic4.setInitialWeight(weight[which]);
     1486        heuristic4.setWeightFactor(factor[which]);
     1487      }
     1488      // fake cutoff
     1489      if (logLevel>1)
     1490        printf("Setting ");
     1491      if (c) {
     1492        double cutoff;
     1493        model->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
     1494        cutoff = CoinMin(cutoff,value + 0.1*fabs(value)*c);
     1495        double dextra1 = parameters[whichParam(DEXTRA1,numberParameters,parameters)].doubleValue();
     1496        if (dextra1)
     1497          cutoff=dextra1;
     1498        heuristic4.setFakeCutoff(cutoff);
     1499        if (logLevel>1)
     1500          printf("fake cutoff of %g ",cutoff);
     1501      }
     1502      if (i||r) {
     1503        // also set increment
     1504        double increment = (0.01*i+0.005)*(fabs(value)+1.0e-12);
     1505        double dextra2 = parameters[whichParam(DEXTRA2,numberParameters,parameters)].doubleValue();
     1506        if (dextra2)
     1507          increment = dextra2;
     1508        heuristic4.setAbsoluteIncrement(increment);
     1509        heuristic4.setAccumulate(accumulate);
     1510        heuristic4.setMaximumRetries(r+1);
     1511        if (logLevel>1) {
     1512          if (i)
     1513            printf("increment of %g ",heuristic4.absoluteIncrement());
     1514          if (accumulate)
     1515            printf("accumulate of %d ",accumulate);
     1516          printf("%d retries ",r+2);
     1517        }
     1518      }
     1519      pumpTune = pumpTune%100;
     1520      if (logLevel>1)
     1521        printf("and setting when to %d\n",pumpTune+10);
     1522      if (pumpTune==6)
     1523        pumpTune =13;
     1524      heuristic4.setWhen(pumpTune+10);
     1525    }
     1526    heuristic4.setHeuristicName("feasibility pump");
     1527    model->addHeuristic(&heuristic4);
     1528  }
     1529  if (useRounding>=type) {
     1530    CbcRounding heuristic1(*model);
     1531    heuristic1.setHeuristicName("rounding");
     1532    model->addHeuristic(&heuristic1) ;
     1533    anyToDo=true;
     1534  }
     1535  if (useCombine>=type) {
     1536    CbcHeuristicLocal heuristic2(*model);
     1537    heuristic2.setHeuristicName("combine solutions");
     1538    heuristic2.setFractionSmall(0.6);
     1539    heuristic2.setSearchType(1);
     1540    model->addHeuristic(&heuristic2);
     1541    anyToDo=true;
     1542  }
     1543  if (useGreedy>=type) {
     1544    CbcHeuristicGreedyCover heuristic3(*model);
     1545    heuristic3.setHeuristicName("greedy cover");
     1546    CbcHeuristicGreedyEquality heuristic3a(*model);
     1547    heuristic3a.setHeuristicName("greedy equality");
     1548    model->addHeuristic(&heuristic3);
     1549    model->addHeuristic(&heuristic3a);
     1550    anyToDo=true;
     1551  }
     1552  if (useRINS>=kType) {
     1553    CbcHeuristicRINS heuristic5(*model);
     1554    heuristic5.setHeuristicName("RINS");
     1555    heuristic5.setFractionSmall(0.6);
     1556    model->addHeuristic(&heuristic5) ;
     1557    anyToDo=true;
     1558  }
     1559  if (type==2&&anyToDo) {
     1560    // Do heuristics
     1561    // clean copy
     1562    CbcModel model2(*model);
     1563    if (logLevel<=1)
     1564      model2.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
     1565    OsiBabSolver defaultC;
     1566    //solver_->setAuxiliaryInfo(&defaultC);
     1567    model2.passInSolverCharacteristics(&defaultC);
     1568    // Save bounds
     1569    int numberColumns = model2.solver()->getNumCols();
     1570    model2.createContinuousSolver();
     1571    bool cleanModel = !model2.numberIntegers()&&!model2.numberObjects();
     1572    model2.findIntegers(false);
     1573    model2.doHeuristicsAtRoot(true);
     1574    if (cleanModel)
     1575      model2.zapIntegerInformation(false);
     1576    if (model2.bestSolution()) {
     1577      double value = model2.getMinimizationObjValue();
     1578      model->setCutoff(value);
     1579      model->setBestSolution(model2.bestSolution(),numberColumns,value);
     1580      model->setSolutionCount(1);
     1581      model->setNumberHeuristicSolutions(1);
     1582    }
     1583    return 0;
     1584  } else {
     1585    return 0;
     1586  }
     1587}
    14351588/* Meaning of whereFrom:
    14361589   1 after initial solve by dualsimplex etc
     
    14391592   4 just after branchAndBound (before postprocessing)
    14401593   5 after postprocessing
     1594   6 after a user called heuristic phase
    14411595*/
    14421596int CbcMain1 (int argc, const char *argv[],
     
    14761630  }
    14771631  CbcModel * babModel = NULL;
     1632  double time0;
    14781633  {
    14791634    double time1 = CoinCpuTime(),time2;
     1635    time0=time1;
    14801636    bool goodModel=(originalSolver->getNumCols()) ? true : false;
    14811637
     
    18111967    bool storedCuts = false;
    18121968
    1813     bool useRounding=true;
    1814     bool useFpump=true;
    1815     bool useGreedy=true;
    1816     bool useCombine=true;
    1817     bool useLocalTree=false;
    1818     bool useRINS=false;
    18191969    int useCosts=0;
    18201970    // don't use input solution
     
    18572007      // next command
    18582008      field=CoinReadGetCommand(argc,argv);
     2009      // Reset time
     2010      time1 = CoinCpuTime();
    18592011      // adjust field if has odd trailing characters
    18602012      char temp [200];
     
    21202272                cutPassInTree = value;
    21212273              else if (parameters[iParam].type()==FPUMPITS)
    2122                 { useFpump = true;parameters[iParam].setIntValue(value);}
     2274                { parameters[iParam].setIntValue(value);}
    21232275              else if (parameters[iParam].type()==STRONGBRANCHING||
    21242276                       parameters[iParam].type()==NUMBERBEFORE)
     
    23142466            case ROUNDING:
    23152467              defaultSettings=false; // user knows what she is doing
    2316               useRounding = action;
    23172468              break;
    23182469            case FPUMP:
    23192470              defaultSettings=false; // user knows what she is doing
    2320               useFpump=action;
    23212471              break;
    23222472            case RINS:
    2323               useRINS=action;
    23242473              break;
    23252474            case CUTSSTRATEGY:
     
    23492498              break;
    23502499            case HEURISTICSTRATEGY:
    2351               useRounding = action;
    2352               useGreedy = action;
    2353               useCombine = action;
    2354               //useLocalTree = action;
    2355               useFpump=action;
    23562500              parameters[whichParam(ROUNDING,numberParameters,parameters)].setCurrentOption(action);
    23572501              parameters[whichParam(GREEDY,numberParameters,parameters)].setCurrentOption(action);
     
    23622506            case GREEDY:
    23632507              defaultSettings=false; // user knows what she is doing
    2364               useGreedy = action;
    23652508              break;
    23662509            case COMBINE:
    23672510              defaultSettings=false; // user knows what she is doing
    2368               useCombine = action;
    23692511              break;
    23702512            case LOCALTREE:
    23712513              defaultSettings=false; // user knows what she is doing
    2372               useLocalTree = action;
    23732514              break;
    23742515            case COSTSTRATEGY:
     
    24402581                //printf("dualize %d\n",dualize);
    24412582                model2 = ((ClpSimplexOther *) model2)->dualOfModel();
    2442                 sprintf(generalPrint,"Dual of model has %d rows and %d columns\n",
     2583                sprintf(generalPrint,"Dual of model has %d rows and %d columns",
    24432584                       model2->numberRows(),model2->numberColumns());
    24442585                generalMessageHandler->message(CLP_GENERAL,generalMessages)
     
    24582599                  if (preSolve<=100) {
    24592600                    presolveType=ClpSolve::presolveNumber;
    2460                     sprintf(generalPrint,"Doing %d presolve passes - picking up non-costed slacks\n",
     2601                    sprintf(generalPrint,"Doing %d presolve passes - picking up non-costed slacks",
    24612602                           preSolve);
    24622603                    generalMessageHandler->message(CLP_GENERAL,generalMessages)
     
    24672608                    preSolve -=100;
    24682609                    presolveType=ClpSolve::presolveNumberCost;
    2469                     sprintf(generalPrint,"Doing %d presolve passes - picking up costed slacks\n",
     2610                    sprintf(generalPrint,"Doing %d presolve passes - picking up costed slacks",
    24702611                           preSolve);
    24712612                    generalMessageHandler->message(CLP_GENERAL,generalMessages)
     
    28152956              int nOut = numberRows-clpSolver->getNumRows();
    28162957              if (nOut&&!noPrinting)
    2817                 sprintf(generalPrint,"%d rows eliminated\n",nOut);
     2958                sprintf(generalPrint,"%d rows eliminated",nOut);
    28182959              generalMessageHandler->message(CLP_GENERAL,generalMessages)
    28192960                << generalPrint
     
    28422983            } else {
    28432984              std::cout<<"** Current model not valid"<<std::endl;
     2985            }
     2986            break;
     2987          case DOHEURISTIC:
     2988            if (goodModel) {
     2989              // Actually do heuristics
     2990              doHeuristics(&model,2);
     2991              if (model.bestSolution()) {
     2992                model.setProblemStatus(1);
     2993                model.setSecondaryStatus(6);
     2994              }
     2995              int returnCode=callBack(&model,6);
     2996              if (returnCode) {
     2997                // exit if user wants
     2998                delete babModel;
     2999                return returnCode;
     3000              }
    28443001            }
    28453002            break;
     
    34093566                    solver2->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
    34103567                }
    3411                 babModel->setOriginalColumns(process.originalColumns());
    34123568#ifdef COIN_HAS_ASL
    34133569                if (!solver2&&usingAmpl) {
     
    34233579                if (!noPrinting) {
    34243580                  if (!solver2) {
    3425                     sprintf(generalPrint,"Pre-processing says infeasible or unbounded\n");
     3581                    sprintf(generalPrint,"Pre-processing says infeasible or unbounded");
    34263582                    generalMessageHandler->message(CLP_GENERAL,generalMessages)
    34273583                      << generalPrint
     
    34593615                solver2 = solver2->clone();
    34603616                babModel->assignSolver(solver2);
     3617                babModel->setOriginalColumns(process.originalColumns());
    34613618                babModel->initialSolve();
    34623619                babModel->setMaximumSeconds(timeLeft-(CoinCpuTime()-time1));
     
    35983755                delete [] dsort;
    35993756              }
    3600               // FPump done first as it only works if no solution
    3601               CbcHeuristicFPump heuristic4(*babModel);
    3602               heuristic4.setFractionSmall(0.6);
    3603               if (useFpump) {
    3604                 heuristic4.setMaximumPasses(parameters[whichParam(FPUMPITS,numberParameters,parameters)].intValue());
    3605                 int pumpTune=parameters[whichParam(FPUMPTUNE,numberParameters,parameters)].intValue();
    3606                 if (pumpTune>0) {
    3607                   /*
    3608                     >=10000000 for using obj
    3609                     >=1000000 use as accumulate switch
    3610                     >=1000 use index+1 as number of large loops
    3611                     >=100 use 0.05 objvalue as increment
    3612                     >=10 use +0.1 objvalue for cutoff (add)
    3613                     1 == fix ints at bounds, 2 fix all integral ints, 3 and continuous at bounds
    3614                     4 and static continuous, 5 as 3 but no internal integers
    3615                     6 as 3 but all slack basis!
    3616                   */
    3617                   int logLevel = parameters[log].intValue();
    3618                   double value = babModel->solver()->getObjSense()*babModel->solver()->getObjValue();
    3619                   int w = pumpTune/10;
    3620                   int c = w % 10;
    3621                   w /= 10;
    3622                   int i = w % 10;
    3623                   w /= 10;
    3624                   int r = w;
    3625                   int accumulate = r/1000;
    3626                   r -= 1000*accumulate;
    3627                   if (accumulate>=10) {
    3628                     int which = accumulate/10;
    3629                     accumulate -= 10*which;
    3630                     which--;
    3631                     // weights and factors
    3632                     double weight[]={0.1,0.1,0.5,0.5,1.0,1.0,5.0,5.0};
    3633                     double factor[] = {0.1,0.5,0.1,0.5,0.1,0.5,0.1,0.5};
    3634                     heuristic4.setInitialWeight(weight[which]);
    3635                     heuristic4.setWeightFactor(factor[which]);
    3636                   }
    3637                   // fake cutoff
    3638                   if (logLevel>1)
    3639                     printf("Setting ");
    3640                   if (c) {
    3641                     double cutoff;
    3642                     babModel->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
    3643                     cutoff = CoinMin(cutoff,value + 0.1*fabs(value)*c);
    3644                     double dextra1 = parameters[whichParam(DEXTRA1,numberParameters,parameters)].doubleValue();
    3645                     if (dextra1)
    3646                       cutoff=dextra1;
    3647                     heuristic4.setFakeCutoff(cutoff);
    3648                     if (logLevel>1)
    3649                       printf("fake cutoff of %g ",cutoff);
    3650                   }
    3651                   if (i||r) {
    3652                     // also set increment
    3653                     double increment = (0.01*i+0.005)*(fabs(value)+1.0e-12);
    3654                     double dextra2 = parameters[whichParam(DEXTRA2,numberParameters,parameters)].doubleValue();
    3655                     if (dextra2)
    3656                       increment = dextra2;
    3657                     heuristic4.setAbsoluteIncrement(increment);
    3658                     heuristic4.setAccumulate(accumulate);
    3659                     heuristic4.setMaximumRetries(r+1);
    3660                     if (logLevel>1) {
    3661                       if (i)
    3662                         printf("increment of %g ",heuristic4.absoluteIncrement());
    3663                       if (accumulate)
    3664                         printf("accumulate of %d ",accumulate);
    3665                       printf("%d retries ",r+2);
    3666                     }
    3667                   }
    3668                   pumpTune = pumpTune%100;
    3669                   if (logLevel>1)
    3670                     printf("and setting when to %d\n",pumpTune+10);
    3671                   if (pumpTune==6)
    3672                     pumpTune =13;
    3673                   heuristic4.setWhen(pumpTune+10);
    3674                 }
    3675                 heuristic4.setHeuristicName("feasibility pump");
    3676                 babModel->addHeuristic(&heuristic4);
    3677               }
     3757              // Set up heuristics
     3758              doHeuristics(babModel,(!miplib) ? 1 : 3);
    36783759              if (!miplib) {
    3679                 CbcRounding heuristic1(*babModel);
    3680                 heuristic1.setHeuristicName("rounding");
    3681                 if (useRounding)
    3682                   babModel->addHeuristic(&heuristic1) ;
    3683                 CbcHeuristicLocal heuristic2(*babModel);
    3684                 heuristic2.setHeuristicName("combine solutions");
    3685                 heuristic2.setFractionSmall(0.6);
    3686                 heuristic2.setSearchType(1);
    3687                 if (useCombine)
    3688                   babModel->addHeuristic(&heuristic2);
    3689                 CbcHeuristicGreedyCover heuristic3(*babModel);
    3690                 heuristic3.setHeuristicName("greedy cover");
    3691                 CbcHeuristicGreedyEquality heuristic3a(*babModel);
    3692                 heuristic3a.setHeuristicName("greedy equality");
    3693                 if (useGreedy) {
    3694                   babModel->addHeuristic(&heuristic3);
    3695                   babModel->addHeuristic(&heuristic3a);
    3696                 }
    3697                 if (useLocalTree) {
     3760                if(parameters[whichParam(LOCALTREE,numberParameters,parameters)].currentOptionAsInteger()) {
    36983761                  CbcTreeLocal localTree(babModel,NULL,10,0,0,10000,2000);
    36993762                  babModel->passInTreeHandler(localTree);
    37003763                }
    37013764              }
    3702               CbcHeuristicRINS heuristic5(*babModel);
    3703               heuristic5.setHeuristicName("RINS");
    3704               heuristic5.setFractionSmall(0.6);
    3705               if (useRINS)
    3706                 babModel->addHeuristic(&heuristic5) ;
    37073765              if (type==MIPLIB) {
    37083766                if (babModel->numberStrong()==5&&babModel->numberBeforeTrust()==5)
     
    38433901              int mipOptions = parameters[whichParam(MIPOPTIONS,numberParameters,parameters)].intValue()%10000;
    38443902              if (mipOptions!=(1)) {
    3845                 sprintf(generalPrint,"mip options %d\n",mipOptions);
     3903                sprintf(generalPrint,"mip options %d",mipOptions);
    38463904                generalMessageHandler->message(CLP_GENERAL,generalMessages)
    38473905                  << generalPrint
     
    38643922                int moreMipOptions = parameters[whichParam(MOREMIPOPTIONS,numberParameters,parameters)].intValue();
    38653923                if (moreMipOptions>=0) {
    3866                   sprintf(generalPrint,"more mip options %d\n",moreMipOptions);
     3924                  sprintf(generalPrint,"more mip options %d",moreMipOptions);
    38673925                  generalMessageHandler->message(CLP_GENERAL,generalMessages)
    38683926                    << generalPrint
     
    39954053                      }
    39964054                      babModel->setNumberObjects(n);
     4055                      babModel->zapIntegerInformation();
    39974056                    }
    39984057                    int nMissing=0;
     
    40484107                    }
    40494108                    if (nMissing) {
    4050                       sprintf(generalPrint,"%d SOS variables vanished due to pre processing? - check validity?\n",nMissing);
     4109                      sprintf(generalPrint,"%d SOS variables vanished due to pre processing? - check validity?",nMissing);
    40514110                      generalMessageHandler->message(CLP_GENERAL,generalMessages)
    40524111                        << generalPrint
     
    41094168                        delete [] back;
    41104169                        if (nMissing) {
    4111                           sprintf(generalPrint,"%d SOS variables vanished due to pre processing? - check validity?\n",nMissing);
     4170                          sprintf(generalPrint,"%d SOS variables vanished due to pre processing? - check validity?",nMissing);
    41124171                          generalMessageHandler->message(CLP_GENERAL,generalMessages)
    41134172                            << generalPrint
     
    42784337                        delete [] back;
    42794338                        if (nMissing) {
    4280                           sprintf(generalPrint,"%d SOS variables vanished due to pre processing? - check validity?\n",nMissing);
     4339                          sprintf(generalPrint,"%d SOS variables vanished due to pre processing? - check validity?",nMissing);
    42814340                          generalMessageHandler->message(CLP_GENERAL,generalMessages)
    42824341                            << generalPrint
     
    44504509                }
    44514510                if (testOsiOptions>=0) {
    4452                   sprintf(generalPrint,"Testing OsiObject options %d\n",testOsiOptions);
     4511                  sprintf(generalPrint,"Testing OsiObject options %d",testOsiOptions);
    44534512                  generalMessageHandler->message(CLP_GENERAL,generalMessages)
    44544513                    << generalPrint
     
    47654824                    babModel->makeGlobalCut(rowCutPointer);
    47664825                  }
    4767                 }
     4826                } 
    47684827                // If defaults then increase trust for small models
    47694828                if (!strongChanged) {
     
    53505409                if (dualize) {
    53515410                  model2 = ((ClpSimplexOther *) model2)->dualOfModel();
    5352                   sprintf(generalPrint,"Dual of model has %d rows and %d columns\n",
     5411                  sprintf(generalPrint,"Dual of model has %d rows and %d columns",
    53535412                         model2->numberRows(),model2->numberColumns());
    53545413                  generalMessageHandler->message(CLP_GENERAL,generalMessages)
     
    66106669  #endif
    66116670  model.solver()->setWarmStart(NULL);
     6671  sprintf(generalPrint,"Total time %.2f",CoinCpuTime()-time0);
     6672  generalMessageHandler->message(CLP_GENERAL,generalMessages)
     6673    << generalPrint
     6674    <<CoinMessageEol;
    66126675  return 0;
    66136676}   
Note: See TracChangeset for help on using the changeset viewer.