Changeset 954


Ignore:
Timestamp:
May 28, 2008 7:05:48 AM (11 years ago)
Author:
forrest
Message:

changes to try and improve code

Location:
trunk/Cbc/src
Files:
10 edited

Legend:

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

    r940 r954  
    657657          model.setMaximumCutPassesAtRoot(CoinMin(20,model_->getMaximumCutPassesAtRoot()));
    658658        } else {
     659          model_->messageHandler()->message(CBC_RESTART,model_->messages())
     660            <<solver2->getNumRows()<<solver2->getNumCols()
     661            <<CoinMessageEol;
    659662          // going for full search and copy across more stuff
    660663          model.gutsOfCopy(*model_,2);
     
    792795          model.branchAndBound();
    793796          if (numberNodes<0) {
     797            model_->incrementIterationCount(model.getIterationCount());
     798            model_->incrementNodeCount(model.getNodeCount());
    794799            for (int iGenerator=0;iGenerator<model.numberCutGenerators();iGenerator++) {
    795800              CbcCutGenerator * generator = model.cutGenerator(iGenerator);
  • trunk/Cbc/src/CbcHeuristicFPump.cpp

    r939 r954  
    599599          }
    600600        } else {
    601           sprintf(pumpPrint,"Not good enough");
     601          sprintf(pumpPrint,"After further testing solution no better than previous of %g",solutionValue);
    602602          model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    603603            << pumpPrint
  • trunk/Cbc/src/CbcHeuristicGreedy.cpp

    r904 r954  
    372372  if (model_&&when()<10) {
    373373    if (model_->numberIntegers()!=
    374         model_->numberObjects())
     374        model_->numberObjects()&&(model_->numberObjects()||
     375                                  (model_->specialOptions()&1024)==0))
    375376      setWhen(0);
    376377    // Only works if costs positive, coefficients positive and all rows G
  • trunk/Cbc/src/CbcMessage.cpp

    r931 r954  
    6363  {CBC_RELAXED1,42,1,"Possible objective of %.18g but variable %d is %g from integer value, integer tolerance %g"},
    6464  {CBC_RELAXED2,43,1,"Possible objective of %.18g but variables are up to %g away from bound (within tolerance of %g) - might be able to fudge solution - but do you want to?"},
     65  {CBC_RESTART,44,1,"Reduced cost fixing - %d rows, %d columns - restarting search"},
    6566  {CBC_DUMMY_END,999999,0,""}
    6667};
  • trunk/Cbc/src/CbcMessage.hpp

    r931 r954  
    6767  CBC_RELAXED1,
    6868  CBC_RELAXED2,
     69  CBC_RESTART,
    6970  CBC_DUMMY_END
    7071};
  • trunk/Cbc/src/CbcModel.cpp

    r952 r954  
    16651665#endif
    16661666#endif
     1667 // Save copy of solver
     1668 OsiSolverInterface * saveSolver = NULL;
     1669 if (!parentModel_&&(specialOptions_&512)!=0)
     1670   saveSolver = solver_->clone();
    16671671/*
    16681672  We've taken the continuous relaxation as far as we can. Time to branch.
     
    21832187    locked = false;
    21842188#endif
     2189    // If done 100 nodes see if worth trying reduction
     2190    if (numberNodes_==100&&saveSolver) {
     2191      bool tryNewSearch=solverCharacteristics_->reducedCostsAccurate();
     2192      int numberColumns = getNumCols();
     2193      if (tryNewSearch) {
     2194        double cutoff = getCutoff() ;
     2195        saveSolver->resolve();
     2196        double direction = saveSolver->getObjSense() ;
     2197        double gap = cutoff - saveSolver->getObjValue()*direction ;
     2198        double tolerance;
     2199        saveSolver->getDblParam(OsiDualTolerance,tolerance) ;
     2200        if (gap<=0.0)
     2201          gap = tolerance;
     2202        gap += 100.0*tolerance;
     2203        double integerTolerance = getDblParam(CbcIntegerTolerance) ;
     2204       
     2205        const double *lower = saveSolver->getColLower() ;
     2206        const double *upper = saveSolver->getColUpper() ;
     2207        const double *solution = saveSolver->getColSolution() ;
     2208        const double *reducedCost = saveSolver->getReducedCost() ;
     2209       
     2210        int numberFixed = 0 ;
     2211        int numberFixed2=0;
     2212        for (int i = 0 ; i < numberIntegers_ ; i++) {
     2213          int iColumn = integerVariable_[i] ;
     2214          double djValue = direction*reducedCost[iColumn] ;
     2215          if (upper[iColumn]-lower[iColumn] > integerTolerance) {
     2216            if (solution[iColumn] < lower[iColumn]+integerTolerance && djValue > gap) {
     2217              saveSolver->setColUpper(iColumn,lower[iColumn]) ;
     2218              numberFixed++ ;
     2219            } else if (solution[iColumn] > upper[iColumn]-integerTolerance && -djValue > gap) {
     2220              saveSolver->setColLower(iColumn,upper[iColumn]) ;
     2221              numberFixed++ ;
     2222            }
     2223          } else {
     2224            numberFixed2++;
     2225          }
     2226        }
     2227#ifdef COIN_DEVELOP
     2228        printf("Restart could fix %d integers (%d already fixed)\n",
     2229               numberFixed+numberFixed2,numberFixed2);
     2230#endif
     2231        numberFixed += numberFixed2;
     2232        if (numberFixed*10<numberColumns)
     2233          tryNewSearch=false;
     2234      }
     2235      if (tryNewSearch) {
     2236        // back to solver without cuts?
     2237#if 1
     2238        OsiSolverInterface * solver2 = continuousSolver_->clone();
     2239#else
     2240        OsiSolverInterface * solver2 = saveSolver->clone();
     2241#endif
     2242        const double *lower = saveSolver->getColLower() ;
     2243        const double *upper = saveSolver->getColUpper() ;
     2244        for (int i = 0 ; i < numberIntegers_ ; i++) {
     2245          int iColumn = integerVariable_[i] ;
     2246          solver2->setColLower(iColumn,lower[iColumn]);
     2247          solver2->setColUpper(iColumn,upper[iColumn]);
     2248        }
     2249        // swap
     2250        delete saveSolver;
     2251        saveSolver=solver2;
     2252        double * newSolution = new double[numberColumns];
     2253        double objectiveValue=cutoff;
     2254        CbcSerendipity heuristic(*this);
     2255        if (bestSolution_)
     2256          heuristic.setInputSolution(bestSolution_,bestObjective_);
     2257        heuristic.setFractionSmall(0.7);
     2258        heuristic.setFeasibilityPumpOptions(1008003);
     2259        int returnCode= heuristic.smallBranchAndBound(saveSolver,
     2260                                                      -1,newSolution,
     2261                                                      objectiveValue,
     2262                                                      cutoff,"Reduce");
     2263        if (returnCode==-1) {
     2264#ifdef COIN_DEVELOP
     2265          printf("Restart - not small enough to do search after fixing\n");
     2266#endif
     2267          delete [] newSolution;
     2268        } else {
     2269          assert (returnCode>=0);
     2270          if ((returnCode&1)!=0) {
     2271            // increment number of solutions so other heuristics can test
     2272            numberSolutions_++;
     2273            numberHeuristicSolutions_++;
     2274            lastHeuristic_ = NULL;
     2275            setBestSolution(CBC_ROUNDING,objectiveValue,newSolution) ;
     2276          }
     2277          delete [] newSolution;
     2278          break;
     2279        }
     2280      }
     2281      delete saveSolver;
     2282      saveSolver=NULL;
     2283    }
    21852284/*
    21862285  Check for abort on limits: node count, solution count, time, integrality gap.
     
    35273626    fastNodeDepth_ -= 1000000;
    35283627  }
     3628  delete saveSolver;
    35293629#if COIN_DEVELOP>1
    35303630  void print_fac_stats();
     
    54695569  down the current situation.
    54705570*/
    5471 
     5571#if 0
    54725572int CbcModel::reducedCostFix ()
    54735573
     
    55445644  numberDJFixed_ += numberFixed;
    55455645  return numberFixed; }
    5546 
     5646#else
     5647int CbcModel::reducedCostFix ()
     5648
     5649{
     5650  if(!solverCharacteristics_->reducedCostsAccurate())
     5651    return 0; //NLP
     5652  double cutoff = getCutoff() ;
     5653  double direction = solver_->getObjSense() ;
     5654  double gap = cutoff - solver_->getObjValue()*direction ;
     5655  double tolerance;
     5656  solver_->getDblParam(OsiDualTolerance,tolerance) ;
     5657  if (gap<=0.0)
     5658    gap = tolerance; //return 0;
     5659  gap += 100.0*tolerance;
     5660  double integerTolerance = getDblParam(CbcIntegerTolerance) ;
     5661
     5662  const double *lower = solver_->getColLower() ;
     5663  const double *upper = solver_->getColUpper() ;
     5664  const double *solution = solver_->getColSolution() ;
     5665  const double *reducedCost = solver_->getReducedCost() ;
     5666
     5667  int numberFixed = 0 ;
     5668  int numberTightened = 0 ;
     5669
     5670# ifdef COIN_HAS_CLP
     5671  OsiClpSolverInterface * clpSolver
     5672    = dynamic_cast<OsiClpSolverInterface *> (solver_);
     5673  ClpSimplex * clpSimplex=NULL;
     5674  if (clpSolver)
     5675    clpSimplex = clpSolver->getModelPtr();
     5676# endif
     5677  for (int i = 0 ; i < numberIntegers_ ; i++) {
     5678    int iColumn = integerVariable_[i] ;
     5679    double djValue = direction*reducedCost[iColumn] ;
     5680    double boundGap=upper[iColumn]-lower[iColumn];
     5681    if (boundGap > integerTolerance) {
     5682      if (solution[iColumn] < lower[iColumn]+integerTolerance
     5683          && djValue*boundGap > gap) {
     5684#ifdef COIN_HAS_CLP
     5685        // may just have been fixed before
     5686        if (clpSimplex) {
     5687          if (clpSimplex->getColumnStatus(iColumn)==ClpSimplex::basic) {
     5688#ifdef COIN_DEVELOP
     5689            printf("DJfix %d has status of %d, dj of %g gap %g, bounds %g %g\n",
     5690                   iColumn,clpSimplex->getColumnStatus(iColumn),
     5691                   djValue,gap,lower[iColumn],upper[iColumn]);
     5692#endif
     5693          } else {         
     5694            assert(clpSimplex->getColumnStatus(iColumn)==ClpSimplex::atLowerBound||
     5695                   clpSimplex->getColumnStatus(iColumn)==ClpSimplex::isFixed);
     5696          }
     5697        }
     5698#endif
     5699        double newBound=lower[iColumn];
     5700        if (boundGap>1.99) {
     5701          boundGap = gap/djValue+1.0e-4*boundGap;
     5702          newBound=lower[iColumn]+floor(boundGap);
     5703          numberTightened++;
     5704          //if (newBound)
     5705          //printf("tighter - gap %g dj %g newBound %g\n",
     5706          //   gap,djValue,newBound);
     5707        }
     5708        solver_->setColUpper(iColumn,newBound) ;
     5709        numberFixed++ ;
     5710      } else if (solution[iColumn] > upper[iColumn]-integerTolerance && -djValue > boundGap*gap) {
     5711#ifdef COIN_HAS_CLP
     5712        // may just have been fixed before
     5713        if (clpSimplex) {
     5714          if (clpSimplex->getColumnStatus(iColumn)==ClpSimplex::basic) {
     5715#ifdef COIN_DEVELOP
     5716            printf("DJfix %d has status of %d, dj of %g gap %g, bounds %g %g\n",
     5717                   iColumn,clpSimplex->getColumnStatus(iColumn),
     5718                   djValue,gap,lower[iColumn],upper[iColumn]);
     5719#endif
     5720          } else {         
     5721            assert(clpSimplex->getColumnStatus(iColumn)==ClpSimplex::atUpperBound||
     5722                   clpSimplex->getColumnStatus(iColumn)==ClpSimplex::isFixed);
     5723          }
     5724        }
     5725#endif
     5726        double newBound=upper[iColumn];
     5727        if (boundGap>1.99) {
     5728          boundGap = -gap/djValue+1.0e-4*boundGap;
     5729          newBound=upper[iColumn]-floor(boundGap);
     5730          //if (newBound)
     5731          //printf("tighter - gap %g dj %g newBound %g\n",
     5732          //   gap,djValue,newBound);
     5733          numberTightened++;
     5734        }
     5735        solver_->setColLower(iColumn,newBound) ;
     5736        numberFixed++ ;
     5737      }
     5738    }
     5739  }
     5740  numberDJFixed_ += numberFixed-numberTightened;
     5741#ifdef COIN_DEVELOP
     5742  if (numberTightened)
     5743    printf("%d tightened, %d others fixed\n",numberTightened,
     5744           numberFixed-numberTightened);
     5745#endif
     5746  return numberFixed; }
     5747#endif
    55475748// Collect coding to replace whichGenerator
    55485749void
  • trunk/Cbc/src/CbcModel.hpp

    r940 r954  
    784784    inline int getIterationCount() const
    785785    { return numberIterations_;}
     786    /// Increment how many iterations it took to solve the problem.
     787    inline void incrementIterationCount(int value)
     788    { numberIterations_ += value;}
    786789    /// Get how many Nodes it took to solve the problem.
    787790    inline int getNodeCount() const
    788791    { return numberNodes_;}
     792    /// Increment how many nodes it took to solve the problem.
     793    inline void incrementNodeCount(int value)
     794    { numberNodes_ += value;}
    789795    /** Final status of problem
    790796        Some of these can be found out by is...... functions
  • trunk/Cbc/src/CbcSolver.cpp

    r934 r954  
    164164#include "CbcHeuristicDiveGuided.hpp"
    165165#include "CbcHeuristicDiveVectorLength.hpp"
     166#include "CbcHeuristicDivePseudoCost.hpp"
     167#include "CbcHeuristicDiveLineSearch.hpp"
    166168#include "CbcTreeLocal.hpp"
    167169#include "CbcCompareActual.hpp"
     
    32323234  int useRINS = parameters_[whichParam(RINS,numberParameters_,parameters_)].currentOptionAsInteger();
    32333235  int useRENS = parameters_[whichParam(RENS,numberParameters_,parameters_)].currentOptionAsInteger();
    3234   int useDIVING = parameters_[whichParam(DIVING,numberParameters_,parameters_)].currentOptionAsInteger();
     3236  int useDIVING = parameters_[whichParam(DIVINGA,numberParameters_,parameters_)].currentOptionAsInteger();
    32353237  // FPump done first as it only works if no solution
    32363238  int kType = (type<3) ? type : 1;
     
    33793381  }
    33803382  // change later?
     3383  {
     3384    int useDiving2=0;
     3385    useDiving2 |= 1*parameters_[whichParam(DIVINGV,numberParameters_,parameters_)].currentOptionAsInteger();
     3386    useDiving2 |= 2*parameters_[whichParam(DIVINGG,numberParameters_,parameters_)].currentOptionAsInteger();
     3387    useDiving2 |= 4*parameters_[whichParam(DIVINGF,numberParameters_,parameters_)].currentOptionAsInteger();
     3388    useDiving2 |= 8*parameters_[whichParam(DIVINGC,numberParameters_,parameters_)].currentOptionAsInteger();
     3389    useDiving2 |= 16*parameters_[whichParam(DIVINGL,numberParameters_,parameters_)].currentOptionAsInteger();
     3390    useDiving2 |= 32*parameters_[whichParam(DIVINGP,numberParameters_,parameters_)].currentOptionAsInteger();
     3391    if (useDiving2)
     3392      useDIVING=useDiving2;
     3393  }
    33813394  if (useDIVING>=kType) {
    33823395    int diveOptions=parameters_[whichParam(DIVEOPT,numberParameters_,parameters_)].intValue();
     
    34063419      heuristicDC.setWhen(diveOptions);
    34073420      model->addHeuristic(&heuristicDC) ;
     3421    }
     3422    if ((useDIVING&16)!=0) {
     3423      CbcHeuristicDiveLineSearch heuristicDL(*model);
     3424      heuristicDL.setHeuristicName("DiveLineSearch");
     3425      heuristicDL.setWhen(diveOptions);
     3426      model->addHeuristic(&heuristicDL) ;
     3427    }
     3428    if ((useDIVING&32)!=0) {
     3429      CbcHeuristicDivePseudoCost heuristicDP(*model);
     3430      heuristicDP.setHeuristicName("DivePseudoCost");
     3431      heuristicDP.setWhen(diveOptions);
     3432      model->addHeuristic(&heuristicDP) ;
    34083433    }
    34093434    anyToDo=true;
     
    44064431                  parameters_[iParam].setIntValue(6);
    44074432                  tunePreProcess=6;
    4408                   iParam = whichParam(DIVING,numberParameters_,parameters_);
     4433                  iParam = whichParam(DIVINGA,numberParameters_,parameters_);
    44094434                  parameters_[iParam].setCurrentOption("C");
    44104435                  iParam = whichParam(RINS,numberParameters_,parameters_);
     
    46604685              break;
    46614686            case GREEDY:
    4662             case DIVING:
     4687            case DIVINGA:
    46634688            case COMBINE:
    46644689            case LOCALTREE:
     
    63046329              OsiSolverInterface * strengthenedModel=NULL;
    63056330              if (type==BAB||type==MIPLIB) {
     6331                if (parameters_[whichParam(EXPERIMENT,numberParameters_,
     6332                                           parameters_)].intValue()==2) {
     6333                  // try reduced model
     6334                  babModel_->setSpecialOptions(babModel_->specialOptions()|512);
     6335                }
    63066336                {
    63076337                  int extra4 = parameters_[whichParam(EXTRA4,numberParameters_,parameters_)].intValue();
  • trunk/Cbc/src/CbcStrategy.cpp

    r931 r954  
    247247    generator->setTiming(true);
    248248  }
    249   if (model.getNumCols()<500)
    250     model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
    251   else if (model.getNumCols()<5000)
    252     model.setMaximumCutPassesAtRoot(100); // use minimum drop
    253   else
    254     model.setMaximumCutPassesAtRoot(20);
     249  int currentPasses = model.getMaximumCutPassesAtRoot();
     250  if (currentPasses>=0) {
     251    if (model.getNumCols()<500)
     252      model.setMaximumCutPassesAtRoot(-CoinMax(100,currentPasses)); // always do 100 if possible
     253    else if (model.getNumCols()<5000)
     254      model.setMaximumCutPassesAtRoot(CoinMax(100,currentPasses)); // use minimum drop
     255    else
     256      model.setMaximumCutPassesAtRoot(CoinMax(20,currentPasses));
     257  } else {
     258    currentPasses=-currentPasses;
     259    if (model.getNumCols()<500)
     260      model.setMaximumCutPassesAtRoot(-CoinMax(100,currentPasses)); // always do 100 if possible
     261    else
     262      model.setMaximumCutPassesAtRoot(-CoinMax(20,currentPasses));
     263  }
    255264}
    256265// Setup heuristics
  • trunk/Cbc/src/CbcTree.cpp

    r940 r954  
    361361      value=node->checkIsCutoff(cutoff);
    362362    }
    363     bestPossibleObjective = CoinMin(bestPossibleObjective,value);
    364363    if (value >= cutoff||!node->active()) {
    365364      if (node) {
     
    368367      }
    369368    } else {
     369      bestPossibleObjective = CoinMin(bestPossibleObjective,value);
    370370      nodeArray[k++]=node;
    371371    }
Note: See TracChangeset for help on using the changeset viewer.