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

changes to use heuristics with SOS etc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.