Changeset 441 for branches/devel/Cbc/src


Ignore:
Timestamp:
Oct 9, 2006 4:19:31 PM (13 years ago)
Author:
forrest
Message:

for local tree search and feasibility pump

Location:
branches/devel/Cbc/src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • branches/devel/Cbc/src/CbcBranchActual.cpp

    r439 r441  
    862862CbcSimpleInteger::infeasibility(int & preferredWay) const
    863863{
    864   abort();
    865   return 0.0;
     864  OsiBranchingInformation info(model_->solver());
     865  return infeasibility(model_->solver(),&info,preferredWay);
    866866}
    867867
  • branches/devel/Cbc/src/CbcHeuristicFPump.cpp

    r439 r441  
    2929   maximumPasses_(100),
    3030   maximumRetries_(1),
     31   accumulate_(0),
    3132   roundExpensive_(false)
    3233{
     
    4647   maximumPasses_(100),
    4748   maximumRetries_(1),
     49   accumulate_(0),
    4850   roundExpensive_(roundExpensive)
    4951{
     
    7779  else
    7880    fprintf(fp,"4  heuristicFPump.setMaximumRetries(%d);\n",maximumRetries_);
     81  if (accumulate_!=other.accumulate_)
     82    fprintf(fp,"3  heuristicFPump.setAccumulate(%d);\n",accumulate_);
     83  else
     84    fprintf(fp,"4  heuristicFPump.setAccumulate(%d);\n",accumulate_);
    7985  if (maximumTime_!=other.maximumTime_)
    8086    fprintf(fp,"3  heuristicFPump.setMaximumTime(%g);\n",maximumTime_);
     
    108114  maximumPasses_(rhs.maximumPasses_),
    109115  maximumRetries_(rhs.maximumRetries_),
     116  accumulate_(rhs.accumulate_),
    110117  roundExpensive_(rhs.roundExpensive_)
    111118{
     
    150157  char * usedColumn = NULL;
    151158  double * lastSolution=NULL;
    152   bool fixContinuous=false;
     159  int fixContinuous=0;
    153160  bool fixInternal=false;
    154   if (when_>=11&&when_<=13) {
    155     fixInternal = when_ >11;
    156     fixContinuous = when_==13;
     161  if (when_>=11&&when_<=15) {
     162    fixInternal = when_ >11&&when_<15;
     163    if (when_<13)
     164      fixContinuous = 0;
     165    else if (when_!=14)
     166      fixContinuous=1;
     167    else
     168      fixContinuous=2;
    157169    when_=1;
    158170    usedColumn = new char [numberColumns];
     
    314326          if (returnCode) {
    315327            memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
     328            if ((accumulate_&1)!=0)
     329              model_->incrementUsed(betterSolution); // for local search
    316330            solutionValue=newSolutionValue;
    317331            solutionFound=true;
     
    438452            if (newSolutionValue<solutionValue) {
    439453              memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
     454              if ((accumulate_&1)!=0)
     455                model_->incrementUsed(betterSolution); // for local search
    440456              solutionValue=newSolutionValue;
    441457              solutionFound=true;
     
    468484      int nFixI=0;
    469485      int nFixC=0;
     486      int nFixC2=0;
    470487      for (i=0;i<numberIntegers;i++) {
    471488        int iColumn=integerVariable[i];
     
    507524              newSolver->setColLower(iColumn,colUpper[iColumn]);
    508525              nFixC++;
     526            } else if (fixContinuous==2) {
     527              newSolver->setColLower(iColumn,value);
     528              newSolver->setColUpper(iColumn,value);
     529              nFixC++;
     530              nFixC2++;
    509531            }
    510532          }
     
    517539        break;
    518540      }
    519       printf("%d integers at bound fixed (of which %d were internal) and %d continuous\n",
    520              nFix,nFixI,nFixC);
     541      printf("%d integers at bound fixed and %d continuous",
     542             nFix,nFixC);
     543      if (nFixC2+nFixI==0)
     544        printf("\n");
     545      else
     546        printf("of which %d were internal integer and %d internal continuous\n",
     547             nFixI,nFixC2);
    521548      double saveValue = newSolutionValue;
    522549      returnCode = smallBranchAndBound(newSolver,200,newSolution,newSolutionValue,
     
    525552        printf("old sol of %g new of %g\n",saveValue,newSolutionValue);
    526553        memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
     554        if (fixContinuous) {
     555          // may be able to do even better
     556          const double * lower = model_->solver()->getColLower();
     557          const double * upper = model_->solver()->getColUpper();
     558          for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     559            if (newSolver->isInteger(iColumn)) {
     560              double value=floor(newSolution[iColumn]+0.5);
     561              newSolver->setColLower(iColumn,value);
     562              newSolver->setColUpper(iColumn,value);
     563            } else {
     564              newSolver->setColLower(iColumn,lower[iColumn]);
     565              newSolver->setColUpper(iColumn,upper[iColumn]);
     566            }
     567          }
     568          newSolver->initialSolve();
     569          if (newSolver->isProvenOptimal()) {
     570            double value = newSolver->getObjValue()*newSolver->getObjSense();
     571            if (value<newSolutionValue) {
     572              printf("freeing continuous gives a solution of %g\n", value);
     573              newSolutionValue=value;
     574              memcpy(betterSolution,newSolver->getColSolution(),numberColumns*sizeof(double));
     575            }
     576          } else {
     577            newSolver->writeMps("bad3.mps");
     578          }
     579        }
     580        if ((accumulate_&1)!=0)
     581          model_->incrementUsed(betterSolution); // for local search
    527582        solutionValue=newSolutionValue;
    528583        solutionFound=true;
     
    532587    if (solutionFound) finalReturnCode=1;
    533588    cutoff = CoinMin(cutoff,solutionValue);
    534     if (numberTries>=CoinAbs(maximumRetries_)||!solutionFound) {
     589    if (numberTries>=maximumRetries_||!solutionFound) {
    535590      break;
    536591    } else if (absoluteIncrement_>0.0||relativeIncrement_>0.0) {
     
    539594      cutoff -= CoinMax(CoinMax(gap,absoluteIncrement_),model_->getCutoffIncrement());
    540595      printf("round again with cutoff of %g\n",cutoff);
    541       if (maximumRetries_<0)
     596      if (accumulate_<2)
    542597        memset(usedColumn,0,numberColumns);
    543598      totalNumberPasses += numberPasses;
  • branches/devel/Cbc/src/CbcHeuristicFPump.hpp

    r439 r441  
    4343      It may make sense for user to call this outside Branch and Cut to
    4444      get solution.  Or normally is just at root node.
     45
     46      * new meanings for when_ - on first try then set back to 1
     47        11 - at end fix all integers at same bound throughout
     48        12 - also fix all integers staying at same internal integral value throughout
     49        13 - also fix all continuous variables staying at same bound throughout
     50        14 - also fix all continuous variables staying at same internal value throughout
     51        15 - as 13 but no internal integers
    4552  */
    4653  virtual int solution(double & objectiveValue,
     
    8289  inline int maximumRetries() const
    8390  { return maximumRetries_;};
     91  /**  Set use of multiple solutions and solves
     92       0 - do not reuse solves, do not accumulate integer solutions for local search
     93       1 - do not reuse solves, accumulate integer solutions for local search
     94       2 - reuse solves, do not accumulate integer solutions for local search
     95       3 - reuse solves, accumulate integer solutions for local search
     96  */
     97  inline void setAccumulate(int value)
     98  { accumulate_=value;};
     99  /// Get accumulation option
     100  inline int accumulate() const
     101  { return accumulate_;};
    84102
    85103protected:
     
    105123  */
    106124  int maximumRetries_;
     125  /**  Set use of multiple solutions and solves
     126       0 - do not reuse solves, do not accumulate integer solutions for local search
     127       1 - do not reuse solves, accumulate integer solutions for local search
     128       2 - reuse solves, do not accumulate integer solutions for local search
     129       3 - reuse solves, accumulate integer solutions for local search
     130  */
     131  int accumulate_;
    107132  /// If true round to expensive
    108133  bool roundExpensive_;
  • branches/devel/Cbc/src/CbcModel.cpp

    r439 r441  
    85848584  if (nodeCompare_)
    85858585    nodeCompare_->generateCpp(fp);
     8586  tree_->generateCpp(fp);
    85868587  CbcModel defaultModel;
    85878588  CbcModel * other = &defaultModel;
     
    86238624  fprintf(fp,"%d  cbcModel->setPrintFrequency(%d);\n",iValue1==iValue2 ? 4 : 3,iValue1);
    86248625  fprintf(fp,"%d  cbcModel->setPrintFrequency(save_printFrequency);\n",iValue1==iValue2 ? 7 : 6);
     8626  iValue1 = this->getPrintingMode();
     8627  iValue2 = other->getPrintingMode();
     8628  fprintf(fp,"%d  int save_printingMode = cbcModel->getPrintingMode();\n",iValue1==iValue2 ? 2 : 1);
     8629  fprintf(fp,"%d  cbcModel->setPrintingMode(%d);\n",iValue1==iValue2 ? 4 : 3,iValue1);
     8630  fprintf(fp,"%d  cbcModel->setPrintingMode(save_printingMode);\n",iValue1==iValue2 ? 7 : 6);
    86258631  iValue1 = this->searchStrategy();
    86268632  iValue2 = other->searchStrategy();
  • branches/devel/Cbc/src/CbcTree.hpp

    r419 r441  
    3030  /// Clone
    3131  virtual CbcTree * clone() const;
     32  /// Create C++ lines to get to current state
     33  virtual void generateCpp( FILE * fp) {};
    3234
    3335/*! \name Heap access and maintenance methods */
  • branches/devel/Cbc/src/CbcTreeLocal.cpp

    r419 r441  
    837837  global->eraseRowCut(i);
    838838}
    839 
    840 
    841 
     839// Create C++ lines to get to current state
     840void
     841CbcTreeLocal::generateCpp( FILE * fp)
     842{
     843  CbcTreeLocal other;
     844  fprintf(fp,"0#include \"CbcTreeLocal.hpp\"\n");
     845  fprintf(fp,"5  CbcTreeLocal localTree(cbcModel,NULL);\n");
     846  if (range_!=other.range_)
     847    fprintf(fp,"5  localTree.setRange(%d);\n",range_);
     848  if (typeCuts_!=other.typeCuts_)
     849    fprintf(fp,"5  localTree.setTypeCuts(%d);\n",typeCuts_);
     850  if (maxDiversification_!=other.maxDiversification_)
     851    fprintf(fp,"5  localTree.setMaxDiversification(%d);\n",maxDiversification_);
     852  if (timeLimit_!=other.timeLimit_)
     853    fprintf(fp,"5  localTree.setTimeLimit(%d);\n",timeLimit_);
     854  if (nodeLimit_!=other.nodeLimit_)
     855    fprintf(fp,"5  localTree.setNodeLimit(%d);\n",nodeLimit_);
     856  if (refine_!=other.refine_)
     857    fprintf(fp,"5  localTree.setRefine(%s);\n",refine_ ? "true" : "false");
     858  fprintf(fp,"5  cbcModel->passInTreeHandler(localTree);\n");
     859}
     860
     861
     862
  • branches/devel/Cbc/src/CbcTreeLocal.hpp

    r419 r441  
    6868  /// Clone
    6969  virtual CbcTree * clone() const;
     70  /// Create C++ lines to get to current state
     71  virtual void generateCpp( FILE * fp) ;
    7072
    7173/*! \name Heap access and maintenance methods */
     
    99101  /// Pass in solution (so can be used after heuristic)
    100102  void passInSolution(const double * solution, double solutionValue);
     103  // range i.e. k
     104  inline int range() const
     105  { return range_;};
     106  // setrange i.e. k
     107  inline void setRange(int value)
     108  { range_ = value;};
     109  // Type of cuts - 0=just 0-1, 1=all
     110  inline int typeCuts() const
     111  { return typeCuts_;};
     112  // Type of cuts - 0=just 0-1, 1=all
     113  inline void setTypeCuts(int value)
     114  { typeCuts_ = value;};
     115  // maximum number of diversifications
     116  inline int maxDiversification() const
     117  { return maxDiversification_;};
     118  // maximum number of diversifications
     119  inline void setMaxDiversification(int value)
     120  { maxDiversification_ = value;};
     121  // time limit per subtree
     122  inline int timeLimit() const
     123  { return timeLimit_;};
     124  // time limit per subtree
     125  inline void setTimeLimit(int value)
     126  { timeLimit_ = value;};
     127  // node limit for subtree
     128  inline int nodeLimit() const
     129  { return nodeLimit_;};
     130  // node limit for subtree
     131  inline void setNodeLimit(int value)
     132  { nodeLimit_ = value;};
     133  // Whether to do refinement step
     134  inline bool refine() const
     135  { return refine_;};
     136  // Whether to do refinement step
     137  inline void setRefine(bool yesNo)
     138    { refine_ = yesNo;};
    101139
    102140//@}
  • branches/devel/Cbc/src/CoinSolve.cpp

    r439 r441  
    9191static bool maskMatches(const int * starts, char ** masks,
    9292                        std::string & check);
    93 static void generateCode(const char * fileName,int type,int preProcess);
     93static void generateCode(CbcModel * model, const char * fileName,int type,int preProcess);
    9494#ifdef NDEBUG
    9595#undef NDEBUG
     
    20642064                heuristic4.setMaximumPasses(parameters[whichParam(FPUMPITS,numberParameters,parameters)].intValue());
    20652065                int pumpTune=parameters[whichParam(FPUMPTUNE,numberParameters,parameters)].intValue();
    2066                 if (pumpTune>10) {
     2066                if (pumpTune>0) {
    20672067                  /*
    2068                     >=1000 use index+2 as number of large loops, if >4 decrement by 5 and clean used array
     2068                    >=1000000 use as accumulate switch
     2069                    >=1000 use index+2 as number of large loops
    20692070                    >=100 use 0.05 objvalue as increment
    20702071                    >=10 use +0.1 objvalue for cutoff (add)
    20712072                    1 == fix ints at bounds, 2 fix all integral ints, 3 and continuous at bounds
     2073                    4 and static continuous, 5 as 3 but no internal integers
    20722074                  */
    2073                   if (pumpTune) {
    2074                     double value = babModel->solver()->getObjSense()*babModel->solver()->getObjValue();
    2075                     int w = pumpTune/10;
    2076                     int c = w % 10;
    2077                     w /= 10;
    2078                     int i = w % 10;
    2079                     w /= 10;
    2080                     int r = w%10;
    2081                     // fake cutoff
    2082                     if (c) {
    2083                       double cutoff;
    2084                       babModel->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
    2085                       cutoff = CoinMin(cutoff,value + 0.1*fabs(value)*c);
    2086                       heuristic4.setFakeCutoff(cutoff);
    2087                     }
    2088                     if (i||r) {
    2089                       // also set increment
    2090                       heuristic4.setAbsoluteIncrement((0.01*i+0.005)*(fabs(value)+1.0e-12));
    2091                       if (r>4) {
    2092                         r -=5;
    2093                         heuristic4.setMaximumRetries(-r-2);
    2094                       } else {
    2095                         heuristic4.setMaximumRetries(r+2);
    2096                       }
    2097                     }
    2098                     pumpTune = pumpTune%100;
    2099                     heuristic4.setWhen(pumpTune+10);
     2075                  double value = babModel->solver()->getObjSense()*babModel->solver()->getObjValue();
     2076                  int w = pumpTune/10;
     2077                  int c = w % 10;
     2078                  w /= 10;
     2079                  int i = w % 10;
     2080                  w /= 10;
     2081                  int r = w;
     2082                  int accumulate = r/1000;
     2083                  r -= 1000*accumulate;
     2084                  // fake cutoff
     2085                  printf("Setting ");
     2086                  if (c) {
     2087                    double cutoff;
     2088                    babModel->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
     2089                    cutoff = CoinMin(cutoff,value + 0.1*fabs(value)*c);
     2090                    heuristic4.setFakeCutoff(cutoff);
     2091                    printf("fake cutoff of %g ",cutoff);
    21002092                  }
     2093                  if (i||r) {
     2094                    // also set increment
     2095                    heuristic4.setAbsoluteIncrement((0.01*i+0.005)*(fabs(value)+1.0e-12));
     2096                    heuristic4.setAccumulate(accumulate);
     2097                    heuristic4.setMaximumRetries(r+2);
     2098                    if (i)
     2099                      printf("increment of %g ",heuristic4.absoluteIncrement());
     2100                    if (accumulate)
     2101                      printf("accumulate of %d ",accumulate);
     2102                    printf("%d retries ",r+2);
     2103                  }
     2104                  pumpTune = pumpTune%100;
     2105                  printf("and setting when to %d\n",pumpTune+10);
     2106                  heuristic4.setWhen(pumpTune+10);
    21012107                }
    21022108                babModel->addHeuristic(&heuristic4);
     
    22152221                  iLevel = -iLevel;
    22162222                }
    2217                 babModel->messageHandler()->setLogLevel(parameters[log].intValue());
     2223                babModel->messageHandler()->setLogLevel(iLevel);
    22182224                if (babModel->getNumCols()>2000||babModel->getNumRows()>1500||
    22192225                    babModel->messageHandler()->logLevel()>1)
     
    25592565                    fclose(fp);
    25602566                    // now call generate code
    2561                     generateCode("user_driver.cpp",cppValue,prepro);
     2567                    generateCode(babModel,"user_driver.cpp",cppValue,prepro);
    25622568                  } else {
    25632569                    std::cout<<"Unable to open file user_driver.cpp"<<std::endl;
     
    44964502  *put='\0';
    44974503}
    4498 static void generateCode(const char * fileName,int type,int preProcess)
     4504static void generateCode(CbcModel * model, const char * fileName,int type,int preProcess)
    44994505{
    45004506  // options on code generation
     
    45214527  if (preProcess>0)
    45224528    strcpy(line[numberLines++],"0#include \"CglProbing.hpp\""); // possibly redundant
    4523   while (fgets(line[numberLines],MAXONELINE,fp)) {
    4524     assert (numberLines<MAXLINES);
    4525     clean(line[numberLines]);
    4526     numberLines++;
    4527   }
    4528   fclose(fp);
    4529   strcpy(line[numberLines++],"0\nint main (int argc, const char *argv[])\n{");
    4530   strcpy(line[numberLines++],"0  OsiClpSolverInterface solver1;");
    4531   strcpy(line[numberLines++],"0  int status=1;");
    4532   strcpy(line[numberLines++],"0  if (argc<2)");
    4533   strcpy(line[numberLines++],"0    std::cout<<\"Please give file name\"<<std::endl;");
    4534   strcpy(line[numberLines++],"0  else");
    4535   strcpy(line[numberLines++],"0    status=solver1.readMps(argv[1],\"\");");
    4536   strcpy(line[numberLines++],"0  if (status) {");
    4537   strcpy(line[numberLines++],"0    std::cout<<\"Bad readMps \"<<argv[1]<<std::endl;");
    4538   strcpy(line[numberLines++],"0    exit(1);");
    4539   strcpy(line[numberLines++],"0  }\n");
    4540   strcpy(line[numberLines++],"0  double time1 = CoinCpuTime();");
    4541   strcpy(line[numberLines++],"0  CbcModel model(solver1);");
    4542   strcpy(line[numberLines++],"0  // Now do requested saves and modifications");
    4543   strcpy(line[numberLines++],"0  CbcModel * cbcModel = & model;");
    4544   strcpy(line[numberLines++],"0  OsiSolverInterface * osiModel = model.solver();");
    4545   strcpy(line[numberLines++],"0  OsiClpSolverInterface * osiclpModel = dynamic_cast< OsiClpSolverInterface*> (osiModel);");
    4546   strcpy(line[numberLines++],"0  ClpSimplex * clpModel = osiclpModel->getModelPtr();");
    4547   // add in comments about messages
    4548   strcpy(line[numberLines++],"3  // You can save some time by switching off message building");
    4549   strcpy(line[numberLines++],"3  // clpModel->messagesPointer()->setDetailMessages(100,10000,(int *) NULL);");
     4529  // To allow generated 5's to be just before branchAndBound - do rest here
    45504530  strcpy(line[numberLines++],"5  cbcModel->initialSolve();");
    45514531  strcpy(line[numberLines++],"5  if (clpModel->tightenPrimalBounds()!=0) {");
     
    46134593    strcpy(line[numberLines++],"5  cbcModel->initialSolve();");
    46144594  }
     4595  while (fgets(line[numberLines],MAXONELINE,fp)) {
     4596    assert (numberLines<MAXLINES);
     4597    clean(line[numberLines]);
     4598    numberLines++;
     4599  }
     4600  fclose(fp);
     4601  strcpy(line[numberLines++],"0\nint main (int argc, const char *argv[])\n{");
     4602  strcpy(line[numberLines++],"0  OsiClpSolverInterface solver1;");
     4603  strcpy(line[numberLines++],"0  int status=1;");
     4604  strcpy(line[numberLines++],"0  if (argc<2)");
     4605  strcpy(line[numberLines++],"0    std::cout<<\"Please give file name\"<<std::endl;");
     4606  strcpy(line[numberLines++],"0  else");
     4607  strcpy(line[numberLines++],"0    status=solver1.readMps(argv[1],\"\");");
     4608  strcpy(line[numberLines++],"0  if (status) {");
     4609  strcpy(line[numberLines++],"0    std::cout<<\"Bad readMps \"<<argv[1]<<std::endl;");
     4610  strcpy(line[numberLines++],"0    exit(1);");
     4611  strcpy(line[numberLines++],"0  }\n");
     4612  strcpy(line[numberLines++],"0  double time1 = CoinCpuTime();");
     4613  strcpy(line[numberLines++],"0  CbcModel model(solver1);");
     4614  strcpy(line[numberLines++],"0  // Now do requested saves and modifications");
     4615  strcpy(line[numberLines++],"0  CbcModel * cbcModel = & model;");
     4616  strcpy(line[numberLines++],"0  OsiSolverInterface * osiModel = model.solver();");
     4617  strcpy(line[numberLines++],"0  OsiClpSolverInterface * osiclpModel = dynamic_cast< OsiClpSolverInterface*> (osiModel);");
     4618  strcpy(line[numberLines++],"0  ClpSimplex * clpModel = osiclpModel->getModelPtr();");
     4619  // add in comments about messages
     4620  strcpy(line[numberLines++],"3  // You can save some time by switching off message building");
     4621  strcpy(line[numberLines++],"3  // clpModel->messagesPointer()->setDetailMessages(100,10000,(int *) NULL);");
    46154622  // add in actual solve
    46164623  strcpy(line[numberLines++],"5  cbcModel->branchAndBound();");
Note: See TracChangeset for help on using the changeset viewer.