Changeset 916


Ignore:
Timestamp:
Apr 15, 2008 12:33:14 PM (11 years ago)
Author:
jpgoncal
Message:

Added fixing of binary variables in variable upper bound constraints.

Location:
trunk/Cbc/src
Files:
2 edited

Legend:

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

    r912 r916  
    99#include "CbcStrategy.hpp"
    1010#include  "CoinTime.hpp"
     11
     12//#define DIVE_FIX_BINARY_VARIABLES
    1113
    1214// Default Constructor
     
    3436  if (matrix) {
    3537    matrix_ = *matrix;
     38    matrixByRow_ = *model.solver()->getMatrixByRow();
    3639    validate();
    3740  }
     
    7376  CbcHeuristic(rhs),
    7477  matrix_(rhs.matrix_),
     78  matrixByRow_(rhs.matrixByRow_),
    7579  percentageToFix_(rhs.percentageToFix_),
    7680  maxIterations_(rhs.maxIterations_),
     
    9498    CbcHeuristic::operator=(rhs);
    9599    matrix_ = rhs.matrix_;
     100    matrixByRow_ = rhs.matrixByRow_;
    96101    percentageToFix_ = rhs.percentageToFix_;
    97102    maxIterations_ = rhs.maxIterations_;
     
    122127  if (matrix) {
    123128    matrix_ = *matrix;
     129    matrixByRow_ = *model->solver()->getMatrixByRow();
    124130    validate();
    125131  }
     
    135141  if (matrix) {
    136142    matrix_ = *matrix;
     143    matrixByRow_ = *model->solver()->getMatrixByRow();
    137144    // make sure model okay for heuristic
    138145    validate();
     
    145152}
    146153
     154struct PseudoReducedCost {
     155  int var;
     156  double pseudoRedCost;
     157};
     158
     159inline bool compareBinaryVars(const PseudoReducedCost obj1,
     160                              const PseudoReducedCost obj2)
     161{
     162  return obj1.pseudoRedCost > obj2.pseudoRedCost;
     163}
    147164
    148165// See if dive fractional will give better solution
     
    191208  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
    192209  const int * columnLength = matrix_.getVectorLengths();
     210  // Row copy
     211  const double * elementByRow = matrixByRow_.getElements();
     212  const int * column = matrixByRow_.getIndices();
     213  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     214  const int * rowLength = matrixByRow_.getVectorLengths();
    193215
    194216  // Get solution array for heuristic solution
     
    201223  double* originalBound = new double [numberIntegers];
    202224  bool * fixedAtLowerBound = new bool [numberIntegers];
     225  PseudoReducedCost * candidate = NULL;
     226  if(binVarIndex_.size())
     227    candidate = new PseudoReducedCost [binVarIndex_.size()];
    203228
    204229  const int maxNumberAtBoundToFix = (int) floor(percentageToFix_ * numberIntegers);
     
    214239  }
    215240
     241  const double* reducedCost = solver->getReducedCost();
     242
    216243  int iteration = 0;
    217244  while(numberFractionalVariables) {
     
    227254      canRoundSolution = false;
    228255     
    229     // fixed integer variables that are at there bounds
     256    // fix binary variables based on pseudo reduced cost
    230257    int numberAtBoundFixed = 0;
     258    if(binVarIndex_.size()) {
     259      int cnt = 0;
     260      for (int j=0; j<(int)binVarIndex_.size(); j++) {
     261        int iColumn = binVarIndex_[j];
     262        double value = newSolution[iColumn];
     263        double pseudoReducedCost = 0.0;
     264        if(fabs(value)<=integerTolerance &&
     265           lower[iColumn] != upper[iColumn]) {
     266          //      std::cout<<"iColumn = "<<iColumn<<", value = "<<value<<std::endl;
     267          int iRow = vbRowIndex_[j];
     268          assert(rowLength[iRow]==2);
     269          int k=rowStart[iRow];
     270          if(iColumn == column[k]) {
     271            pseudoReducedCost = fabs(reducedCost[column[k+1]] *
     272                                     elementByRow[k+1] /
     273                                     elementByRow[k]);
     274            //      std::cout<<"reducedCost["<<column[k+1]<<"] = "
     275            //               <<reducedCost[column[k+1]]
     276            //               <<", elementByRow["<<k+1<<"] = "<<elementByRow[k+1]
     277            //               <<", elementByRow["<<k<<"] = "<<elementByRow[k];
     278          }
     279          else {
     280            pseudoReducedCost = fabs(reducedCost[column[k]] *
     281                                     elementByRow[k] /
     282                                     elementByRow[k+1]);
     283            //      std::cout<<"reducedCost["<<column[k]<<"] = "
     284            //               <<reducedCost[column[k]]
     285            //               <<", elementByRow["<<k<<"] = "<<elementByRow[k]
     286            //               <<", elementByRow["<<k+1<<"] = "<<elementByRow[k+1];
     287          }
     288          //      std::cout<<", pseudoRedCost = "<<pseudoReducedCost<<std::endl;
     289          candidate[cnt].var = iColumn;
     290          candidate[cnt++].pseudoRedCost = pseudoReducedCost;
     291        }
     292      }
     293      //      std::cout<<"candidates for rounding = "<<cnt<<std::endl;
     294      std::sort(candidate, candidate+cnt, compareBinaryVars);
     295      for (int i=0; i<cnt; i++) {
     296        int iColumn = candidate[i].var;
     297        if (numberAtBoundFixed < maxNumberAtBoundToFix) {
     298          columnFixed[numberAtBoundFixed] = iColumn;
     299          originalBound[numberAtBoundFixed] = upper[iColumn];
     300          fixedAtLowerBound[numberAtBoundFixed] = true;
     301          solver->setColUpper(iColumn, lower[iColumn]);
     302          numberAtBoundFixed++;
     303          if(numberAtBoundFixed == maxNumberAtBoundToFix)
     304            break;
     305        }
     306      }
     307    }
     308    //    std::cout<<"numberAtBoundFixed = "<<numberAtBoundFixed<<std::endl;
     309
     310    // fix other integer variables that are at there bounds
    231311    for (int i=0; i<numberIntegers; i++) {
    232312      int iColumn = integerVariable[i];
     
    414494  delete [] originalBound;
    415495  delete [] fixedAtLowerBound;
     496  delete [] candidate;
    416497  delete [] rowActivity;
    417498  delete solver;
     
    471552    upLocks_[i] = (unsigned short) up;
    472553  }
    473 }
     554
     555#ifdef DIVE_FIX_BINARY_VARIABLES
     556  selectBinaryVariables();
     557#endif
     558}
     559
     560// Select candidate binary variables for fixing
     561void
     562CbcHeuristicDive::selectBinaryVariables()
     563{
     564  // Row copy
     565  const double * elementByRow = matrixByRow_.getElements();
     566  const int * column = matrixByRow_.getIndices();
     567  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     568  const int * rowLength = matrixByRow_.getVectorLengths();
     569
     570  const int numberRows = matrixByRow_.getNumRows();
     571  const int numberCols = matrixByRow_.getNumCols();
     572
     573  const double * lower = model_->solver()->getColLower();
     574  const double * upper = model_->solver()->getColUpper();
     575  const double * rowLower = model_->solver()->getRowLower();
     576  const double * rowUpper = model_->solver()->getRowUpper();
     577
     578  //  const char * integerType = model_->integerType();
     579 
     580
     581  //  const int numberIntegers = model_->numberIntegers();
     582  //  const int * integerVariable = model_->integerVariable();
     583  const double * objective = model_->solver()->getObjCoefficients();
     584
     585  // vector to store the row number of variable bound rows
     586  int* rowIndexes = new int [numberCols];
     587  memset(rowIndexes, -1, numberCols*sizeof(int));
     588
     589  for(int i=0; i<numberRows; i++) {
     590    int binVar = -1;
     591    int numContinuous = 0;
     592    if(rowLength[i] == 2) {
     593      int k = rowStart[i];
     594      int iColumn1 = column[k++];
     595      int iColumn2 = column[k];
     596      if(model_->solver()->isInteger(iColumn1) &&
     597         lower[iColumn1] == 0.0 && upper[iColumn1] == 1.0 &&
     598         objective[iColumn1] == 0.0 &&
     599         model_->solver()->isContinuous(iColumn2))
     600        binVar = iColumn1;
     601      else if(model_->solver()->isInteger(iColumn2) &&
     602              lower[iColumn2] == 0.0 && upper[iColumn2] == 1.0 &&
     603              objective[iColumn2] == 0.0 &&
     604              model_->solver()->isContinuous(iColumn1))
     605        binVar = iColumn2;
     606    }
     607    if(binVar >= 0 &&
     608       ((rowLower[i] == 0.0 && rowUpper[i] > 1.0e30) ||
     609        (rowLower[i] < -1.0e30 && rowUpper[i] == 0))) {
     610      if(rowIndexes[binVar] == -1)
     611        rowIndexes[binVar] = i;
     612      else if(rowIndexes[binVar] >= 0)
     613        rowIndexes[binVar] = -2;
     614    }
     615  }
     616
     617  for(int j=0; j<numberCols; j++) {
     618    if(rowIndexes[j] >= 0) {
     619      binVarIndex_.push_back(j);
     620      vbRowIndex_.push_back(rowIndexes[j]);
     621    }
     622  }
     623
     624  std::cout<<"number vub Binary = "<<binVarIndex_.size()<<std::endl;
     625
     626  delete [] rowIndexes;
     627   
     628}
  • trunk/Cbc/src/CbcHeuristicDive.hpp

    r912 r916  
    5555  virtual void validate();
    5656
     57  /// Select candidate binary variables for fixing
     58  void selectBinaryVariables();
     59
    5760  /// Set percentage of integer variables to fix at bounds
    5861  void setPercentageToFix(double value)
     
    8285  CoinPackedMatrix matrix_;
    8386
     87  // Original matrix by
     88  CoinPackedMatrix matrixByRow_;
     89
    8490  // Down locks
    8591  unsigned short * downLocks_;
     
    8793  // Up locks
    8894  unsigned short * upLocks_;
     95
     96  // Indexes of binary variables with 0 objective coefficient
     97  // and in variable bound constraints
     98  std::vector<int> binVarIndex_;
     99
     100  // Indexes of variable bound rows for each binary variable
     101  std::vector<int> vbRowIndex_;
    89102
    90103  // Percentage of integer variables to fix at bounds
Note: See TracChangeset for help on using the changeset viewer.