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/CbcHeuristicDive.cpp

    r1121 r1271  
     1/* $Id: CbcHeuristicDive.cpp 1240 2009-10-02 18:41:44Z forrest $ */
    12// Copyright (C) 2008, International Business Machines
    23// Corporation and others.  All Rights Reserved.
     
    89#include "CbcHeuristicDive.hpp"
    910#include "CbcStrategy.hpp"
     11#include "OsiAuxInfo.hpp"
    1012#include  "CoinTime.hpp"
    1113
     
    2426  downLocks_ =NULL;
    2527  upLocks_ = NULL;
     28  downArray_ =NULL;
     29  upArray_ = NULL;
    2630  percentageToFix_ = 0.2;
    2731  maxIterations_ = 100;
     
    2933  maxSimplexIterationsAtRoot_ = 1000000;
    3034  maxTime_ = 600;
     35  whereFrom_=255-2-16+256;
    3136}
    3237
     
    3742  downLocks_ =NULL;
    3843  upLocks_ = NULL;
     44  downArray_ =NULL;
     45  upArray_ = NULL;
    3946  // Get a copy of original matrix
    4047  assert(model.solver());
     
    5158  maxSimplexIterationsAtRoot_ = 1000000;
    5259  maxTime_ = 600;
     60  whereFrom_=255-2-16+256;
    5361}
    5462
     
    5866  delete [] downLocks_;
    5967  delete [] upLocks_;
     68  assert (!downArray_);
    6069}
    6170
     
    7483  else
    7584    fprintf(fp,"4  %s.setMaxIterations(%d);\n",heuristic,maxIterations_);
    76   if (maxSimplexIterations_!=100)
    77     fprintf(fp,"3  %s.setMaxIterations(%d);\n",heuristic,maxSimplexIterations_);
     85  if (maxSimplexIterations_!=10000)
     86    fprintf(fp,"3  %s.setMaxSimplexIterations(%d);\n",heuristic,maxSimplexIterations_);
    7887  else
    79     fprintf(fp,"4  %s.setMaxIterations(%d);\n",heuristic,maxSimplexIterations_);
     88    fprintf(fp,"4  %s.setMaxSimplexIterations(%d);\n",heuristic,maxSimplexIterations_);
    8089  if (maxTime_!=600)
    8190    fprintf(fp,"3  %s.setMaxTime(%.2f);\n",heuristic,maxTime_);
     
    96105  maxTime_(rhs.maxTime_)
    97106{
     107  downArray_ =NULL;
     108  upArray_ = NULL;
    98109  if (rhs.downLocks_) {
    99110    int numberIntegers = model_->numberIntegers();
     
    169180}
    170181
    171 struct PseudoReducedCost {
    172   int var;
    173   double pseudoRedCost;
    174 };
    175 
    176182inline bool compareBinaryVars(const PseudoReducedCost obj1,
    177183                              const PseudoReducedCost obj2)
     
    214220    : maxSimplexIterationsAtRoot_;
    215221
    216   OsiSolverInterface * solver = model_->solver()->clone();
     222  OsiSolverInterface * solver = cloneBut(6); // was model_->solver()->clone();
     223# ifdef COIN_HAS_CLP
     224  OsiClpSolverInterface * clpSolver
     225    = dynamic_cast<OsiClpSolverInterface *> (solver);
     226  if (clpSolver) {
     227    // say give up easily
     228    ClpSimplex * clpSimplex = clpSolver->getModelPtr();
     229    clpSimplex->setMoreSpecialOptions(clpSimplex->moreSpecialOptions()|64);
     230  }
     231# endif
    217232  const double * lower = solver->getColLower();
    218233  const double * upper = solver->getColUpper();
     
    237252  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
    238253  const int * columnLength = matrix_.getVectorLengths();
     254#ifdef DIVE_FIX_BINARY_VARIABLES
    239255  // Row copy
    240   //const double * elementByRow = matrixByRow_.getElements();
    241   //const int * column = matrixByRow_.getIndices();
    242   //const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
    243   //const int * rowLength = matrixByRow_.getVectorLengths();
     256  const double * elementByRow = matrixByRow_.getElements();
     257  const int * column = matrixByRow_.getIndices();
     258  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     259  const int * rowLength = matrixByRow_.getVectorLengths();
     260#endif
    244261
    245262  // Get solution array for heuristic solution
     
    252269  double* originalBound = new double [numberIntegers];
    253270  bool * fixedAtLowerBound = new bool [numberIntegers];
    254   PseudoReducedCost * candidate = NULL;
    255   if(binVarIndex_.size())
    256     candidate = new PseudoReducedCost [binVarIndex_.size()];
    257 
    258   const int maxNumberAtBoundToFix = static_cast<int> (floor(percentageToFix_ * numberIntegers));
     271  PseudoReducedCost * candidate = new PseudoReducedCost [numberIntegers];
     272  double * random = new double [numberIntegers];
     273
     274  int maxNumberAtBoundToFix = static_cast<int> (floor(percentageToFix_ * numberIntegers));
    259275
    260276  // count how many fractional variables
    261277  int numberFractionalVariables = 0;
    262278  for (int i=0; i<numberIntegers; i++) {
     279    random[i]=randomNumberGenerator_.randomDouble()+0.3;
    263280    int iColumn = integerVariable[i];
    264281    double value=newSolution[iColumn];
     
    268285  }
    269286
    270 #ifdef DIVE_FIX_BINARY_VARIABLES
    271   const double* reducedCost = solver->getReducedCost();
    272 #endif
     287  const double* reducedCost = NULL;
     288  // See if not NLP
     289  if(model_->solverCharacteristics()->reducedCostsAccurate())
     290    reducedCost = solver->getReducedCost();
    273291
    274292  int iteration = 0;
    275293  while(numberFractionalVariables) {
    276294    iteration++;
     295   
     296    // initialize any data
     297    initializeData();
    277298
    278299    // select a fractional variable to bound
     
    353374    if(binVarIndex_.size()) {
    354375      int cnt = 0;
    355       for (int j=0; j<(int)binVarIndex_.size(); j++) {
     376      int n = static_cast<int>(binVarIndex_.size());
     377      for (int j=0; j<n; j++) {
    356378        int iColumn1 = binVarIndex_[j];
    357379        double value = newSolution[iColumn1];
    358         double maxPseudoReducedCost = 0.0;
    359380        if(fabs(value)<=integerTolerance &&
    360381           lower[iColumn1] != upper[iColumn1]) {
     382          double maxPseudoReducedCost = 0.0;
    361383#ifdef DIVE_DEBUG
    362384          std::cout<<"iColumn1 = "<<iColumn1<<", value = "<<value<<std::endl;
    363385#endif
    364386          int iRow = vbRowIndex_[j];
     387          double chosenValue=0.0;
    365388          for (int k=rowStart[iRow];k<rowStart[iRow]+rowLength[iRow];k++) {
    366389            int iColumn2 = column[k];
     
    370393            if(iColumn1 != iColumn2) {
    371394              double pseudoReducedCost = fabs(reducedCost[iColumn2] *
    372                                               elementByRow[iColumn2] /
    373                                               elementByRow[iColumn1]);
    374 #ifdef DIVE_DEBUG
     395                                              elementByRow[k]);
     396#ifdef DIVE_DEBUG
     397              int k2;
     398              for (k2=rowStart[iRow];k2<rowStart[iRow]+rowLength[iRow];k2++) {
     399                if (column[k2]==iColumn1)
     400                  break;
     401              }
    375402              std::cout<<"reducedCost["<<iColumn2<<"] = "
    376403                       <<reducedCost[iColumn2]
    377                        <<", elementByRow["<<iColumn2<<"] = "<<elementByRow[iColumn2]
    378                        <<", elementByRow["<<iColumn1<<"] = "<<elementByRow[iColumn1]
     404                       <<", elementByRow["<<iColumn2<<"] = "<<elementByRow[k]
     405                       <<", elementByRow["<<iColumn1<<"] = "<<elementByRow[k2]
    379406                       <<", pseudoRedCost = "<<pseudoReducedCost
    380407                       <<std::endl;
     
    382409              if(pseudoReducedCost > maxPseudoReducedCost)
    383410                maxPseudoReducedCost = pseudoReducedCost;
     411            } else {
     412              // save value
     413              chosenValue = fabs(elementByRow[k]);
    384414            }
    385415          }
     416          assert (chosenValue);
     417          maxPseudoReducedCost /= chosenValue;
    386418#ifdef DIVE_DEBUG
    387419          std::cout<<", maxPseudoRedCost = "<<maxPseudoReducedCost<<std::endl;
     
    411443
    412444    // fix other integer variables that are at their bounds
    413     for (int i=0; i<numberIntegers; i++) {
    414       int iColumn = integerVariable[i];
    415       double value=newSolution[iColumn];
    416       if(fabs(floor(value+0.5)-value)<=integerTolerance &&
    417          numberAtBoundFixed < maxNumberAtBoundToFix) {
    418         // fix the variable at one of its bounds
    419         if (fabs(lower[iColumn]-value)<=integerTolerance &&
    420             lower[iColumn] != upper[iColumn]) {
    421           columnFixed[numberAtBoundFixed] = iColumn;
    422           originalBound[numberAtBoundFixed] = upper[iColumn];
    423           fixedAtLowerBound[numberAtBoundFixed] = true;
    424           solver->setColUpper(iColumn, lower[iColumn]);
    425           numberAtBoundFixed++;
    426         }
    427         else if(fabs(upper[iColumn]-value)<=integerTolerance &&
    428             lower[iColumn] != upper[iColumn]) {
    429           columnFixed[numberAtBoundFixed] = iColumn;
    430           originalBound[numberAtBoundFixed] = lower[iColumn];
    431           fixedAtLowerBound[numberAtBoundFixed] = false;
    432           solver->setColLower(iColumn, upper[iColumn]);
    433           numberAtBoundFixed++;
    434         }
    435         if(numberAtBoundFixed == maxNumberAtBoundToFix)
    436           break;
     445    int cnt=0;
     446#ifdef GAP
     447    double gap=1.0e30;
     448#endif
     449    if (reducedCost&&true) {
     450#if 1
     451      cnt=fixOtherVariables(solver,solution,candidate,random);
     452#else
     453#ifdef GAP
     454      double cutoff = model_->getCutoff() ;
     455      if (cutoff<1.0e20&&false) {
     456        double direction = solver->getObjSense() ;
     457        gap = cutoff - solver->getObjValue()*direction ;
     458        gap *= 0.1; // Fix more if plausible
     459        double tolerance;
     460        solver->getDblParam(OsiDualTolerance,tolerance) ;
     461        if (gap<=0.0)
     462          gap = tolerance;
     463        gap += 100.0*tolerance;
     464      }
     465      int nOverGap=0;
     466#endif
     467      int numberFree=0;
     468      int numberFixed=0;
     469      for (int i=0; i<numberIntegers; i++) {
     470        int iColumn = integerVariable[i];
     471        if (upper[iColumn]>lower[iColumn]) {
     472          numberFree++;
     473          double value=newSolution[iColumn];
     474          if(fabs(floor(value+0.5)-value)<=integerTolerance) {
     475            candidate[cnt].var = iColumn;
     476            candidate[cnt++].pseudoRedCost =
     477              fabs(reducedCost[iColumn]*random[i]);
     478#ifdef GAP
     479            if (fabs(reducedCost[iColumn])>gap)
     480              nOverGap++;
     481#endif
     482          }
     483        } else {
     484          numberFixed++;
     485        }
     486      }
     487#ifdef GAP
     488      int nLeft = maxNumberAtBoundToFix-numberAtBoundFixed;
     489#ifdef CLP_INVESTIGATE
     490      printf("cutoff %g obj %g nover %d - %d free, %d fixed\n",
     491             cutoff,solver->getObjValue(),nOverGap,numberFree,numberFixed);
     492#endif
     493      if (nOverGap>nLeft&&true) {
     494        nOverGap = CoinMin(nOverGap,nLeft+maxNumberAtBoundToFix/2);
     495        maxNumberAtBoundToFix += nOverGap-nLeft;
     496      }
     497#else
     498#ifdef CLP_INVESTIGATE
     499      printf("cutoff %g obj %g - %d free, %d fixed\n",
     500             model_->getCutoff(),solver->getObjValue(),numberFree,numberFixed);
     501#endif
     502#endif
     503#endif
     504    } else {
     505      for (int i=0; i<numberIntegers; i++) {
     506        int iColumn = integerVariable[i];
     507        if (upper[iColumn]>lower[iColumn]) {
     508          double value=newSolution[iColumn];
     509          if(fabs(floor(value+0.5)-value)<=integerTolerance) {
     510            candidate[cnt].var = iColumn;
     511            candidate[cnt++].pseudoRedCost = numberIntegers-i;
     512          }
     513        }
     514      }
     515    }
     516    std::sort(candidate, candidate+cnt, compareBinaryVars);
     517    for (int i=0; i<cnt; i++) {
     518      int iColumn = candidate[i].var;
     519      if (upper[iColumn]>lower[iColumn]) {
     520        double value=newSolution[iColumn];
     521        if(fabs(floor(value+0.5)-value)<=integerTolerance &&
     522           numberAtBoundFixed < maxNumberAtBoundToFix) {
     523          // fix the variable at one of its bounds
     524          if (fabs(lower[iColumn]-value)<=integerTolerance) {
     525            columnFixed[numberAtBoundFixed] = iColumn;
     526            originalBound[numberAtBoundFixed] = upper[iColumn];
     527            fixedAtLowerBound[numberAtBoundFixed] = true;
     528            solver->setColUpper(iColumn, lower[iColumn]);
     529            numberAtBoundFixed++;
     530          }
     531          else if(fabs(upper[iColumn]-value)<=integerTolerance) {
     532            columnFixed[numberAtBoundFixed] = iColumn;
     533            originalBound[numberAtBoundFixed] = lower[iColumn];
     534            fixedAtLowerBound[numberAtBoundFixed] = false;
     535            solver->setColLower(iColumn, upper[iColumn]);
     536            numberAtBoundFixed++;
     537          }
     538          if(numberAtBoundFixed == maxNumberAtBoundToFix)
     539            break;
     540        }
    437541      }
    438542    }
     
    461565      solver->resolve();
    462566      model_->setSpecialOptions(saveModelOptions);
    463 
     567      if(!solver->isAbandoned()) {
     568        numberSimplexIterations+=solver->getIterationCount();
     569      } else {
     570        numberSimplexIterations=maxSimplexIterations+1;
     571        break;
     572      }
     573     
    464574      if(!solver->isProvenOptimal()) {
    465575        if(numberAtBoundFixed > 0) {
     
    514624    }
    515625
    516     numberSimplexIterations+=solver->getIterationCount();
    517626    if(numberSimplexIterations > maxSimplexIterations) {
    518627#ifdef DIVE_DEBUG
     
    625734  delete [] candidate;
    626735  delete [] rowActivity;
     736  delete [] random;
     737  delete [] downArray_;
     738  downArray_=NULL;
     739  delete [] upArray_;
     740  upArray_=NULL;
    627741  delete solver;
    628742  return returnCode;
     
    633747CbcHeuristicDive::validate()
    634748{
    635   if (model_&&when()<10) {
     749  if (model_&&(when()%100)<10) {
    636750    if (model_->numberIntegers()!=
    637751        model_->numberObjects()&&(model_->numberObjects()||
    638                                   (model_->specialOptions()&1024)==0))
    639       setWhen(0);
     752                                  (model_->specialOptions()&1024)==0)) {
     753      int numberOdd=0;
     754      for (int i=0;i<model_->numberObjects();i++) {
     755        if (!model_->object(i)->canDoHeuristics())
     756          numberOdd++;
     757      }
     758      if (numberOdd)
     759        setWhen(0);
     760    }
    640761  }
    641762
     
    795916
    796917{
    797   return 0; // temp
    798 #if 0
    799   if(!solverCharacteristics_->reducedCostsAccurate())
     918  //return 0; // temp
     919#if 1
     920  if(!model_->solverCharacteristics()->reducedCostsAccurate())
    800921    return 0; //NLP
    801922#endif
    802923  double cutoff = model_->getCutoff() ;
     924  if (cutoff>1.0e20)
     925    return 0;
    803926#ifdef DIVE_DEBUG
    804927  std::cout<<"cutoff = "<<cutoff<<std::endl;
     
    806929  double direction = solver->getObjSense() ;
    807930  double gap = cutoff - solver->getObjValue()*direction ;
     931  gap *= 0.5; // Fix more
    808932  double tolerance;
    809933  solver->getDblParam(OsiDualTolerance,tolerance) ;
     
    875999  return numberFixed;
    8761000}
     1001// Fix other variables at bounds
     1002int
     1003CbcHeuristicDive::fixOtherVariables(OsiSolverInterface * solver,
     1004                                    const double * solution,
     1005                                    PseudoReducedCost * candidate,
     1006                                    const double * random)
     1007{
     1008  const double * lower = solver->getColLower();
     1009  const double * upper = solver->getColUpper();
     1010  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
     1011  double primalTolerance;
     1012  solver->getDblParam(OsiPrimalTolerance,primalTolerance);
     1013
     1014  int numberIntegers = model_->numberIntegers();
     1015  const int * integerVariable = model_->integerVariable();
     1016  const double* reducedCost = solver->getReducedCost();
     1017  // fix other integer variables that are at their bounds
     1018  int cnt=0;
     1019#ifdef GAP
     1020  double direction = solver->getObjSense(); // 1 for min, -1 for max
     1021  double gap=1.0e30;
     1022#endif
     1023#ifdef GAP
     1024  double cutoff = model_->getCutoff() ;
     1025  if (cutoff<1.0e20&&false) {
     1026    double direction = solver->getObjSense() ;
     1027    gap = cutoff - solver->getObjValue()*direction ;
     1028    gap *= 0.1; // Fix more if plausible
     1029    double tolerance;
     1030    solver->getDblParam(OsiDualTolerance,tolerance) ;
     1031    if (gap<=0.0)
     1032      gap = tolerance;
     1033    gap += 100.0*tolerance;
     1034  }
     1035  int nOverGap=0;
     1036#endif
     1037  int numberFree=0;
     1038  int numberFixedAlready=0;
     1039  for (int i=0; i<numberIntegers; i++) {
     1040    int iColumn = integerVariable[i];
     1041    if (upper[iColumn]>lower[iColumn]) {
     1042      numberFree++;
     1043      double value=solution[iColumn];
     1044      if(fabs(floor(value+0.5)-value)<=integerTolerance) {
     1045        candidate[cnt].var = iColumn;
     1046        candidate[cnt++].pseudoRedCost =
     1047          fabs(reducedCost[iColumn]*random[i]);
     1048#ifdef GAP
     1049        if (fabs(reducedCost[iColumn])>gap)
     1050          nOverGap++;
     1051#endif
     1052      }
     1053    } else {
     1054      numberFixedAlready++;
     1055    }
     1056  }
     1057#ifdef GAP
     1058  int nLeft = maxNumberToFix-numberFixedAlready;
     1059#ifdef CLP_INVESTIGATE
     1060  printf("cutoff %g obj %g nover %d - %d free, %d fixed\n",
     1061         cutoff,solver->getObjValue(),nOverGap,numberFree,
     1062         numberFixedAlready);
     1063#endif
     1064  if (nOverGap>nLeft&&true) {
     1065    nOverGap = CoinMin(nOverGap,nLeft+maxNumberToFix/2);
     1066    maxNumberToFix += nOverGap-nLeft;
     1067  }
     1068#else
     1069#ifdef CLP_INVESTIGATE
     1070  printf("cutoff %g obj %g - %d free, %d fixed\n",
     1071         model_->getCutoff(),solver->getObjValue(),numberFree,
     1072         numberFixedAlready);
     1073#endif
     1074#endif
     1075  return cnt;
     1076}
Note: See TracChangeset for help on using the changeset viewer.