Changeset 917


Ignore:
Timestamp:
Apr 15, 2008 1:41:17 PM (11 years ago)
Author:
jpgoncal
Message:

Added version for fixing binary variables with generalized VUB constraints.

File:
1 edited

Legend:

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

    r916 r917  
    256256    // fix binary variables based on pseudo reduced cost
    257257    int numberAtBoundFixed = 0;
     258#if 0
     259    // This version uses generalized upper bounds. It doesn't seem to be working.
     260    if(binVarIndex_.size()) {
     261      int cnt = 0;
     262      for (int j=0; j<(int)binVarIndex_.size(); j++) {
     263        int iColumn1 = binVarIndex_[j];
     264        double value = newSolution[iColumn1];
     265        double maxPseudoReducedCost = 0.0;
     266        if(fabs(value)<=integerTolerance &&
     267           lower[iColumn1] != upper[iColumn1]) {
     268          //      std::cout<<"iColumn = "<<iColumn<<", value = "<<value<<std::endl;
     269          int iRow = vbRowIndex_[j];
     270          for (int k=rowStart[iRow];k<rowStart[iRow]+rowLength[iRow];k++) {
     271            int iColumn2 = column[k];
     272            if(iColumn1 != iColumn2) {
     273              double pseudoReducedCost = fabs(reducedCost[iColumn2] *
     274                                              elementByRow[iColumn2] /
     275                                              elementByRow[iColumn1]);
     276              if(pseudoReducedCost > maxPseudoReducedCost)
     277                maxPseudoReducedCost = pseudoReducedCost;
     278            }
     279          }
     280          //      std::cout<<", pseudoRedCost = "<<pseudoReducedCost<<std::endl;
     281          candidate[cnt].var = iColumn1;
     282          candidate[cnt++].pseudoRedCost = maxPseudoReducedCost;
     283        }
     284      }
     285      //      std::cout<<"candidates for rounding = "<<cnt<<std::endl;
     286      std::sort(candidate, candidate+cnt, compareBinaryVars);
     287      for (int i=0; i<cnt; i++) {
     288        int iColumn = candidate[i].var;
     289        if (numberAtBoundFixed < maxNumberAtBoundToFix) {
     290          columnFixed[numberAtBoundFixed] = iColumn;
     291          originalBound[numberAtBoundFixed] = upper[iColumn];
     292          fixedAtLowerBound[numberAtBoundFixed] = true;
     293          solver->setColUpper(iColumn, lower[iColumn]);
     294          numberAtBoundFixed++;
     295          if(numberAtBoundFixed == maxNumberAtBoundToFix)
     296            break;
     297        }
     298      }
     299    }
     300#else
     301// THIS ONLY USES variable upper bound constraints with 1 continuous variable
    258302    if(binVarIndex_.size()) {
    259303      int cnt = 0;
     
    306350      }
    307351    }
     352#endif
    308353    //    std::cout<<"numberAtBoundFixed = "<<numberAtBoundFixed<<std::endl;
    309354
     
    558603}
    559604
     605#if 0
     606// This version uses generalized upper bounds. It doesn't seem to be working.
     607
     608// Select candidate binary variables for fixing
     609void
     610CbcHeuristicDive::selectBinaryVariables()
     611{
     612  // Row copy
     613  const double * elementByRow = matrixByRow_.getElements();
     614  const int * column = matrixByRow_.getIndices();
     615  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     616  const int * rowLength = matrixByRow_.getVectorLengths();
     617
     618  const int numberRows = matrixByRow_.getNumRows();
     619  const int numberCols = matrixByRow_.getNumCols();
     620
     621  const double * lower = model_->solver()->getColLower();
     622  const double * upper = model_->solver()->getColUpper();
     623  const double * rowLower = model_->solver()->getRowLower();
     624  const double * rowUpper = model_->solver()->getRowUpper();
     625
     626  //  const char * integerType = model_->integerType();
     627 
     628
     629  //  const int numberIntegers = model_->numberIntegers();
     630  //  const int * integerVariable = model_->integerVariable();
     631  const double * objective = model_->solver()->getObjCoefficients();
     632
     633  // vector to store the row number of variable bound rows
     634  int* rowIndexes = new int [numberCols];
     635  memset(rowIndexes, -1, numberCols*sizeof(int));
     636
     637  for(int i=0; i<numberRows; i++) {
     638    int binVar = -1;
     639    int numIntegers = 0;
     640    int numContinuous = 0;
     641    for (int k=rowStart[i];k<rowStart[i]+rowLength[i];k++) {
     642      int iColumn = column[k];
     643      if(model_->solver()->isInteger(iColumn)) {
     644        numIntegers++;
     645        if(numIntegers > 1)
     646          break;
     647        if(lower[iColumn] == 0.0 && upper[iColumn] == 1.0 &&
     648           objective[iColumn] == 0.0)
     649          binVar = iColumn;
     650      }
     651    }
     652    if(numIntegers == 1 && binVar >= 0 &&
     653       ((rowLower[i] == 0.0 && rowUpper[i] > 1.0e30) ||
     654        (rowLower[i] < -1.0e30 && rowUpper[i] == 0))) {
     655      if(rowIndexes[binVar] == -1)
     656        rowIndexes[binVar] = i;
     657      else if(rowIndexes[binVar] >= 0)
     658        rowIndexes[binVar] = -2;
     659    }
     660  }
     661
     662  for(int j=0; j<numberCols; j++) {
     663    if(rowIndexes[j] >= 0) {
     664      binVarIndex_.push_back(j);
     665      vbRowIndex_.push_back(rowIndexes[j]);
     666    }
     667  }
     668
     669  std::cout<<"number vub Binary = "<<binVarIndex_.size()<<std::endl;
     670
     671  delete [] rowIndexes;
     672   
     673}
     674
     675#else
     676// THIS ONLY USES variable upper bound constraints with 1 continuous variable
     677
    560678// Select candidate binary variables for fixing
    561679void
     
    627745   
    628746}
     747#endif
Note: See TracChangeset for help on using the changeset viewer.