Ignore:
Timestamp:
Nov 6, 2008 4:48:31 PM (11 years ago)
Author:
forrest
Message:

add in a few modifications and naive heuristic

File:
1 edited

Legend:

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

    r961 r1100  
    593593  memset(used_,0,numberColumns);
    594594}
    595 
     595// Default Constructor
     596CbcHeuristicNaive::CbcHeuristicNaive()
     597  :CbcHeuristic()
     598{
     599  large_=1.0e6;
     600}
     601
     602// Constructor with model - assumed before cuts
     603
     604CbcHeuristicNaive::CbcHeuristicNaive(CbcModel & model)
     605  :CbcHeuristic(model)
     606{
     607  large_=1.0e6;
     608}
     609
     610// Destructor
     611CbcHeuristicNaive::~CbcHeuristicNaive ()
     612{
     613}
     614
     615// Clone
     616CbcHeuristic *
     617CbcHeuristicNaive::clone() const
     618{
     619  return new CbcHeuristicNaive(*this);
     620}
     621// Create C++ lines to get to current state
     622void
     623CbcHeuristicNaive::generateCpp( FILE * fp)
     624{
     625  CbcHeuristicNaive other;
     626  fprintf(fp,"0#include \"CbcHeuristicNaive.hpp\"\n");
     627  fprintf(fp,"3  CbcHeuristicNaive naive(*cbcModel);\n");
     628  CbcHeuristic::generateCpp(fp,"naive");
     629  if (large_!=other.large_)
     630    fprintf(fp,"3  naive.setLarge(%g);\n",large_);
     631  else
     632    fprintf(fp,"4  naive.setLarge(%g);\n",large_);
     633  fprintf(fp,"3  cbcModel->addHeuristic(&naive);\n");
     634}
     635
     636// Copy constructor
     637CbcHeuristicNaive::CbcHeuristicNaive(const CbcHeuristicNaive & rhs)
     638:
     639  CbcHeuristic(rhs),
     640  large_(rhs.large_)
     641{
     642}
     643
     644// Assignment operator
     645CbcHeuristicNaive &
     646CbcHeuristicNaive::operator=( const CbcHeuristicNaive& rhs)
     647{
     648  if (this!=&rhs) {
     649    CbcHeuristic::operator=(rhs);
     650    large_ = rhs.large_;
     651  }
     652  return *this;
     653}
     654
     655// Resets stuff if model changes
     656void
     657CbcHeuristicNaive::resetModel(CbcModel * model)
     658{
     659  CbcHeuristic::resetModel(model);
     660}
     661int
     662CbcHeuristicNaive::solution(double & solutionValue,
     663                         double * betterSolution)
     664{
     665  numCouldRun_++;
     666  // See if to do
     667  bool atRoot = model_->getNodeCount()==0;
     668  int passNumber = model_->getCurrentPassNumber();
     669  if (!when()||(when()==1&&model_->phase()!=1)||!atRoot||passNumber!=1)
     670    return 0; // switched off
     671  // Don't do if it was this heuristic which found solution!
     672  if (this==model_->lastHeuristic())
     673    return 0;
     674  numRuns_++;
     675  double cutoff;
     676  model_->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
     677  double direction = model_->solver()->getObjSense();
     678  cutoff *= direction;
     679  cutoff = CoinMin(cutoff,solutionValue);
     680  OsiSolverInterface * solver = model_->continuousSolver();
     681  if (!solver)
     682    solver = model_->solver();
     683  const double * colLower = solver->getColLower();
     684  const double * colUpper = solver->getColUpper();
     685  const double * objective = solver->getObjCoefficients();
     686
     687  int numberColumns = model_->getNumCols();
     688  int numberIntegers = model_->numberIntegers();
     689  const int * integerVariable = model_->integerVariable();
    596690 
     691  int i;
     692  bool solutionFound=false;
     693  CoinWarmStartBasis saveBasis;
     694  CoinWarmStartBasis * basis =
     695    dynamic_cast<CoinWarmStartBasis *>(solver->getWarmStart()) ;
     696  if (basis) {
     697    saveBasis = * basis;
     698    delete basis;
     699  }
     700  // First just fix all integers as close to zero as possible
     701  OsiSolverInterface * newSolver = solver->clone();
     702  for (i=0;i<numberIntegers;i++) {
     703    int iColumn=integerVariable[i];
     704    double lower = colLower[iColumn];
     705    double upper = colUpper[iColumn];
     706    double value;
     707    if (lower>0.0)
     708      value=lower;
     709    else if (upper<0.0)
     710      value=upper;
     711    else
     712      value=0.0;
     713    newSolver->setColLower(iColumn,value);
     714    newSolver->setColUpper(iColumn,value);
     715  }
     716  newSolver->initialSolve();
     717  if (newSolver->isProvenOptimal()) {
     718    double solValue = newSolver->getObjValue()*direction ;
     719    if (solValue<cutoff) {
     720      // we have a solution
     721      solutionFound=true;
     722      solutionValue=solValue;
     723      memcpy(betterSolution,newSolver->getColSolution(),
     724             numberColumns*sizeof(double));
     725      printf("Naive fixing close to zero gave solution of %g\n",solutionValue);
     726      cutoff = solValue - model_->getCutoffIncrement();
     727    }
     728  }
     729  // Now fix all integers as close to zero if zero or large cost
     730  int nFix=0;
     731  for (i=0;i<numberIntegers;i++) {
     732    int iColumn=integerVariable[i];
     733    double lower = colLower[iColumn];
     734    double upper = colUpper[iColumn];
     735    double value;
     736    if (fabs(objective[i])>0.0&&fabs(objective[i])<large_) {
     737      nFix++;
     738      if (lower>0.0)
     739        value=lower;
     740      else if (upper<0.0)
     741        value=upper;
     742      else
     743        value=0.0;
     744      newSolver->setColLower(iColumn,value);
     745      newSolver->setColUpper(iColumn,value);
     746    }
     747  }
     748  const double * solution = solver->getColSolution();
     749  if (nFix) {
     750    newSolver->setWarmStart(&saveBasis);
     751    newSolver->setColSolution(solution);
     752    newSolver->initialSolve();
     753    if (newSolver->isProvenOptimal()) {
     754      double solValue = newSolver->getObjValue()*direction ;
     755      if (solValue<cutoff) {
     756        // try branch and bound
     757        double * newSolution = new double [numberColumns];
     758        printf("%d fixed after fixing costs\n",nFix);
     759        int returnCode = smallBranchAndBound(newSolver,
     760                                             numberNodes_,newSolution,
     761                                             solutionValue,
     762                                             solutionValue,"CbcHeuristicNaive1");
     763        if (returnCode<0)
     764          returnCode=0; // returned on size
     765        if ((returnCode&2)!=0) {
     766          // could add cut
     767          returnCode &= ~2;
     768        }
     769        if (returnCode==1) {
     770          // solution
     771          solutionFound=true;
     772          memcpy(betterSolution,newSolution,
     773                 numberColumns*sizeof(double));
     774          printf("Naive fixing zeros gave solution of %g\n",solutionValue);
     775          cutoff = solutionValue - model_->getCutoffIncrement();
     776        }
     777        delete [] newSolution;
     778      }
     779    }
     780  }
     781#if 1
     782  newSolver->setObjSense(-direction); // maximize
     783  newSolver->setWarmStart(&saveBasis);
     784  newSolver->setColSolution(solution);
     785  for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     786    double value = solution[iColumn];
     787    double lower = colLower[iColumn];
     788    double upper = colUpper[iColumn];
     789    double newLower;
     790    double newUpper;
     791    if (newSolver->isInteger(iColumn)) {
     792      newLower = CoinMax(lower,floor(value)-2.0);
     793      newUpper = CoinMin(upper,ceil(value)+2.0);
     794    } else {
     795      newLower = CoinMax(lower,value-1.0e5);
     796      newUpper = CoinMin(upper,value+1.0e-5);
     797    }
     798    newSolver->setColLower(iColumn,newLower);
     799    newSolver->setColUpper(iColumn,newUpper);
     800  }
     801  newSolver->initialSolve();
     802  if (newSolver->isProvenOptimal()) {
     803    double solValue = newSolver->getObjValue()*direction ;
     804    if (solValue<cutoff) {
     805      nFix=0;
     806      newSolver->setObjSense(direction); // correct direction
     807      const double * thisSolution = newSolver->getColSolution();
     808      for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     809        double value = solution[iColumn];
     810        double lower = colLower[iColumn];
     811        double upper = colUpper[iColumn];
     812        double newLower=lower;
     813        double newUpper=upper;
     814        if (newSolver->isInteger(iColumn)) {
     815          if (value<lower+1.0e-6) {
     816            nFix++;
     817            newUpper=lower;
     818          } else if (value>upper-1.0e-6) {
     819            nFix++;
     820            newLower=upper;
     821          } else {
     822            newLower = CoinMax(lower,floor(value)-2.0);
     823            newUpper = CoinMin(upper,ceil(value)+2.0);
     824          }
     825        }
     826        newSolver->setColLower(iColumn,newLower);
     827        newSolver->setColUpper(iColumn,newUpper);
     828      }
     829      // try branch and bound
     830      double * newSolution = new double [numberColumns];
     831      printf("%d fixed after maximizing\n",nFix);
     832      int returnCode = smallBranchAndBound(newSolver,
     833                                           numberNodes_,newSolution,
     834                                           solutionValue,
     835                                           solutionValue,"CbcHeuristicNaive1");
     836      if (returnCode<0)
     837        returnCode=0; // returned on size
     838      if ((returnCode&2)!=0) {
     839        // could add cut
     840        returnCode &= ~2;
     841      }
     842      if (returnCode==1) {
     843        // solution
     844        solutionFound=true;
     845        memcpy(betterSolution,newSolution,
     846               numberColumns*sizeof(double));
     847        printf("Naive maximizing gave solution of %g\n",solutionValue);
     848        cutoff = solutionValue - model_->getCutoffIncrement();
     849      }
     850      delete [] newSolution;
     851    }
     852  }
     853#endif
     854  delete newSolver;
     855  return solutionFound ? 1 : 0;
     856}
     857// update model
     858void CbcHeuristicNaive::setModel(CbcModel * model)
     859{
     860  model_ = model;
     861}
     862
     863 
Note: See TracChangeset for help on using the changeset viewer.