Changeset 1499


Ignore:
Timestamp:
Aug 31, 2010 7:14:51 AM (9 years ago)
Author:
forrest
Message:

a few more rens heuristics

Location:
trunk/Cbc/src
Files:
5 edited

Legend:

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

    r1432 r1499  
    2424#include "CbcStrategy.hpp"
    2525#include "CglPreProcess.hpp"
     26#include "CglGomory.hpp"
    2627#include "CglProbing.hpp"
    2728#include "OsiAuxInfo.hpp"
     
    830831    solver->setHintParam(OsiDoReducePrint, true, OsiHintTry);
    831832    solver->setHintParam(OsiDoPresolveInInitial, false, OsiHintTry);
    832     solver->setDblParam(OsiDualObjectiveLimit, cutoff*solver->getObjSense());
     833    double signedCutoff = cutoff*solver->getObjSense();
     834    solver->setDblParam(OsiDualObjectiveLimit, signedCutoff);
    833835    solver->initialSolve();
    834836    if (solver->isProvenOptimal()) {
     
    896898                    // No small fathoming
    897899                    model.setFastNodeDepth(-1);
    898                     model.setCutoff(cutoff);
     900                    model.setCutoff(signedCutoff);
     901                    // Don't do if original fraction > 1.0 and too large
     902                    if (fractionSmall_>1.0) {
     903                      /* 1.4 means -1 nodes if >.4
     904                         2.4 means -1 nodes if >.5 and 0 otherwise
     905                         3.4 means -1 nodes if >.6 and 0 or 5
     906                         4.4 means -1 nodes if >.7 and 0, 5 or 10
     907                      */
     908                      double fraction = fractionSmall_-floor(fractionSmall_);
     909                      if (ratio>fraction) {
     910                        int type = static_cast<int>(floor(fractionSmall_*0.1));
     911                        int over = static_cast<int>(ceil(ratio-fraction));
     912                        int maxNodes[]={-1,0,5,10};
     913                        if (type>over)
     914                          numberNodes=maxNodes[type-over];
     915                        else
     916                          numberNodes=-1;
     917                      }
     918                    }
    899919                    model.setMaximumNodes(numberNodes);
    900920                    model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
     
    913933                    model.gutsOfCopy(*model_, 2);
    914934                    for (int i = 0; i < model.numberCutGenerators(); i++) {
    915                         model.cutGenerator(i)->setTiming(true);
     935                        CbcCutGenerator * generator = model.cutGenerator(i);
     936                        CglGomory * gomory = dynamic_cast<CglGomory *>
     937                          (generator->generator());
     938                        if (gomory&&gomory->originalSolver())
     939                          gomory->passInOriginalSolver(model.solver());
     940                        generator->setTiming(true);
    916941                        // Turn on if was turned on
    917942                        int iOften = model_->cutGenerator(i)->howOften();
    918943#ifdef CLP_INVESTIGATE
    919944                        printf("Gen %d often %d %d\n",
    920                                i, model.cutGenerator(i)->howOften(),
     945                               i, generator->howOften(),
    921946                               iOften);
    922947#endif
    923948                        if (iOften > 0)
    924                             model.cutGenerator(i)->setHowOften(iOften % 1000000);
     949                            generator->setHowOften(iOften % 1000000);
    925950                        if (model_->cutGenerator(i)->howOftenInSub() == -200)
    926                             model.cutGenerator(i)->setHowOften(-100);
     951                            generator->setHowOften(-100);
    927952                    }
    928                     model.setCutoff(cutoff);
     953                    model.setCutoff(signedCutoff);
    929954                    // make sure can't do nested search! but allow heuristics
    930955                    model.setSpecialOptions((model.specialOptions()&(~(512 + 2048))) | 1024);
     
    9781003                    if (!gotPump) {
    9791004                        CbcHeuristicFPump heuristic4;
    980                         heuristic4.setMaximumPasses(10);
     1005                        if (fractionSmall_<=1.0)
     1006                          heuristic4.setMaximumPasses(10);
    9811007                        int pumpTune = feasibilityPumpOptions_;
    9821008                        if (pumpTune > 0) {
     
    10961122                        double value = solver3->getObjSense() * solver3->getObjValue();
    10971123                        heuristic.setInputSolution(solver3->getColSolution(), value);
    1098                         model.setCutoff(value + 1.0e-7*(1.0 + fabs(value)));
     1124                        value = value + 1.0e-7*(1.0 + fabs(value));
     1125                        value *= solver3->getObjSense();
     1126                        model.setCutoff(value);
    10991127                        model.addHeuristic(&heuristic, "Previous solution", 0);
    11001128                        //printf("added seren\n");
    11011129                    } else {
    11021130                        double value = model_->getMinimizationObjValue();
    1103                         model.setCutoff(value + 1.0e-7*(1.0 + fabs(value)));
     1131                        value = value + 1.0e-7*(1.0 + fabs(value));
     1132                        value *= solver3->getObjSense();
     1133                        model.setCutoff(value);
    11041134#ifdef CLP_INVESTIGATE
    11051135                        printf("NOT added seren\n");
     
    11261156                    }
    11271157                    model.setWhenCuts(999998);
     1158#define ALWAYS_DUAL
     1159#ifdef ALWAYS_DUAL
     1160                    OsiSolverInterface * solver = model.solver();
     1161                    bool takeHint;
     1162                    OsiHintStrength strength;
     1163                    solver->getHintParam(OsiDoDualInResolve, takeHint, strength);
     1164                    solver->setHintParam(OsiDoDualInResolve, true, OsiHintDo);
     1165#endif
    11281166                    model.branchAndBound();
     1167#ifdef ALWAYS_DUAL
     1168                    solver->setHintParam(OsiDoDualInResolve, takeHint, strength);
     1169#endif
    11291170#ifdef COIN_DEVELOP
    11301171                    printf("sub branch %d nodes, %d iterations - max %d\n",
     
    11811222#endif
    11821223                    process.postProcess(*model.solver());
    1183                     if (solver->isProvenOptimal() && solver->getObjValue() < cutoff) {
     1224                    if (solver->isProvenOptimal() && solver->getObjValue()*solver->getObjSense() < cutoff) {
    11841225                        // Solution now back in solver
    11851226                        int numberColumns = solver->getNumCols();
  • trunk/Cbc/src/CbcHeuristicRENS.cpp

    r1432 r1499  
    1313#include "CbcMessage.hpp"
    1414#include "CbcHeuristicRENS.hpp"
     15#include "CoinWarmStartBasis.hpp"
    1516#include "CbcBranchActual.hpp"
    1617#include "CbcStrategy.hpp"
     
    2223{
    2324    numberTries_ = 0;
     25    rensType_ = 0;
    2426    whereFrom_ = 256 + 1;
    2527}
     
    3133{
    3234    numberTries_ = 0;
     35    rensType_ = 0;
    3336    whereFrom_ = 256 + 1;
    3437}
     
    5356        CbcHeuristic::operator=(rhs);
    5457        numberTries_ = rhs.numberTries_;
     58        rensType_ = rhs.rensType_;
    5559    }
    5660    return *this;
     
    6165        :
    6266        CbcHeuristic(rhs),
    63         numberTries_(rhs.numberTries_)
     67        numberTries_(rhs.numberTries_),
     68        rensType_(rhs.rensType_)
    6469{
    6570}
     
    7580    int returnCode = 0;
    7681    const double * bestSolution = model_->bestSolution();
    77     if (numberTries_ || (when() < 2 && bestSolution))
     82    if ((numberTries_&&(rensType_&16)==0) || numberTries_>1 || (when() < 2 && bestSolution))
    7883        return 0;
    7984    numberTries_++;
     
    8489
    8590    const double * currentSolution = solver->getColSolution();
     91    const double * dj = solver->getReducedCost();
    8692    OsiSolverInterface * newSolver = cloneBut(3); // was model_->continuousSolver()->clone();
     93    int numberColumns = newSolver->getNumCols();
     94    double direction = newSolver->getObjSense();
     95    int type = rensType_&15;
     96    double djTolerance = (type!=1) ? -1.0e30 : 1.0e-4;
    8797    const double * colLower = newSolver->getColLower();
    8898    const double * colUpper = newSolver->getColUpper();
     99    if ((type&3)==3) {
     100        double total=0.0;
     101        int n=0;
     102        CoinWarmStartBasis * basis =
     103          dynamic_cast<CoinWarmStartBasis *>(solver->getWarmStart()) ;
     104        if (basis) {
     105            for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
     106              if (colUpper[iColumn]>colLower[iColumn]&&
     107                  basis->getStructStatus(iColumn) !=
     108                  CoinWarmStartBasis::basic) {
     109                  n++;
     110                  total += fabs(dj[iColumn]);
     111              }
     112            }
     113            if (n)
     114                djTolerance = (0.01*total)/static_cast<double>(n);
     115            delete basis;
     116        }
     117    }
    89118
    90119    double primalTolerance;
     
    95124    int numberTightened = 0;
    96125    int numberAtBound = 0;
    97     int numberColumns = newSolver->getNumCols();
    98126    int numberContinuous = numberColumns - numberIntegers;
    99127
     
    105133        value = CoinMax(value, lower);
    106134        value = CoinMin(value, upper);
     135        double djValue=dj[iColumn]*direction;
    107136#define RENS_FIX_ONLY_LOWER
    108137#ifndef RENS_FIX_ONLY_LOWER
     
    121150#else
    122151        if (fabs(value - floor(value + 0.5)) < 1.0e-8 &&
    123                 floor(value + 0.5) == lower) {
    124             value = floor(value + 0.5);
    125             numberAtBound++;
    126             newSolver->setColLower(iColumn, value);
    127             newSolver->setColUpper(iColumn, value);
    128             numberFixed++;
    129         } else if (colUpper[iColumn] - colLower[iColumn] >= 2.0) {
     152                floor(value + 0.5) == lower &&
     153            djValue > djTolerance ) {
     154          value = floor(value + 0.5);
     155          numberAtBound++;
     156          newSolver->setColLower(iColumn, value);
     157          newSolver->setColUpper(iColumn, value);
     158          numberFixed++;
     159        } else if (fabs(value - floor(value + 0.5)) < 1.0e-8 &&
     160                floor(value + 0.5) == upper &&
     161                   -djValue > djTolerance && (djTolerance > 0.0||type==2)) {
     162          value = floor(value + 0.5);
     163          numberAtBound++;
     164          newSolver->setColLower(iColumn, value);
     165          newSolver->setColUpper(iColumn, value);
     166          numberFixed++;
     167        } else if (colUpper[iColumn] - colLower[iColumn] >= 2.0 &&
     168                   djTolerance <0.0) {
    130169            numberTightened++;
    131170            if (fabs(value - floor(value + 0.5)) < 1.0e-8) {
     
    145184    }
    146185    if (numberFixed > numberIntegers / 5) {
    147         if (numberContinuous > numberIntegers && numberFixed < numberColumns / 5) {
     186        if ( numberFixed < numberColumns / 5) {
    148187#define RENS_FIX_CONTINUOUS
    149188#ifdef RENS_FIX_CONTINUOUS
     
    153192            double sumDj = 0.0;
    154193            const double * dj = newSolver->getReducedCost();
    155             double direction = newSolver->getObjSense();
    156194            for (int iColumn = 0; iColumn < numberColumns; iColumn++) {
    157195                if (!newSolver->isInteger(iColumn)) {
  • trunk/Cbc/src/CbcHeuristicRENS.hpp

    r1432 r1499  
    4747                         double * newSolution);
    4848
     49    /// Set type
     50    inline void setRensType(int value)
     51    { rensType_ = value;}
     52
    4953protected:
    5054    // Data
    5155    /// Number of tries
    5256    int numberTries_;
     57    /** Type
     58        0 - fix at LB
     59        1 - fix on dj
     60        2 - fix at UB as well
     61        3 - fix on 0.01*average dj
     62        add 16 to allow two tries
     63    */
     64    int rensType_;
    5365};
    5466
  • trunk/Cbc/src/CbcSolver.cpp

    r1482 r1499  
    39963996                                    }
    39973997                                }
    3998                                 babModel_->addCutGenerator(&gomoryGen, translate[gomoryAction], "Gomory");
     3998                                int extra3 = parameters_[whichParam(CBC_PARAM_INT_EXTRA3, numberParameters_, parameters_)].intValue();
     3999                                if (extra3>=100) {
     4000                                  // replace
     4001                                  gomoryGen.passInOriginalSolver(babModel_->solver());
     4002                                  gomoryGen.setGomoryType(2);
     4003                                  extra3 = -1;
     4004                                  parameters_[whichParam(CBC_PARAM_INT_EXTRA3, numberParameters_, parameters_)].setIntValue(extra3);
     4005                                  babModel_->addCutGenerator(&gomoryGen, translate[gomoryAction], "GomoryL");
     4006                                } else {
     4007                                  babModel_->addCutGenerator(&gomoryGen, translate[gomoryAction], "Gomory");
     4008                                }
    39994009                                accuracyFlag[numberGenerators] = 3;
    40004010                                switches[numberGenerators++] = 0;
     4011                                if (extra3>=10) {
     4012                                  // just root if 10
     4013                                  int itype=-99;
     4014                                  if (extra3>=20) {
     4015                                    extra3-=10;
     4016                                    itype = translate[gomoryAction];
     4017                                  }
     4018                                  gomoryGen.passInOriginalSolver(babModel_->solver());
     4019                                  babModel_->addCutGenerator(&gomoryGen, itype, "GomoryL2");
     4020                                  accuracyFlag[numberGenerators] = 3;
     4021                                  switches[numberGenerators++] = 0;
     4022                                  extra3 -= 10;
     4023                                  parameters_[whichParam(CBC_PARAM_INT_EXTRA3, numberParameters_, parameters_)].setIntValue(extra3);
     4024                                }
    40014025                            }
    40024026#ifdef CLIQUE_ANALYSIS
     
    52815305                                    // use osl in gomory (may not if CglGomory decides not to)
    52825306                                    int numberGenerators = babModel_->numberCutGenerators();
     5307                                    int nGomory=0;
    52835308                                    for (int iGenerator = 0; iGenerator < numberGenerators;
    52845309                                            iGenerator++) {
     
    52865311                                        CglGomory * gomory = dynamic_cast<CglGomory *>
    52875312                                                             (generator->generator());
    5288                                         if (gomory)
     5313                                        if (gomory) {
     5314                                          if (nGomory<2) {
    52895315                                            gomory->useAlternativeFactorization();
     5316                                          } else if (gomory->originalSolver()) {
     5317                                            OsiClpSolverInterface * clpSolver = dynamic_cast<OsiClpSolverInterface *>(gomory->originalSolver());
     5318                                            if (clpSolver) {
     5319                                              ClpSimplex * simplex = clpSolver->getModelPtr();
     5320                                              simplex->factorization()->setGoOslThreshold(0);
     5321                                            }
     5322                                          }
     5323                                            nGomory++;
     5324                                        }
    52905325                                    }
    52915326                                }
  • trunk/Cbc/src/CbcSolverHeuristics.cpp

    r1393 r1499  
    13541354        anyToDo = true;
    13551355    }
     1356    if ((useRENS==7 && kType==1) || (useRENS==8 && kType==2)) {
     1357        useRENS=1+2*(useRENS-7);
     1358        CbcHeuristicRENS heuristic6a(*model);
     1359        heuristic6a.setHeuristicName("RENSdj");
     1360        heuristic6a.setFractionSmall(0.6/*3.4*/);
     1361        heuristic6a.setFeasibilityPumpOptions(3);
     1362        heuristic6a.setNumberNodes(10);
     1363        heuristic6a.setWhereFrom(4*256+4*1);
     1364        heuristic6a.setWhen(2);
     1365        heuristic6a.setRensType(1+16);
     1366        model->addHeuristic(&heuristic6a) ;
     1367        heuristic6a.setHeuristicName("RENSub");
     1368        heuristic6a.setFractionSmall(0.4);
     1369        heuristic6a.setFeasibilityPumpOptions(1008003);
     1370        heuristic6a.setNumberNodes(50);
     1371        heuristic6a.setWhereFrom(4*256+4*1);
     1372        heuristic6a.setWhen(2);
     1373        heuristic6a.setRensType(2+16);
     1374        model->addHeuristic(&heuristic6a) ;
     1375    }
    13561376    if (useRENS >= kType && useRENS <= kType + 1) {
    13571377#ifndef JJF_ONE
Note: See TracChangeset for help on using the changeset viewer.