Ignore:
Timestamp:
Oct 30, 2009 8:45:20 AM (12 years ago)
Author:
forrest
Message:

modifications to heuristics and use of cuts

File:
1 edited

Legend:

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

    r1255 r1261  
    1 
    21/* $Id$ */
    32// Copyright (C) 2002, International Business Machines
     
    76#  pragma warning(disable:4786)
    87#endif
    9 #define MODEL2 0
    10 #define MODEL4 0
    11 #define MODEL13 1
    128
    139#include "CbcConfig.h"
     
    521517      if (iPriority>=0) {
    522518        char general[200];
    523         if (cost==-COIN_DBL_MAX)
     519        if (cost==-COIN_DBL_MAX) {
    524520          sprintf(general,"%d integer variables out of %d objects (%d integer) have costs - high priority",
    525521                  numberIntegerObj,numberObjects_,numberInteger);
    526         else
     522        } else if (cost==COIN_DBL_MAX) {
     523          sprintf(general,"No integer variables out of %d objects (%d integer) have costs",
     524                  numberObjects_,numberInteger);
     525          branchOnSatisfied=false;
     526        } else {
    527527          sprintf(general,"%d integer variables out of %d objects (%d integer) have cost of %g - high priority",
    528528                  numberIntegerObj,numberObjects_,numberInteger,cost);
     529        }
    529530        messageHandler()->message(CBC_GENERAL,
    530531                                  messages())
     
    579580        }
    580581#endif
     582        CoinDrand48(true,1234567);
    581583        for (int i=0;i<numberColumns;i++) {
    582584          double lowerValue=lower[i];
     
    11431145  numberStrongIterations_ = 0;
    11441146  currentNode_ = NULL;
    1145   CoinThreadRandom randomGenerator(1234567);
    11461147  // See if should do cuts old way
    11471148  if (parallelMode()<0) {
     
    35963597      if (redoTree)
    35973598        tree_->setComparison(*nodeCompare_) ;
    3598 #if MODEL2
    3599       if (searchStrategy_==2) {
    3600         // may be time to tweak numberBeforeTrust
    3601         if (numberStrongIterations_*5<numberIterations_&&numberNodes_<10000) {
    3602           int numberDone = strongInfo_[0]-strongInfo_[3];
    3603           int numberFixed = strongInfo_[1]-strongInfo_[4];
    3604           int numberInfeasible = strongInfo_[2]-strongInfo_[5];
    3605           int numberNodes=numberNodes_-strongInfo_[6];
    3606           for (int i=0;i<7;i++)
    3607             printf("%d ",strongInfo_[i]);
    3608           printf("its %d strong %d\n",
    3609                  numberIterations_,numberStrongIterations_);
    3610           printf("done %d fixed %d inf %d in %d nodes\n",
    3611                  numberDone,numberFixed,numberInfeasible,numberNodes);
    3612           if (numberInfeasible*500+numberFixed*10>numberDone) {
    3613             synchronizeNumberBeforeTrust(1);
    3614             strongInfo_[3]=strongInfo_[0];
    3615             strongInfo_[4]=strongInfo_[1];
    3616             strongInfo_[5]=strongInfo_[2];
    3617             strongInfo_[6]=numberNodes_;
    3618           }
    3619         }
    3620       }
    3621 #endif
    36223599      if (parallelMode()>0)
    36233600        unlockThread();
     
    36513628          printf("model cutoff in status %g, best %g, increment %g\n",
    36523629                 getCutoff(),bestObjective_,getCutoffIncrement());
    3653         assert (getCutoff()<bestObjective_-getCutoffIncrement()+1.0e-6);
     3630        assert (getCutoff()<bestObjective_-getCutoffIncrement()+
     3631                1.0e-6+1.0e-10*fabs(bestObjective_));
    36543632      }
    36553633#endif
     
    66406618
    66416619{
    6642 #if MODEL4
     6620#if 0
    66436621  if (node&&numberTries>1) {
    66446622    if (currentDepth_<5)
     
    66486626  }
    66496627#endif
    6650 #if MODEL13
    66516628#define CUT_HISTORY 7
    66526629  double cut_obj[CUT_HISTORY];
    66536630  for (int j=0;j<CUT_HISTORY;j++)
    66546631         cut_obj[j]=-COIN_DBL_MAX;
    6655 #endif
    66566632# ifdef COIN_HAS_CLP
    66576633  OsiClpSolverInterface * clpSolver
     
    67456721#endif
    67466722  double lastObjective = solver_->getObjValue()*solver_->getObjSense();
    6747 #if MODEL13
    67486723  cut_obj[CUT_HISTORY-1]=lastObjective;
    6749 #endif
    67506724  //double firstObjective = lastObjective+1.0e-8+1.0e-12*fabs(lastObjective);
    67516725  if (node&&node->nodeInfo()&&!node->nodeInfo()->numberBranchesLeft())
     
    69396913  bool allowZeroIterations = false;
    69406914  int maximumBadPasses=0;
    6941 #if MODEL13==0
    6942   if (numberTries<0)
    6943   { numberTries = -numberTries ;
    6944     if (numberTries>100)
    6945       allowZeroIterations=true;
    6946     minimumDrop = -1.0 ; }
    6947 #else
    69486915  if (numberTries<0) {
    69496916    numberTries = -numberTries ;
     
    69536920      minimumDrop=-1.0;
    69546921    }
    6955     numberTries=CoinMax(numberTries,100);
     6922    //numberTries=CoinMax(numberTries,100);
    69566923    allowZeroIterations=true;
    69576924  }
    6958 #endif
    69596925/*
    69606926  Is it time to scan the cuts in order to remove redundant cuts? If so, set
     
    69766942  // We may need to keep going on
    69776943  bool keepGoing=false;
     6944  // Say we have not tried one last time
     6945  int numberLastAttempts=0;
     6946  /* Get experimental option as to when to stop adding cuts
     6947     0 - old style
     6948     1 - new style
     6949     2 - new style plus don't break if zero cuts first time
     6950     3 - as 2 but last drop has to be >0.1*min to say OK
     6951  */
     6952  int experimentBreak = (moreSpecialOptions_>>11)&3;
     6953  // Whether to increase minimum drop
     6954  bool increaseDrop = (moreSpecialOptions_&8192)!=0;
    69786955/*
    69796956  Begin cut generation loop. Cuts generated during each iteration are
     
    71567133        }
    71577134        if (generate) {
    7158 #if MODEL13
    71597135          if (!node&&cut_obj[CUT_HISTORY-1]!=-COIN_DBL_MAX&&
    71607136              fabs(cut_obj[CUT_HISTORY-1]-cut_obj[CUT_HISTORY-2])<1.0e-7)
    71617137            generator_[i]->setIneffectualCuts(true);
    7162 #endif
    71637138          bool mustResolve =
    71647139            generator_[i]->generateCuts(theseCuts,fullScan,solver_,node) ;
    7165 #if MODEL13
    71667140          generator_[i]->setIneffectualCuts(false);
    7167 #endif
    71687141          numberRowCutsAfter = theseCuts.sizeRowCuts() ;
    71697142          if (fullScan&&generator_[i]->howOften()==1000000+SCANCUTS_PROBING) {
     
    79497922  No cuts. Cut short the cut generation (numberTries) loop.
    79507923*/
    7951     else
     7924    else if (numberLastAttempts>2||experimentBreak<2)
    79527925      { numberTries = 0 ;}
    79537926/*
     
    79997972        lastNumberCuts = numberNewCuts_ ;
    80007973        double thisObj = direction*solver_->getObjValue();
    8001 #if MODEL13
    80027974        bool badObj = (allowZeroIterations) ? thisObj < cut_obj[0]+minimumDrop
    80037975          : thisObj < cut_obj[CUT_HISTORY-1]+minimumDrop;
     7976#if 0 // probably not a good idea
     7977        if (!badObj)
     7978          numberLastAttempts=CoinMax(0,numberLastAttempts-1);
     7979#endif
    80047980        // Compute maximum number of bad passes
    80057981        if (minimumDrop>0.0) {
     7982          if (increaseDrop) {
     7983            // slowly increase minimumDrop
     7984            if (currentPassNumber_==13)
     7985              minimumDrop = CoinMax(1.5*minimumDrop,1.0e-5*fabs(thisObj));
     7986            else if (currentPassNumber_>20&&(currentPassNumber_%5)==0)
     7987              minimumDrop = CoinMax(1.1*minimumDrop,1.0e-5*fabs(thisObj));
     7988            else if (currentPassNumber_>50)
     7989              minimumDrop = CoinMax(1.1*minimumDrop,1.0e-5*fabs(thisObj));
     7990          }
    80067991          int nBadPasses=0;
    8007           double test = 0.01*minimumDrop;
    8008           double goodDrop=COIN_DBL_MAX;
    8009           for (int j=CUT_HISTORY-1;j>=0;j--) {
    8010             if (thisObj-cut_obj[j]<test) {
    8011               nBadPasses++;
    8012             } else {
    8013               goodDrop=(thisObj-cut_obj[j])/static_cast<double>(nBadPasses+1);
    8014               break;
     7992          if (!experimentBreak) {
     7993            double test = 0.01*minimumDrop;
     7994            double goodDrop=COIN_DBL_MAX;
     7995            for (int j=CUT_HISTORY-1;j>=0;j--) {
     7996              if (thisObj-cut_obj[j]<test) {
     7997                nBadPasses++;
     7998              } else {
     7999                goodDrop=(thisObj-cut_obj[j])/static_cast<double>(nBadPasses+1);
     8000                break;
     8001              }
    80158002            }
     8003            maximumBadPasses=CoinMax(maximumBadPasses,nBadPasses);
     8004            if (nBadPasses<maximumBadPasses&&
     8005                goodDrop>minimumDrop)
     8006              badObj=false; // carry on
     8007          } else {
     8008            //if (currentPassNumber_==13||currentPassNumber_>50)
     8009            //minimumDrop = CoinMax(1.5*minimumDrop,1.0e-5*fabs(thisObj));
     8010            double test = 0.1*minimumDrop;
     8011            double goodDrop=(thisObj-cut_obj[0])/static_cast<double>(CUT_HISTORY);
     8012            double objValue = thisObj;
     8013            for (int j=CUT_HISTORY-1;j>=0;j--) {
     8014              if (objValue-cut_obj[j]<test) {
     8015                nBadPasses++;
     8016                objValue = cut_obj[j];
     8017              } else {
     8018                break;
     8019              }
     8020            }
     8021#ifdef CLP_INVESTIGATE2
     8022            if (!parentModel_&&!numberNodes_)
     8023              printf("badObj %s nBad %d maxBad %d goodDrop %g minDrop %g thisDrop %g obj %g\n",
     8024                     badObj ? "true" : "false",
     8025                     nBadPasses,maximumBadPasses,goodDrop,minimumDrop,
     8026                     thisObj-cut_obj[CUT_HISTORY-1],
     8027                     solver_->getObjValue());
     8028#endif
     8029            maximumBadPasses=CoinMax(maximumBadPasses,nBadPasses);
     8030            if (nBadPasses<2||goodDrop>2.0*minimumDrop) {
     8031              if (experimentBreak<=2||goodDrop>0.1*minimumDrop)
     8032                badObj=false; // carry on
     8033            }
     8034            if (experimentBreak>1&&goodDrop<minimumDrop)
     8035              numberLastAttempts++;
    80168036          }
    8017           maximumBadPasses=CoinMax(maximumBadPasses,nBadPasses);
    8018           if (nBadPasses<maximumBadPasses&&
    8019               goodDrop>minimumDrop)
    8020             badObj=false; // carry on
    80218037        }
    80228038        if (numberTries==1&&currentDepth_&&currentPassNumber_<10) {
     
    80318047          cut_obj[j] = cut_obj[j+1];
    80328048        cut_obj[CUT_HISTORY-1]=thisObj;
    8033 #else
    8034         bool badObj = thisObj < lastObjective+minimumDrop;
    8035 #endif
    80368049        bool allowEarlyTermination = currentPassNumber_ >= 10;
    80378050        if (currentDepth_>10||(currentDepth_>5&&numberColumns>200))
     
    80438056          { numberTries = 0 ; }
    80448057        if (numberRowCuts+numberColumnCuts == 0 ||
    8045             (cutIterations == 0 && !allowZeroIterations) )
    8046           { break ; }
     8058            (cutIterations == 0 && !allowZeroIterations) ) {
     8059          // maybe give it one more try
     8060          if(numberLastAttempts>2||currentDepth_||experimentBreak<2)
     8061            break ;
     8062          else
     8063            numberLastAttempts++;
     8064        }
    80478065        if (numberTries > 0) {
    80488066          reducedCostFix() ;
     
    84878505          // Allow on smaller number if <-1
    84888506          if (generator_[i]->switchOffIfLessThan()<0) {
    8489             double multiplier = -generator_[i]->switchOffIfLessThan()+1.0;
    8490             thisCuts *= multiplier;
     8507            double multiplier[]={2.0,5.0};
     8508            int iSwitch=-generator_[i]->switchOffIfLessThan()-1;
     8509            assert (iSwitch>=0&&iSwitch<2);
     8510            thisCuts *= multiplier[iSwitch];
    84918511          }
    84928512          if (!thisCuts||howOften == -99) {
Note: See TracChangeset for help on using the changeset viewer.