Changeset 1148


Ignore:
Timestamp:
Apr 19, 2009 10:08:30 AM (11 years ago)
Author:
forrest
Message:

changes to use heuristics with SOS etc

Location:
trunk/Cbc/src
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcBranchBase.hpp

    r1121 r1148  
    214214  inline int id() const
    215215  { return id_;}
     216 
     217  /** Set identifier (normally column number in matrix)
     218      but 1000000000 to 1100000000 means optional branching object
     219      i.e. code would work without it */
     220  inline void setId(int value)
     221  { id_ = value;}
     222 
     223  /** Return true if optional branching object
     224      i.e. code would work without it */
     225  inline bool optionalObject() const
     226  { return (id_ >= 1000000000 && id_ < 1100000000);}
    216227 
    217228  /// Get position in object_ list
  • trunk/Cbc/src/CbcBranchCut.cpp

    r1121 r1148  
    198198    way_=-1;      // Swap direction
    199199  }
     200  printf("CUT %s ",(way_==-1) ? "up" : "down");
     201  cut->print();
    200202  // See if cut just fixes variables
    201203  double lb = cut->lb();
     
    456458  int * sort = new int[numberColumns];
    457459  double * dsort = new double[numberColumns];
    458   int type = shallWe();
    459   assert (type);
    460   // Take clean first
    461   if (type==1) {
    462     for (i=0;i<numberIntegers;i++) {
    463       int iColumn = integerVariable[i];
    464       if (upper[iColumn]>lower[iColumn]) {
    465         if (!mark_||!mark_[iColumn]) {
    466           if(solution[iColumn]<lower[iColumn]+tolerance) {
    467             if (dj[iColumn]>djTolerance_) {
    468               dsort[nSort]=-dj[iColumn];
    469               sort[nSort++]=iColumn;
     460  if (djTolerance_!=-1.234567) {
     461    int type = shallWe();
     462    assert (type);
     463    // Take clean first
     464    if (type==1) {
     465      for (i=0;i<numberIntegers;i++) {
     466        int iColumn = integerVariable[i];
     467        if (upper[iColumn]>lower[iColumn]) {
     468          if (!mark_||!mark_[iColumn]) {
     469            if(solution[iColumn]<lower[iColumn]+tolerance) {
     470              if (dj[iColumn]>djTolerance_) {
     471                dsort[nSort]=-dj[iColumn];
     472                sort[nSort++]=iColumn;
     473              }
     474            } else if (solution[iColumn]>upper[iColumn]-tolerance) {
     475              if (dj[iColumn]<-djTolerance_) {
     476                dsort[nSort]=dj[iColumn];
     477                sort[nSort++]=iColumn;
     478              }
    470479            }
    471           } else if (solution[iColumn]>upper[iColumn]-tolerance) {
    472             if (dj[iColumn]<-djTolerance_) {
    473               dsort[nSort]=dj[iColumn];
     480          }
     481        } else {
     482          numberFixed++;
     483        }
     484      }
     485      // sort
     486      CoinSort_2(dsort,dsort+nSort,sort);
     487      nSort= CoinMin(nSort,wantedFixed-numberFixed);
     488    } else if (type<10) {
     489      int i;
     490      //const double * rowLower = solver->getRowLower();
     491      const double * rowUpper = solver->getRowUpper();
     492      // Row copy
     493      const double * elementByRow = matrixByRow_.getElements();
     494      const int * column = matrixByRow_.getIndices();
     495      const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     496      const int * rowLength = matrixByRow_.getVectorLengths();
     497      const double * columnLower = solver->getColLower();
     498      const double * columnUpper = solver->getColUpper();
     499      const double * solution = solver->getColSolution();
     500      int numberColumns = solver->getNumCols();
     501      int numberRows = solver->getNumRows();
     502      for (i=0;i<numberColumns;i++) {
     503        sort[i]=i;
     504        if (columnLower[i]!=columnUpper[i]){
     505          dsort[i]=1.0e100;
     506        } else {
     507          dsort[i]=1.0e50;
     508          numberFixed++;
     509        }
     510      }
     511      for (i=0;i<numberRows;i++) {
     512        double rhsValue = rowUpper[i];
     513        bool oneRow=true;
     514        // check elements
     515        int numberUnsatisfied=0;
     516        for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     517          int iColumn = column[j];
     518          double value = elementByRow[j];
     519          double solValue = solution[iColumn];
     520          if (columnLower[iColumn]!=columnUpper[iColumn]) {
     521            if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
     522              numberUnsatisfied++;
     523            if (value!=1.0) {
     524              oneRow=false;
     525              break;
     526            }
     527          } else {
     528            rhsValue -= value*floor(solValue+0.5);
     529          }
     530        }
     531        if (oneRow&&rhsValue<=1.0+tolerance) {
     532          if (!numberUnsatisfied) {
     533            for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     534              int iColumn = column[j];
     535              if (dsort[iColumn]>1.0e50){
     536                dsort[iColumn]=0;
     537                nSort++;
     538              }
     539            }
     540          }
     541        }
     542      }
     543      // sort
     544      CoinSort_2(dsort,dsort+numberColumns,sort);
     545    } else {
     546      // new way
     547      for (i=0;i<numberIntegers;i++) {
     548        int iColumn = integerVariable[i];
     549        if (upper[iColumn]>lower[iColumn]) {
     550          if (!mark_||!mark_[iColumn]) {
     551            double distanceDown=solution[iColumn]-lower[iColumn];
     552            double distanceUp=upper[iColumn]-solution[iColumn];
     553            double distance = CoinMin(distanceDown,distanceUp);
     554            if (distance>0.001&&distance<0.5) {
     555              dsort[nSort]=distance;
    474556              sort[nSort++]=iColumn;
    475557            }
    476558          }
    477559        }
    478       } else {
    479         numberFixed++;
    480       }
    481     }
    482     // sort
    483     CoinSort_2(dsort,dsort+nSort,sort);
    484     nSort= CoinMin(nSort,wantedFixed-numberFixed);
    485   } else if (type<10) {
    486     int i;
    487     //const double * rowLower = solver->getRowLower();
    488     const double * rowUpper = solver->getRowUpper();
    489     // Row copy
    490     const double * elementByRow = matrixByRow_.getElements();
     560      }
     561      // sort
     562      CoinSort_2(dsort,dsort+nSort,sort);
     563      int n=0;
     564      double sum=0.0;
     565      for (int k=0;k<nSort;k++) {
     566        sum += dsort[k];
     567        if (sum<=djTolerance_)
     568          n=k;
     569        else
     570          break;
     571      }
     572      nSort = CoinMin(n,numberClean_/1000000);
     573    }
     574  } else {
     575#define FIX_IF_LESS -0.1
     576    // 3 in same row and sum <FIX_IF_LESS?
     577    int numberRows = matrixByRow_.getNumRows();
     578    const double * solution = model_->testSolution();
    491579    const int * column = matrixByRow_.getIndices();
    492580    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
    493581    const int * rowLength = matrixByRow_.getVectorLengths();
    494     const double * columnLower = solver->getColLower();
    495     const double * columnUpper = solver->getColUpper();
    496     const double * solution = solver->getColSolution();
    497     int numberColumns = solver->getNumCols();
    498     int numberRows = solver->getNumRows();
    499     for (i=0;i<numberColumns;i++) {
    500       sort[i]=i;
    501       if (columnLower[i]!=columnUpper[i]){
    502         dsort[i]=1.0e100;
    503       } else {
    504         dsort[i]=1.0e50;
    505         numberFixed++;
    506       }
    507     }
    508     for (i=0;i<numberRows;i++) {
    509       double rhsValue = rowUpper[i];
    510       bool oneRow=true;
    511       // check elements
     582    double bestSum=1.0;
     583    int nBest=-1;
     584    int kRow=-1;
     585    OsiSolverInterface * solver = model_->solver();
     586    for (int i=0;i<numberRows;i++) {
    512587      int numberUnsatisfied=0;
     588      double sum=0.0;
    513589      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
    514590        int iColumn = column[j];
    515         double value = elementByRow[j];
     591        if (solver->isInteger(iColumn)) {
     592          double solValue = solution[iColumn];
     593          if (solValue>1.0e-5&&solValue<FIX_IF_LESS) {
     594            numberUnsatisfied++;
     595            sum += solValue;
     596          }
     597        }
     598      }
     599      if (numberUnsatisfied>=3&&sum<FIX_IF_LESS) {
     600        // possible
     601        if (numberUnsatisfied>nBest||
     602            numberUnsatisfied==nBest&&sum<bestSum) {
     603          nBest=numberUnsatisfied;
     604          bestSum=sum;
     605          kRow=i;
     606        }
     607      }
     608    }
     609    assert (nBest>0);
     610    for (int j=rowStart[kRow];j<rowStart[kRow]+rowLength[kRow];j++) {
     611      int iColumn = column[j];
     612      if (solver->isInteger(iColumn)) {
    516613        double solValue = solution[iColumn];
    517         if (columnLower[iColumn]!=columnUpper[iColumn]) {
    518           if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
    519             numberUnsatisfied++;
    520           if (value!=1.0) {
    521             oneRow=false;
    522             break;
    523           }
    524         } else {
    525           rhsValue -= value*floor(solValue+0.5);
    526         }
    527       }
    528       if (oneRow&&rhsValue<=1.0+tolerance) {
    529         if (!numberUnsatisfied) {
    530           for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
    531             int iColumn = column[j];
    532             if (dsort[iColumn]>1.0e50){
    533               dsort[iColumn]=0;
    534               nSort++;
    535             }
    536           }
    537         }
    538       }
    539     }
    540     // sort
    541     CoinSort_2(dsort,dsort+numberColumns,sort);
    542   } else {
    543     // new way
    544     for (i=0;i<numberIntegers;i++) {
    545       int iColumn = integerVariable[i];
    546       if (upper[iColumn]>lower[iColumn]) {
    547         if (!mark_||!mark_[iColumn]) {
    548           double distanceDown=solution[iColumn]-lower[iColumn];
    549           double distanceUp=upper[iColumn]-solution[iColumn];
    550           double distance = CoinMin(distanceDown,distanceUp);
    551           if (distance>0.001&&distance<0.5) {
    552             dsort[nSort]=distance;
    553             sort[nSort++]=iColumn;
    554           }
    555         }
    556       }
    557     }
    558     // sort
    559     CoinSort_2(dsort,dsort+nSort,sort);
    560     int n=0;
    561     double sum=0.0;
    562     for (int k=0;k<nSort;k++) {
    563       sum += dsort[k];
    564       if (sum<=djTolerance_)
    565         n=k;
    566       else
    567         break;
    568     }
    569     nSort = CoinMin(n,numberClean_/1000000);
     614        if (solValue>1.0e-5&&solValue<FIX_IF_LESS) {
     615          sort[nSort++]=iColumn;
     616        }
     617      }
     618    }
    570619  }
    571620  OsiRowCut down;
     
    779828      return 0.0;
    780829  }
    781   if (!shallWe())
    782     return 0.0;
    783   else
    784     return 1.0e20;
     830  if (djTolerance_!=-1.234567) {
     831    if (!shallWe())
     832      return 0.0;
     833    else
     834      return 1.0e20;
     835  } else {
     836    // See if 3 in same row and sum <FIX_IF_LESS?
     837    int numberRows = matrixByRow_.getNumRows();
     838    const double * solution = model_->testSolution();
     839    const int * column = matrixByRow_.getIndices();
     840    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     841    const int * rowLength = matrixByRow_.getVectorLengths();
     842    double bestSum=1.0;
     843    int nBest=-1;
     844    OsiSolverInterface * solver = model_->solver();
     845    for (int i=0;i<numberRows;i++) {
     846      int numberUnsatisfied=0;
     847      double sum=0.0;
     848      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     849        int iColumn = column[j];
     850        if (solver->isInteger(iColumn)) {
     851          double solValue = solution[iColumn];
     852          if (solValue>1.0e-5&&solValue<FIX_IF_LESS) {
     853            numberUnsatisfied++;
     854            sum += solValue;
     855          }
     856        }
     857      }
     858      if (numberUnsatisfied>=3&&sum<FIX_IF_LESS) {
     859        // possible
     860        if (numberUnsatisfied>nBest||
     861            numberUnsatisfied==nBest&&sum<bestSum) {
     862          nBest=numberUnsatisfied;
     863          bestSum=sum;
     864        }
     865      }
     866    }
     867    if (nBest>0)
     868      return 1.0e20;
     869    else
     870      return 0.0;
     871  }
     872}
     873// Redoes data when sequence numbers change
     874void
     875CbcBranchToFixLots::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)
     876{
     877  model_=model;
     878  if (mark_) {
     879    OsiSolverInterface * solver = model_->solver();
     880    int numberColumnsNow = solver->getNumCols();
     881    char * temp = new char[numberColumnsNow];
     882    memset(temp,0,numberColumnsNow);
     883    for (int i=0;i<numberColumns;i++) {
     884      int j = originalColumns[i];
     885      temp[i]=mark_[j];
     886    }
     887    delete [] mark_;
     888    mark_=temp;
     889  }
     890  OsiSolverInterface * solver = model_->solver();
     891  matrixByRow_ = *solver->getMatrixByRow();
    785892}
    786893
  • trunk/Cbc/src/CbcBranchCut.hpp

    r912 r1148  
    235235  /// Infeasibility - large is 0.5
    236236  virtual double infeasibility(int & preferredWay) const;
     237  /** \brief Return true if object can take part in normal heuristics
     238  */
     239  virtual bool canDoHeuristics() const
     240  {return true;}
    237241
    238242  using CbcObject::createBranch ;
    239243  /// Creates a branching object
    240244  virtual CbcBranchingObject * createBranch(int way);
     245  /// Redoes data when sequence numbers change
     246  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
    241247
    242248
  • trunk/Cbc/src/CbcHeuristic.cpp

    r1132 r1148  
    22532253    if (model_->numberIntegers()!=
    22542254        model_->numberObjects()&&(model_->numberObjects()||
    2255                                   (model_->specialOptions()&1024)==0))
    2256       setWhen(0);
     2255                                  (model_->specialOptions()&1024)==0)) {
     2256      int numberOdd=0;
     2257      for (int i=0;i<model_->numberObjects();i++) {
     2258        if (!model_->object(i)->canDoHeuristics())
     2259          numberOdd++;
     2260      }
     2261      if (numberOdd)
     2262        setWhen(0);
     2263    }
    22572264  }
    22582265#ifdef NEW_ROUNDING
  • trunk/Cbc/src/CbcHeuristicDive.cpp

    r1121 r1148  
    636636    if (model_->numberIntegers()!=
    637637        model_->numberObjects()&&(model_->numberObjects()||
    638                                   (model_->specialOptions()&1024)==0))
    639       setWhen(0);
     638                                  (model_->specialOptions()&1024)==0)) {
     639      int numberOdd=0;
     640      for (int i=0;i<model_->numberObjects();i++) {
     641        if (!model_->object(i)->canDoHeuristics())
     642          numberOdd++;
     643      }
     644      if (numberOdd)
     645        setWhen(0);
     646    }
    640647  }
    641648
  • trunk/Cbc/src/CbcHeuristicGreedy.cpp

    r961 r1148  
    375375    if (model_->numberIntegers()!=
    376376        model_->numberObjects()&&(model_->numberObjects()||
    377                                   (model_->specialOptions()&1024)==0))
    378       setWhen(0);
     377                                  (model_->specialOptions()&1024)==0)) {
     378      int numberOdd=0;
     379      for (int i=0;i<model_->numberObjects();i++) {
     380        if (!model_->object(i)->canDoHeuristics())
     381          numberOdd++;
     382      }
     383      if (numberOdd)
     384        setWhen(0);
     385    }
    379386    // Only works if costs positive, coefficients positive and all rows G
    380387    OsiSolverInterface * solver = model_->solver();
  • trunk/Cbc/src/CbcNode.cpp

    r1133 r1148  
    24102410  }
    24112411  int numberObjects = model->numberObjects();
    2412   bool checkFeasibility = numberObjects>model->numberIntegers();
     2412  bool checkFeasibility = false;
     2413  if (numberObjects>model->numberIntegers()) {
     2414    for (int i=model->numberIntegers();i<numberObjects;i++) {
     2415      OsiObject * object = model->modifiableObject(i);
     2416      CbcObject * obj = dynamic_cast <CbcObject *>(object) ;
     2417      if (!obj || !obj->optionalObject()) {
     2418        checkFeasibility=true;
     2419        break;
     2420      }
     2421    }
     2422  }
    24132423  if ((model->specialOptions()&128)!=0)
    24142424    checkFeasibility=false; // allow
     
    30843094            CbcSOS * sosObject =
    30853095              dynamic_cast <CbcSOS *>(object) ;
    3086             assert (sosObject);
    3087             gotDown=false;
    3088             numberThisDown = sosObject->numberTimesDown();
    3089             if (numberThisDown>=numberBeforeTrust)
     3096            if (sosObject) {
     3097              gotDown=false;
     3098              numberThisDown = sosObject->numberTimesDown();
     3099              if (numberThisDown>=numberBeforeTrust)
     3100                gotDown=true;
     3101              gotUp=false;
     3102              numberThisUp = sosObject->numberTimesUp();
     3103              if (numberThisUp>=numberBeforeTrust)
     3104                gotUp=true;
     3105            } else {
    30903106              gotDown=true;
    3091             gotUp=false;
    3092             numberThisUp = sosObject->numberTimesUp();
    3093             if (numberThisUp>=numberBeforeTrust)
     3107              numberThisDown=999999;
     3108              downGuess=1.0e20;
    30943109              gotUp=true;
     3110              numberThisUp=999999;
     3111              upGuess=1.0e20;
     3112              numberPassesLeft=0;
     3113            }
    30953114          }
    30963115          // Increase estimated degradation to solution
     
    32923311    int saveLimit=0;
    32933312    solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
     3313    if (!numberPassesLeft)
     3314      skipAll=1;
    32943315    if (!skipAll) {
    32953316      ws = solver->getWarmStart();
Note: See TracChangeset for help on using the changeset viewer.