Changeset 2092 for trunk/Cbc


Ignore:
Timestamp:
Oct 3, 2014 7:58:33 AM (5 years ago)
Author:
forrest
Message:

symmetry and diving

Location:
trunk/Cbc/src
Files:
8 edited

Legend:

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

    r2040 r2092  
    383383            3 only at root and if no solution
    384384            4 only at root and if this heuristic has not got solution
    385             5 as 3 but decay more
    386             6 decay
     385            5 decay (but only if no solution)
     386            6 if depth <3 or decay
    387387            7 run up to 2 times if solution found 4 otherwise
    388388            */
     
    423423                    if (model_->bestSolution())
    424424                        probability *= 0.5;
     425                } else {
     426                    probability = 1.1;
    425427                }
    426428                break;
     
    12721274                        value *= solver3->getObjSense();
    12731275                        model.setCutoff(value);
     1276                        sprintf(generalPrint, "Unable to insert previous solution - using cutoff of %g",
     1277                                value);
     1278                        model_->messageHandler()->message(CBC_FPUMP1, model_->messages())
     1279                        << generalPrint
     1280                        << CoinMessageEol;
    12741281#ifdef CLP_INVESTIGATE
    12751282                        printf("NOT added seren\n");
  • trunk/Cbc/src/CbcHeuristicDive.cpp

    r1911 r2092  
    291291        int iColumn = integerVariable[i];
    292292        double value = newSolution[iColumn];
     293        // clean
     294        value = CoinMin(value,upperBefore[iColumn]);
     295        value = CoinMax(value,lowerBefore[iColumn]);
     296        newSolution[iColumn] = value;
    293297        if (fabs(floor(value + 0.5) - value) > integerTolerance) {
    294298            numberFractionalVariables++;
  • trunk/Cbc/src/CbcModel.cpp

    r2087 r2092  
    1666016660                    int iHeur ;
    1666116661                    int whereFrom = 3;
     16662                    // allow more heuristics
     16663                    currentPassNumber_=0;
    1666216664                    for (iHeur = 0 ; iHeur < numberHeuristics_ ; iHeur++) {
    1666316665                        // skip if can't run here
  • trunk/Cbc/src/CbcNode.cpp

    r2080 r2092  
    19581958    numberPassesLeft = CoinMax(numberPassesLeft, 2);
    19591959#ifdef COIN_HAS_NTY
    1960     // 1 after, 2 strong, 3 subset
     1960    // 1 after, 2 strong, 3 until depth 5
    19611961    int orbitOption = (model->moreSpecialOptions2()&(128|256))>>7;
    19621962#endif
     
    28132813#endif
    28142814#ifdef COIN_HAS_NTY
    2815             if (orbitOption>1) {
     2815            if (orbitOption==2 /* was >1*/) {
    28162816              CbcSymmetry * symmetryInfo = model->symmetryInfo();
    28172817              CbcNodeInfo * infoX = lastNode ? lastNode->nodeInfo() : NULL;
     
    38413841        worthTrying=true;
    38423842      }
     3843      if (orbitOption==3&&depth_>5)
     3844        worthTrying=false;
    38433845      if (symmetryInfo && worthTrying) {
    3844         if (orbitOption==1) {
     3846        if ((orbitOption&1)==1) {
    38453847          symmetryInfo->ChangeBounds(solver->getColLower(),
    38463848                                     solver->getColUpper(),
     
    38543856          if (solver->messageHandler()->logLevel() > 1)
    38553857            printf("Orbital Branching on %d - way %d n %d\n",kColumn,way(),numberUsefulOrbits);
    3856           if (numberUsefulOrbits<1000) {
     3858          if (numberUsefulOrbits<1000||orbitOption==3) {
    38573859            delete branch_;
    38583860            branch_ = new CbcOrbitalBranchingObject(model,kColumn,1,0,NULL);
  • trunk/Cbc/src/CbcSolver.cpp

    r2086 r2092  
    41074107                                    // say infeasible for solution
    41084108                                    integerStatus = 6;
     4109                                    delete saveSolver;
     4110                                    saveSolver=NULL;
    41094111                                    model_.setProblemStatus(0);
    41104112                                    model_.setSecondaryStatus(1);
     
    46054607                                    // say infeasible for solution
    46064608                                    integerStatus = 6;
     4609                                    delete saveSolver;
     4610                                    saveSolver=NULL;
    46074611                                    // and in babModel_ if exists
    46084612                                    if (babModel_) {
     
    69406944                                    // infeasible
    69416945                                    integerStatus = 6;
     6946                                    delete saveSolver;
     6947                                    saveSolver=NULL;
    69426948                                }
    69436949                            }
  • trunk/Cbc/src/CbcSolverHeuristics.cpp

    r1957 r2092  
    14781478            diveOptions2 = 0;
    14791479        }
    1480         if (diveOptions < 0 || diveOptions > 9)
     1480        if (diveOptions < 0 || diveOptions > 29)
    14811481            diveOptions = 2;
     1482        int diveOptionsNotC=diveOptions;
     1483        if (diveOptions>10) {
     1484          if (diveOptions>20) {
     1485            diveOptions-=20;
     1486            diveOptionsNotC-=20;
     1487          } else {
     1488            diveOptions -= 10;
     1489            diveOptionsNotC = 4;
     1490          }
     1491          useDIVING = 63;
     1492        }
    14821493        if ((useDIVING&1) != 0) {
    14831494            CbcHeuristicDiveVectorLength heuristicDV(*model);
    14841495            heuristicDV.setHeuristicName("DiveVectorLength");
    1485             heuristicDV.setWhen(diveOptions);
     1496            heuristicDV.setWhen(diveOptionsNotC);
    14861497            if (diveOptions2) {
    14871498              heuristicDV.setMaxIterations(majorIterations);
     
    14951506            CbcHeuristicDiveGuided heuristicDG(*model);
    14961507            heuristicDG.setHeuristicName("DiveGuided");
    1497             heuristicDG.setWhen(diveOptions);
     1508            heuristicDG.setWhen(diveOptionsNotC);
    14981509            if (diveOptions2) {
    14991510              heuristicDG.setMaxIterations(majorIterations);
     
    15071518            CbcHeuristicDiveFractional heuristicDF(*model);
    15081519            heuristicDF.setHeuristicName("DiveFractional");
    1509             heuristicDF.setWhen(diveOptions);
     1520            heuristicDF.setWhen(diveOptionsNotC);
    15101521            if (diveOptions2) {
    15111522              heuristicDF.setMaxIterations(majorIterations);
     
    15311542            CbcHeuristicDiveLineSearch heuristicDL(*model);
    15321543            heuristicDL.setHeuristicName("DiveLineSearch");
    1533             heuristicDL.setWhen(diveOptions);
     1544            heuristicDL.setWhen(diveOptionsNotC);
    15341545            if (diveOptions2) {
    15351546              heuristicDL.setMaxIterations(majorIterations);
     
    15431554            CbcHeuristicDivePseudoCost heuristicDP(*model);
    15441555            heuristicDP.setHeuristicName("DivePseudoCost");
    1545             heuristicDP.setWhen(diveOptions /*+ diveOptions2*/);
     1556            heuristicDP.setWhen(diveOptionsNotC /*+ diveOptions2*/);
    15461557            if (diveOptions2) {
    15471558              heuristicDP.setMaxIterations(majorIterations);
  • trunk/Cbc/src/CbcSymmetry.cpp

    r2051 r2092  
    2323#include "CbcBranchingObject.hpp"
    2424#include "CoinTime.hpp"
     25#define NAUTY_MAX_LEVEL 2000
     26#if NAUTY_MAX_LEVEL
     27extern int nauty_maxalllevel;
     28#endif
    2529/* Deliberately not threadsafe to save effort
    2630   Just for statistics
     
    2933 */
    3034static int nautyBranchCalls_ = 0;
     35static int lastNautyBranchCalls_ = 0;
    3136static int nautyBranchSucceeded_ = 0;
    3237static int nautyFixCalls_ = 0;
     38static int lastNautyFixCalls_ = 0;
    3339static int nautyFixSucceeded_ = 0;
    3440static double nautyTime_ = 0.0;
     
    96102  char general[200];
    97103  int returnCode=0;
     104  bool printSomething=true;
    98105  if (type) {
    99106    double branchSuccess=0.0;
     
    103110    if (nautyFixSucceeded_)
    104111      fixSuccess = nautyFixes_/nautyFixSucceeded_;
    105     sprintf(general,"Orbital branching tried %d times, succeeded %d times - average extra %7.3f, fixing %d times (%d, %7.3f) - %.2f seconds",
    106             nautyBranchCalls_,nautyBranchSucceeded_,branchSuccess,
    107             nautyFixCalls_,nautyFixSucceeded_,fixSuccess,nautyTime_);
     112    if (nautyBranchCalls_>lastNautyBranchCalls_||
     113        nautyFixCalls_>lastNautyFixCalls_) {
     114      sprintf(general,"Orbital branching tried %d times, succeeded %d times - average extra %7.3f, fixing %d times (%d, %7.3f)",
     115              nautyBranchCalls_,nautyBranchSucceeded_,branchSuccess,
     116              nautyFixCalls_,nautyFixSucceeded_,fixSuccess);
     117      lastNautyBranchCalls_=nautyBranchCalls_;
     118      lastNautyFixCalls_=nautyFixCalls_;
     119    } else {
     120      printSomething=false;
     121    }
    108122  } else {
    109123    returnCode = nauty_info_->getNumGenerators();
    110     if (returnCode) {
    111       sprintf (general,"Nauty: %d orbits, %d generators, group size: %g - dense size %d, sparse %d - going %s",
    112                nauty_info_->getNumOrbits(),
    113                nauty_info_ -> getNumGenerators () ,
    114                nauty_info_ -> getGroupSize (),
    115                whichOrbit_[0],whichOrbit_[1],nauty_info_->isSparse() ? "sparse" : "dense");
     124    if (!nauty_info_->errorStatus()) {
     125      if (returnCode && numberUsefulOrbits_) {
     126        sprintf (general,"Nauty: %d orbits (%d useful covering %d variables), %d generators, group size: %g - dense size %d, sparse %d - took %g seconds",
     127                 nauty_info_->getNumOrbits(),numberUsefulOrbits_,numberUsefulObjects_,
     128                 nauty_info_ -> getNumGenerators () ,
     129                 nauty_info_ -> getGroupSize (),
     130                 whichOrbit_[0],whichOrbit_[1],nautyTime_);
     131      } else {
     132        if ((model->moreSpecialOptions2()&(128|256))!=(128|256))
     133          sprintf(general,"Nauty did not find any useful orbits in time %g",nautyTime_);
     134        else
     135          sprintf(general,"Nauty did not find any useful orbits - but keeping Nauty on");
     136      }
    116137    } else {
    117       if ((model->moreSpecialOptions2()&(128|256))!=(128|256))
    118         sprintf(general,"Nauty did not find any useful orbits");
    119       else
    120         sprintf(general,"Nauty did not find any useful orbits - but keeping Nauty on");
    121     }
    122   }
    123   model->messageHandler()->message(CBC_GENERAL,
    124                                    model->messages())
    125     << general << CoinMessageEol ;
     138      // error
     139      sprintf(general,"Nauty failed with error code %d (%g seconds)",
     140              nauty_info_->errorStatus(),nautyTime_);
     141      model->setMoreSpecialOptions2(model->moreSpecialOptions2()&~(128|256));
     142    }
     143  }
     144  if (printSomething)
     145    model->messageHandler()->message(CBC_GENERAL,
     146                                     model->messages())
     147      << general << CoinMessageEol ;
    126148  return returnCode;
    127149}
     
    197219    whichOrbit_[i]=-1;
    198220  numberUsefulOrbits_=0;
     221  numberUsefulObjects_=0;
    199222
    200223  std::vector<std::vector<int> > *orbits = nauty_info_ -> getOrbits ();
     
    213236    if (nUseful>1) {
    214237      numberUsefulOrbits_++;
     238      numberUsefulObjects_ += nUseful;
    215239    } else if (jColumn>=0) {
    216240      assert (nUseful);
     
    292316}
    293317void CbcSymmetry::setupSymmetry (const OsiSolverInterface & solver) {
     318  double startCPU = CoinCpuTime ();
    294319  const double *objective = solver.getObjCoefficients() ;
    295320  const double *columnLower = solver.getColLower() ;
     
    353378  int * e = NULL;
    354379  bool sparse=false;
    355   double spaceDense = ((nc+WORDSIZE-1)*(nc+WORDSIZE-1))/WORDSIZE;
     380  double spaceDense = nc+WORDSIZE-1;
     381  spaceDense *= nc+WORDSIZE-1;
     382  spaceDense /= WORDSIZE;
    356383  int spaceSparse = 0;
    357384  {
     
    581608  nautyOtherBranches_ = 0.0;
    582609  Compute_Symmetry ();
     610  fillOrbits();
     611  //whichOrbit_[2]=numberUsefulOrbits_;
    583612  //Print_Orbits ();
    584613  // stats in array
    585   whichOrbit_[0]=spaceDense;
     614  if (spaceDense<COIN_INT_MAX)
     615    whichOrbit_[0]=spaceDense;
     616  else
     617    whichOrbit_[0]=COIN_INT_MAX;
    586618  whichOrbit_[1]=spaceSparse;
     619  double endCPU = CoinCpuTime ();
     620  nautyTime_ = endCPU-startCPU;
    587621}
    588622// Fixes variables using orbits (returns number fixed)
     
    654688    numberColumns_(0),
    655689    numberUsefulOrbits_(0),
     690    numberUsefulObjects_(0),
    656691    whichOrbit_(NULL)
    657692{
     
    663698  nauty_info_ = new CbcNauty(*rhs.nauty_info_);
    664699  numberUsefulOrbits_ = rhs.numberUsefulOrbits_;
     700  numberUsefulObjects_ = rhs.numberUsefulObjects_;
    665701  numberColumns_ = rhs.numberColumns_;
    666702  if (rhs.whichOrbit_)
     
    681717    numberColumns_ = rhs.numberColumns_;
    682718    numberUsefulOrbits_ = rhs.numberUsefulOrbits_;
     719    numberUsefulObjects_ = rhs.numberUsefulObjects_;
    683720    if (rhs.whichOrbit_)
    684721      whichOrbit_=CoinCopyOfArray(rhs.whichOrbit_,numberColumns_);
     
    9981035  //  if (autoComputed_) return;
    9991036
    1000   double startCPU = CoinCpuTime ();
     1037  //double startCPU = CoinCpuTime ();
    10011038
    10021039  options_->defaultptn = FALSE;
     
    10361073#endif
    10371074  } else {
     1075#if NAUTY_MAX_LEVEL
     1076    nauty_maxalllevel=NAUTY_MAX_LEVEL;
     1077#endif
    10381078#ifndef NTY_TRACES
    10391079    options_->dispatch = &dispatch_sparse;
     
    10481088  autoComputed_ = true;
    10491089
    1050   double endCPU = CoinCpuTime ();
    1051 
    1052   nautyTime_ += endCPU - startCPU;
     1090  //double endCPU = CoinCpuTime ();
     1091
     1092  //nautyTime_ += endCPU - startCPU;
    10531093  // Need to make sure all generators are written
    10541094  if (afp_) fflush(afp_);   
  • trunk/Cbc/src/CbcSymmetry.hpp

    r2049 r2092  
    140140  void Compute_Symmetry() const;
    141141  int statsOrbits(CbcModel * model, int type) const;
    142   double timeNauty () const;
     142  //double timeNauty () const;
    143143  void Print_Orbits() const;
    144144  void fillOrbits();
     
    147147  inline int * whichOrbit()
    148148  { return numberUsefulOrbits_ ? whichOrbit_ : NULL;}
     149  inline int numberUsefulOrbits() const
     150  { return numberUsefulOrbits_;}
    149151  inline int numberUsefulObjects() const
    150   { return numberUsefulOrbits_;}
     152  { return numberUsefulObjects_;}
    151153  int largestOrbit(const double * lower, const double * upper) const;
    152154  void ChangeBounds (const double * lower, const double * upper,
     
    165167  int numberColumns_;
    166168  int numberUsefulOrbits_;
     169  int numberUsefulObjects_;
    167170  int * whichOrbit_;
    168171};
     
    215218  inline bool isSparse() const
    216219  { return GSparse_ != NULL;}
    217 
     220  inline int errorStatus() const
     221  { return stats_->errstatus;}
    218222  /**
    219223   * Methods to classify orbits.  Not horribly efficient, but gets the job done
Note: See TracChangeset for help on using the changeset viewer.