Changeset 916
 Timestamp:
 Apr 15, 2008 12:33:14 PM (11 years ago)
 Location:
 trunk/Cbc/src
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Cbc/src/CbcHeuristicDive.cpp
r912 r916 9 9 #include "CbcStrategy.hpp" 10 10 #include "CoinTime.hpp" 11 12 //#define DIVE_FIX_BINARY_VARIABLES 11 13 12 14 // Default Constructor … … 34 36 if (matrix) { 35 37 matrix_ = *matrix; 38 matrixByRow_ = *model.solver()>getMatrixByRow(); 36 39 validate(); 37 40 } … … 73 76 CbcHeuristic(rhs), 74 77 matrix_(rhs.matrix_), 78 matrixByRow_(rhs.matrixByRow_), 75 79 percentageToFix_(rhs.percentageToFix_), 76 80 maxIterations_(rhs.maxIterations_), … … 94 98 CbcHeuristic::operator=(rhs); 95 99 matrix_ = rhs.matrix_; 100 matrixByRow_ = rhs.matrixByRow_; 96 101 percentageToFix_ = rhs.percentageToFix_; 97 102 maxIterations_ = rhs.maxIterations_; … … 122 127 if (matrix) { 123 128 matrix_ = *matrix; 129 matrixByRow_ = *model>solver()>getMatrixByRow(); 124 130 validate(); 125 131 } … … 135 141 if (matrix) { 136 142 matrix_ = *matrix; 143 matrixByRow_ = *model>solver()>getMatrixByRow(); 137 144 // make sure model okay for heuristic 138 145 validate(); … … 145 152 } 146 153 154 struct PseudoReducedCost { 155 int var; 156 double pseudoRedCost; 157 }; 158 159 inline bool compareBinaryVars(const PseudoReducedCost obj1, 160 const PseudoReducedCost obj2) 161 { 162 return obj1.pseudoRedCost > obj2.pseudoRedCost; 163 } 147 164 148 165 // See if dive fractional will give better solution … … 191 208 const CoinBigIndex * columnStart = matrix_.getVectorStarts(); 192 209 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(); 193 215 194 216 // Get solution array for heuristic solution … … 201 223 double* originalBound = new double [numberIntegers]; 202 224 bool * fixedAtLowerBound = new bool [numberIntegers]; 225 PseudoReducedCost * candidate = NULL; 226 if(binVarIndex_.size()) 227 candidate = new PseudoReducedCost [binVarIndex_.size()]; 203 228 204 229 const int maxNumberAtBoundToFix = (int) floor(percentageToFix_ * numberIntegers); … … 214 239 } 215 240 241 const double* reducedCost = solver>getReducedCost(); 242 216 243 int iteration = 0; 217 244 while(numberFractionalVariables) { … … 227 254 canRoundSolution = false; 228 255 229 // fix ed integer variables that are at there bounds256 // fix binary variables based on pseudo reduced cost 230 257 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 231 311 for (int i=0; i<numberIntegers; i++) { 232 312 int iColumn = integerVariable[i]; … … 414 494 delete [] originalBound; 415 495 delete [] fixedAtLowerBound; 496 delete [] candidate; 416 497 delete [] rowActivity; 417 498 delete solver; … … 471 552 upLocks_[i] = (unsigned short) up; 472 553 } 473 } 554 555 #ifdef DIVE_FIX_BINARY_VARIABLES 556 selectBinaryVariables(); 557 #endif 558 } 559 560 // Select candidate binary variables for fixing 561 void 562 CbcHeuristicDive::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 55 55 virtual void validate(); 56 56 57 /// Select candidate binary variables for fixing 58 void selectBinaryVariables(); 59 57 60 /// Set percentage of integer variables to fix at bounds 58 61 void setPercentageToFix(double value) … … 82 85 CoinPackedMatrix matrix_; 83 86 87 // Original matrix by 88 CoinPackedMatrix matrixByRow_; 89 84 90 // Down locks 85 91 unsigned short * downLocks_; … … 87 93 // Up locks 88 94 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_; 89 102 90 103 // Percentage of integer variables to fix at bounds
Note: See TracChangeset
for help on using the changeset viewer.