Ignore:
Timestamp:
Nov 5, 2009 10:57:25 AM (10 years ago)
Author:
forrest
Message:

Creating new stable branch 2.4 from trunk (rev 1270)

Location:
stable/2.4
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed
  • stable/2.4

    • Property svn:externals
      •  

        old new  
        77CoinUtils         https://projects.coin-or.org/svn/CoinUtils/stable/2.5/CoinUtils
        88Cgl               https://projects.coin-or.org/svn/Cgl/stable/0.54/Cgl
        9 Clp               https://projects.coin-or.org/svn/Clp/stable/1.10/Clp
         9Clp               https://projects.coin-or.org/svn/Clp/stable/1.11/Clp
        1010Osi               https://projects.coin-or.org/svn/Osi/stable/0.100/Osi
        1111Vol               https://projects.coin-or.org/svn/Vol/stable/1.1/Vol
  • stable/2.4/Cbc/src/CbcHeuristicLocal.cpp

    r1132 r1271  
     1/* $Id$ */
    12// Copyright (C) 2002, International Business Machines
    23// Corporation and others.  All Rights Reserved.
     
    3637  // Get a copy of original matrix
    3738  assert(model.solver());
    38   matrix_ = *model.solver()->getMatrixByCol();
     39  if (model.solver()->getNumRows()) {
     40    matrix_ = *model.solver()->getMatrixByCol();
     41  }
    3942  int numberColumns = model.solver()->getNumCols();
    40   used_ = new char[numberColumns];
    41   memset(used_,0,numberColumns);
     43  used_ = new int[numberColumns];
     44  memset(used_,0,numberColumns*sizeof(int));
    4245}
    4346
     
    7982  if (model_&&rhs.used_) {
    8083    int numberColumns = model_->solver()->getNumCols();
    81     used_ = new char[numberColumns];
    82     memcpy(used_,rhs.used_,numberColumns);
     84    used_ = CoinCopyOfArray(rhs.used_,numberColumns);
    8385  } else {
    8486    used_=NULL;
     
    98100    if (model_&&rhs.used_) {
    99101      int numberColumns = model_->solver()->getNumCols();
    100       used_ = new char[numberColumns];
    101       memcpy(used_,rhs.used_,numberColumns);
     102      used_ = CoinCopyOfArray(rhs.used_,numberColumns);
    102103    } else {
    103104      used_=NULL;
     
    109110// Resets stuff if model changes
    110111void
    111 CbcHeuristicLocal::resetModel(CbcModel * model)
     112CbcHeuristicLocal::resetModel(CbcModel * /*model*/)
    112113{
    113114  //CbcHeuristic::resetModel(model);
     
    115116  if (model_&&used_) {
    116117    int numberColumns = model_->solver()->getNumCols();
    117     used_ = new char[numberColumns];
    118     memset(used_,0,numberColumns);
     118    used_ = new int[numberColumns];
     119    memset(used_,0,numberColumns*sizeof(int));
    119120  } else {
    120121    used_=NULL;
     
    125126CbcHeuristicLocal::solutionFix(double & objectiveValue,
    126127                            double * newSolution,
    127                             const int * keep)
     128                               const int * /*keep*/)
    128129{
    129130  numCouldRun_++;
     
    156157    }
    157158  }
    158   int returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,objectiveValue,
    159                                          objectiveValue,"CbcHeuristicLocal");
    160   if (returnCode<0)
    161     returnCode=0; // returned on size
     159  int returnCode = 0;
     160  if (nFix*10>numberIntegers) {
     161    returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,objectiveValue,
     162                                     objectiveValue,"CbcHeuristicLocal");
     163    if (returnCode<0) {
     164      returnCode=0; // returned on size
     165      int numberColumns=newSolver->getNumCols();
     166      int numberContinuous = numberColumns-numberIntegers;
     167      if (numberContinuous>2*numberIntegers&&
     168          nFix*10<numberColumns) {
     169#define LOCAL_FIX_CONTINUOUS
     170#ifdef LOCAL_FIX_CONTINUOUS
     171        //const double * colUpper = newSolver->getColUpper();
     172        const double * colLower = newSolver->getColLower();
     173        int nAtLb=0;
     174        //double sumDj=0.0;
     175        const double * dj = newSolver->getReducedCost();
     176        double direction=newSolver->getObjSense();
     177        for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     178          if (!newSolver->isInteger(iColumn)) {
     179            if (!used_[iColumn]) {
     180              //double djValue = dj[iColumn]*direction;
     181              nAtLb++;
     182              //sumDj += djValue;
     183            }
     184          }
     185        }
     186        if (nAtLb) {
     187          // fix some continuous
     188          double * sort = new double[nAtLb];
     189          int * which = new int [nAtLb];
     190          //double threshold = CoinMax((0.01*sumDj)/static_cast<double>(nAtLb),1.0e-6);
     191          int nFix2=0;
     192          for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     193            if (!newSolver->isInteger(iColumn)) {
     194              if (!used_[iColumn]) {
     195                double djValue = dj[iColumn]*direction;
     196                if (djValue>1.0e-6) {
     197                  sort[nFix2]=-djValue;
     198                  which[nFix2++]=iColumn;
     199                }
     200              }
     201            }
     202          }
     203          CoinSort_2(sort,sort+nFix2,which);
     204          int divisor=2;
     205          nFix2=CoinMin(nFix2,(numberColumns-nFix)/divisor);
     206          for (int i=0;i<nFix2;i++) {
     207            int iColumn = which[i];
     208            newSolver->setColUpper(iColumn,colLower[iColumn]);
     209          }
     210          delete [] sort;
     211          delete [] which;
     212#ifdef CLP_INVESTIGATE2
     213          printf("%d integers have zero value, and %d continuous fixed at lb\n",
     214                 nFix,nFix2);
     215#endif
     216          returnCode = smallBranchAndBound(newSolver,
     217                                           numberNodes_,newSolution,
     218                                           objectiveValue,
     219                                           objectiveValue,"CbcHeuristicLocal");
     220          if (returnCode<0)
     221            returnCode=0; // returned on size
     222        }
     223#endif
     224      }
     225    }
     226  }
    162227  if ((returnCode&2)!=0) {
    163228    // could add cut
     
    216281  double * newSolution = new double [numberColumns];
    217282  memcpy(newSolution,solution,numberColumns*sizeof(double));
     283#ifdef LOCAL_FIX_CONTINUOUS
     284  // mark continuous used
     285  const double * columnLower = solver->getColLower();
     286  for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     287    if (!solver->isInteger(iColumn)) {
     288      if (solution[iColumn]>columnLower[iColumn]+1.0e-8)
     289        used_[iColumn]=numberSolutions_;
     290    }
     291  }
     292#endif
    218293
    219294  // way is 1 if down possible, 2 if up possible, 3 if both possible
     
    249324    // if away from lower bound mark that fact
    250325    if (nearest>originalLower) {
    251       used_[iColumn]=1;
     326      used_[iColumn]=numberSolutions_;
    252327    }
    253328    cost[i] = direction*objective[iColumn];
     
    258333    if (value<originalUpper-0.5)
    259334      iway |= 2;
    260     way[i]=iway;
     335    way[i]=static_cast<char>(iway);
    261336  }
    262337  // get row activities
     
    503578        if (value<originalUpper-0.5)
    504579          iway |= 2;
    505         way[goodK]=iway;
     580        way[goodK]=static_cast<char>(iway);
    506581      }
    507582    }
     
    547622          // if away from lower bound mark that fact
    548623          if (value>originalLower) {
    549             used_[iColumn]=1;
     624            used_[iColumn]=numberSolutions_;
    550625          }
    551626        }
     
    574649  delete [] mark;
    575650  if (numberSolutions_>1&&swap_==1) {
    576     int i;
    577     for ( i=0;i<numberColumns;i++) {
    578       if (used_[i]>1)
    579         break;
    580     }
    581     if (i==numberColumns) {
    582       // modify used_ if just one
    583       const int * used = model_->usedInSolution();
    584       for (int i=0;i<numberColumns;i++)
    585         used_[i]= CoinMin(used[i],255);
    586     }
    587651    // try merge
    588652    int returnCode2=solutionFix( solutionValue, betterSolution,NULL);
     
    598662  // Get a copy of original matrix
    599663  assert(model_->solver());
    600   matrix_ = *model_->solver()->getMatrixByCol();
     664  if (model_->solver()->getNumRows()) {
     665    matrix_ = *model_->solver()->getMatrixByCol();
     666  }
    601667  delete [] used_;
    602668  int numberColumns = model->solver()->getNumCols();
    603   used_ = new char[numberColumns];
    604   memset(used_,0,numberColumns);
     669  used_ = new int[numberColumns];
     670  memset(used_,0,numberColumns*sizeof(int));
    605671}
    606672// Default Constructor
     
    635701{
    636702  CbcHeuristicNaive other;
    637   fprintf(fp,"0#include \"CbcHeuristicNaive.hpp\"\n");
     703  fprintf(fp,"0#include \"CbcHeuristicLocal.hpp\"\n");
    638704  fprintf(fp,"3  CbcHeuristicNaive naive(*cbcModel);\n");
    639705  CbcHeuristic::generateCpp(fp,"naive");
     
    710776  }
    711777  // First just fix all integers as close to zero as possible
    712   OsiSolverInterface * newSolver = solver->clone();
     778  OsiSolverInterface * newSolver = cloneBut(7); // wassolver->clone();
    713779  for (i=0;i<numberIntegers;i++) {
    714780    int iColumn=integerVariable[i];
     
    755821      newSolver->setColLower(iColumn,value);
    756822      newSolver->setColUpper(iColumn,value);
     823    } else {
     824      // set back to original
     825      newSolver->setColLower(iColumn,lower);
     826      newSolver->setColUpper(iColumn,upper);
    757827    }
    758828  }
     
    871941  model_ = model;
    872942}
     943// Default Constructor
     944CbcHeuristicCrossover::CbcHeuristicCrossover()
     945  :CbcHeuristic(),
     946   numberSolutions_(0),
     947   useNumber_(3)
     948{
     949  setWhen(1);
     950}
     951
     952// Constructor with model - assumed before cuts
     953
     954CbcHeuristicCrossover::CbcHeuristicCrossover(CbcModel & model)
     955  :CbcHeuristic(model),
     956   numberSolutions_(0),
     957   useNumber_(3)
     958{
     959  setWhen(1);
     960  for (int i=0;i<10;i++)
     961    random_[i]=model.randomNumberGenerator()->randomDouble();
     962}
     963
     964// Destructor
     965CbcHeuristicCrossover::~CbcHeuristicCrossover ()
     966{
     967}
     968
     969// Clone
     970CbcHeuristic *
     971CbcHeuristicCrossover::clone() const
     972{
     973  return new CbcHeuristicCrossover(*this);
     974}
     975// Create C++ lines to get to current state
     976void
     977CbcHeuristicCrossover::generateCpp( FILE * fp)
     978{
     979  CbcHeuristicCrossover other;
     980  fprintf(fp,"0#include \"CbcHeuristicLocal.hpp\"\n");
     981  fprintf(fp,"3  CbcHeuristicCrossover crossover(*cbcModel);\n");
     982  CbcHeuristic::generateCpp(fp,"crossover");
     983  if (useNumber_!=other.useNumber_)
     984    fprintf(fp,"3  crossover.setNumberSolutions(%d);\n",useNumber_);
     985  else
     986    fprintf(fp,"4  crossover.setNumberSolutions(%d);\n",useNumber_);
     987  fprintf(fp,"3  cbcModel->addHeuristic(&crossover);\n");
     988}
     989
     990// Copy constructor
     991CbcHeuristicCrossover::CbcHeuristicCrossover(const CbcHeuristicCrossover & rhs)
     992:
     993  CbcHeuristic(rhs),
     994  attempts_(rhs.attempts_),
     995  numberSolutions_(rhs.numberSolutions_),
     996  useNumber_(rhs.useNumber_)
     997{
     998  memcpy(random_,rhs.random_,10*sizeof(double));
     999}
     1000
     1001// Assignment operator
     1002CbcHeuristicCrossover &
     1003CbcHeuristicCrossover::operator=( const CbcHeuristicCrossover& rhs)
     1004{
     1005  if (this!=&rhs) {
     1006    CbcHeuristic::operator=(rhs);
     1007    useNumber_ = rhs.useNumber_;
     1008    attempts_ = rhs.attempts_;
     1009    numberSolutions_ = rhs.numberSolutions_;
     1010    memcpy(random_,rhs.random_,10*sizeof(double));
     1011  }
     1012  return *this;
     1013}
     1014
     1015// Resets stuff if model changes
     1016void
     1017CbcHeuristicCrossover::resetModel(CbcModel * model)
     1018{
     1019  CbcHeuristic::resetModel(model);
     1020}
     1021int
     1022CbcHeuristicCrossover::solution(double & solutionValue,
     1023                         double * betterSolution)
     1024{
     1025  if (when_==0)
     1026    return 0;
     1027  numCouldRun_++;
     1028  bool useBest=(numberSolutions_!=model_->getSolutionCount());
     1029  if (!useBest&&(when_%10)==1)
     1030    return 0;
     1031  numberSolutions_=model_->getSolutionCount();
     1032  OsiSolverInterface * continuousSolver = model_->continuousSolver();
     1033  int useNumber =CoinMin(model_->numberSavedSolutions(),useNumber_);
     1034  if (useNumber<2||!continuousSolver)
     1035    return 0;
     1036  // Fix later
     1037  if (!useBest)
     1038    abort();
     1039  numRuns_++;
     1040  double cutoff;
     1041  model_->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
     1042  double direction = model_->solver()->getObjSense();
     1043  cutoff *= direction;
     1044  cutoff = CoinMin(cutoff,solutionValue);
     1045  OsiSolverInterface * solver = cloneBut(2);
     1046  // But reset bounds
     1047  solver->setColLower(continuousSolver->getColLower());
     1048  solver->setColUpper(continuousSolver->getColUpper());
     1049  int numberColumns = solver->getNumCols();
     1050  // Fixed
     1051  double * fixed =new double [numberColumns];
     1052  for (int i=0;i<numberColumns;i++)
     1053    fixed[i]=-COIN_DBL_MAX;
     1054  int whichSolution[10];
     1055  for (int i=0;i<useNumber;i++)
     1056    whichSolution[i]=i;
     1057  for (int i=0;i<useNumber;i++) {
     1058    int k = whichSolution[i];
     1059    const double * solution = model_->savedSolution(k);
     1060    for (int j=0;j<numberColumns;j++) {
     1061      if (solver->isInteger(j)) {
     1062        if (fixed[j]==-COIN_DBL_MAX)
     1063          fixed[j]=floor(solution[j]+0.5);
     1064        else if (fabs(fixed[j]-solution[j])>1.0e-7)
     1065          fixed[j]=COIN_DBL_MAX;
     1066      }
     1067    }
     1068  }
     1069  const double * colLower = solver->getColLower();
     1070  for (int i=0;i<numberColumns;i++) {
     1071    if (solver->isInteger(i)) {
     1072      double value=fixed[i];
     1073      if (value!=COIN_DBL_MAX) {
     1074        if (when_<10) {
     1075          solver->setColLower(i,value);
     1076          solver->setColUpper(i,value);
     1077        } else if (value==colLower[i]) {
     1078          solver->setColUpper(i,value);
     1079        }
     1080      }
     1081    }
     1082  }
     1083  int returnCode = smallBranchAndBound(solver,numberNodes_,betterSolution,
     1084                                       solutionValue,
     1085                                       solutionValue,"CbcHeuristicCrossover");
     1086  if (returnCode<0)
     1087    returnCode=0; // returned on size
     1088  if ((returnCode&2)!=0) {
     1089    // could add cut
     1090    returnCode &= ~2;
     1091  }
     1092
     1093  delete solver;
     1094  return returnCode;
     1095}
     1096// update model
     1097void CbcHeuristicCrossover::setModel(CbcModel * model)
     1098{
     1099  model_ = model;
     1100  if (model) {
     1101    for (int i=0;i<10;i++)
     1102      random_[i]=model->randomNumberGenerator()->randomDouble();
     1103  }
     1104}
    8731105
    8741106 
Note: See TracChangeset for help on using the changeset viewer.