Changeset 2385 for trunk/Clp/src/ClpNode.cpp
 Timestamp:
 Jan 6, 2019 2:43:06 PM (4 months ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Clp/src/ClpNode.cpp
r1910 r2385 17 17 // Default Constructor 18 18 // 19 ClpNode::ClpNode () :20 branchingValue_(0.5),21 objectiveValue_(0.0),22 sumInfeasibilities_(0.0),23 estimatedSolution_(0.0),24 factorization_(NULL),25 weights_(NULL),26 status_(NULL),27 primalSolution_(NULL),28 dualSolution_(NULL),29 lower_(NULL),30 upper_(NULL),31 pivotVariables_(NULL),32 fixed_(NULL),33 sequence_(1),34 numberInfeasibilities_(0),35 depth_(0),36 numberFixed_(0),37 flags_(0),38 maximumFixed_(0),39 maximumRows_(0),40 maximumColumns_(0),41 42 { 43 44 19 ClpNode::ClpNode() 20 : branchingValue_(0.5) 21 , objectiveValue_(0.0) 22 , sumInfeasibilities_(0.0) 23 , estimatedSolution_(0.0) 24 , factorization_(NULL) 25 , weights_(NULL) 26 , status_(NULL) 27 , primalSolution_(NULL) 28 , dualSolution_(NULL) 29 , lower_(NULL) 30 , upper_(NULL) 31 , pivotVariables_(NULL) 32 , fixed_(NULL) 33 , sequence_(1) 34 , numberInfeasibilities_(0) 35 , depth_(0) 36 , numberFixed_(0) 37 , flags_(0) 38 , maximumFixed_(0) 39 , maximumRows_(0) 40 , maximumColumns_(0) 41 , maximumIntegers_(0) 42 { 43 branchState_.firstBranch = 0; 44 branchState_.branch = 0; 45 45 } 46 46 // 47 47 // Useful Constructor from model 48 48 // 49 ClpNode::ClpNode (ClpSimplex * model, const ClpNodeStuff * stuff, int depth) :50 branchingValue_(0.5),51 objectiveValue_(0.0),52 sumInfeasibilities_(0.0),53 estimatedSolution_(0.0),54 factorization_(NULL),55 weights_(NULL),56 status_(NULL),57 primalSolution_(NULL),58 dualSolution_(NULL),59 lower_(NULL),60 upper_(NULL),61 pivotVariables_(NULL),62 fixed_(NULL),63 sequence_(1),64 numberInfeasibilities_(0),65 depth_(0),66 numberFixed_(0),67 flags_(0),68 maximumFixed_(0),69 maximumRows_(0),70 maximumColumns_(0),71 72 { 73 74 75 49 ClpNode::ClpNode(ClpSimplex *model, const ClpNodeStuff *stuff, int depth) 50 : branchingValue_(0.5) 51 , objectiveValue_(0.0) 52 , sumInfeasibilities_(0.0) 53 , estimatedSolution_(0.0) 54 , factorization_(NULL) 55 , weights_(NULL) 56 , status_(NULL) 57 , primalSolution_(NULL) 58 , dualSolution_(NULL) 59 , lower_(NULL) 60 , upper_(NULL) 61 , pivotVariables_(NULL) 62 , fixed_(NULL) 63 , sequence_(1) 64 , numberInfeasibilities_(0) 65 , depth_(0) 66 , numberFixed_(0) 67 , flags_(0) 68 , maximumFixed_(0) 69 , maximumRows_(0) 70 , maximumColumns_(0) 71 , maximumIntegers_(0) 72 { 73 branchState_.firstBranch = 0; 74 branchState_.branch = 0; 75 gutsOfConstructor(model, stuff, 0, depth); 76 76 } 77 77 … … 79 79 // Most of work of constructor from model 80 80 // 81 void 82 ClpNode::gutsOfConstructor (ClpSimplex * model, const ClpNodeStuff * stuff, 83 int arraysExist, int depth) 84 { 85 int numberRows = model>numberRows(); 86 int numberColumns = model>numberColumns(); 87 int numberTotal = numberRows + numberColumns; 88 int maximumTotal = maximumRows_ + maximumColumns_; 89 depth_ = depth; 90 // save stuff 91 objectiveValue_ = model>objectiveValue() * model>optimizationDirection(); 92 estimatedSolution_ = objectiveValue_; 93 flags_ = 1; //say scaled 94 if (!arraysExist) { 95 maximumRows_ = CoinMax(maximumRows_, numberRows); 96 maximumColumns_ = CoinMax(maximumColumns_, numberColumns); 97 maximumTotal = maximumRows_ + maximumColumns_; 98 assert (!factorization_); 99 factorization_ = new ClpFactorization(*model>factorization(), numberRows); 100 status_ = CoinCopyOfArrayPartial(model>statusArray(), maximumTotal, numberTotal); 101 primalSolution_ = CoinCopyOfArrayPartial(model>solutionRegion(), maximumTotal, numberTotal); 102 dualSolution_ = CoinCopyOfArrayPartial(model>djRegion(), maximumTotal, numberTotal); //? has duals as well? 103 pivotVariables_ = CoinCopyOfArrayPartial(model>pivotVariable(), maximumRows_, numberRows); 104 ClpDualRowSteepest* pivot = 105 dynamic_cast< ClpDualRowSteepest*>(model>dualRowPivot()); 106 if (pivot) { 107 assert (!weights_); 108 weights_ = new ClpDualRowSteepest(*pivot); 81 void ClpNode::gutsOfConstructor(ClpSimplex *model, const ClpNodeStuff *stuff, 82 int arraysExist, int depth) 83 { 84 int numberRows = model>numberRows(); 85 int numberColumns = model>numberColumns(); 86 int numberTotal = numberRows + numberColumns; 87 int maximumTotal = maximumRows_ + maximumColumns_; 88 depth_ = depth; 89 // save stuff 90 objectiveValue_ = model>objectiveValue() * model>optimizationDirection(); 91 estimatedSolution_ = objectiveValue_; 92 flags_ = 1; //say scaled 93 if (!arraysExist) { 94 maximumRows_ = CoinMax(maximumRows_, numberRows); 95 maximumColumns_ = CoinMax(maximumColumns_, numberColumns); 96 maximumTotal = maximumRows_ + maximumColumns_; 97 assert(!factorization_); 98 factorization_ = new ClpFactorization(*model>factorization(), numberRows); 99 status_ = CoinCopyOfArrayPartial(model>statusArray(), maximumTotal, numberTotal); 100 primalSolution_ = CoinCopyOfArrayPartial(model>solutionRegion(), maximumTotal, numberTotal); 101 dualSolution_ = CoinCopyOfArrayPartial(model>djRegion(), maximumTotal, numberTotal); //? has duals as well? 102 pivotVariables_ = CoinCopyOfArrayPartial(model>pivotVariable(), maximumRows_, numberRows); 103 ClpDualRowSteepest *pivot = dynamic_cast< ClpDualRowSteepest * >(model>dualRowPivot()); 104 if (pivot) { 105 assert(!weights_); 106 weights_ = new ClpDualRowSteepest(*pivot); 107 } 108 } else { 109 if (arraysExist == 2) 110 assert(lower_); 111 if (numberRows <= maximumRows_ && numberColumns <= maximumColumns_) { 112 CoinMemcpyN(model>statusArray(), numberTotal, status_); 113 if (arraysExist == 1) { 114 *factorization_ = *model>factorization(); 115 CoinMemcpyN(model>solutionRegion(), numberTotal, primalSolution_); 116 CoinMemcpyN(model>djRegion(), numberTotal, dualSolution_); //? has duals as well? 117 ClpDualRowSteepest *pivot = dynamic_cast< ClpDualRowSteepest * >(model>dualRowPivot()); 118 if (pivot) { 119 if (weights_) { 120 //if (weights_>numberRows()==pivot>numberRows()) { 121 weights_>fill(*pivot); 122 //} else { 123 //delete weights_; 124 //weights_ = new ClpDualRowSteepest(*pivot); 125 //} 126 } else { 127 weights_ = new ClpDualRowSteepest(*pivot); 109 128 } 110 } else { 111 if (arraysExist == 2) 112 assert(lower_); 113 if (numberRows <= maximumRows_ && numberColumns <= maximumColumns_) { 114 CoinMemcpyN(model>statusArray(), numberTotal, status_); 115 if (arraysExist == 1) { 116 *factorization_ = *model>factorization(); 117 CoinMemcpyN(model>solutionRegion(), numberTotal, primalSolution_); 118 CoinMemcpyN(model>djRegion(), numberTotal, dualSolution_); //? has duals as well? 119 ClpDualRowSteepest* pivot = 120 dynamic_cast< ClpDualRowSteepest*>(model>dualRowPivot()); 121 if (pivot) { 122 if (weights_) { 123 //if (weights_>numberRows()==pivot>numberRows()) { 124 weights_>fill(*pivot); 125 //} else { 126 //delete weights_; 127 //weights_ = new ClpDualRowSteepest(*pivot); 128 //} 129 } else { 130 weights_ = new ClpDualRowSteepest(*pivot); 131 } 132 } 133 CoinMemcpyN(model>pivotVariable(), numberRows, pivotVariables_); 134 } else { 135 CoinMemcpyN(model>primalColumnSolution(), numberColumns, primalSolution_); 136 CoinMemcpyN(model>dualColumnSolution(), numberColumns, dualSolution_); 137 flags_ = 0; 138 CoinMemcpyN(model>dualRowSolution(), numberRows, dualSolution_ + numberColumns); 139 } 140 } else { 141 // size has changed 142 maximumRows_ = CoinMax(maximumRows_, numberRows); 143 maximumColumns_ = CoinMax(maximumColumns_, numberColumns); 144 maximumTotal = maximumRows_ + maximumColumns_; 145 delete weights_; 146 weights_ = NULL; 147 delete [] status_; 148 delete [] primalSolution_; 149 delete [] dualSolution_; 150 delete [] pivotVariables_; 151 status_ = CoinCopyOfArrayPartial(model>statusArray(), maximumTotal, numberTotal); 152 primalSolution_ = new double [maximumTotal*sizeof(double)]; 153 dualSolution_ = new double [maximumTotal*sizeof(double)]; 154 if (arraysExist == 1) { 155 *factorization_ = *model>factorization(); // I think this is OK 156 CoinMemcpyN(model>solutionRegion(), numberTotal, primalSolution_); 157 CoinMemcpyN(model>djRegion(), numberTotal, dualSolution_); //? has duals as well? 158 ClpDualRowSteepest* pivot = 159 dynamic_cast< ClpDualRowSteepest*>(model>dualRowPivot()); 160 if (pivot) { 161 assert (!weights_); 162 weights_ = new ClpDualRowSteepest(*pivot); 163 } 164 } else { 165 CoinMemcpyN(model>primalColumnSolution(), numberColumns, primalSolution_); 166 CoinMemcpyN(model>dualColumnSolution(), numberColumns, dualSolution_); 167 flags_ = 0; 168 CoinMemcpyN(model>dualRowSolution(), numberRows, dualSolution_ + numberColumns); 169 } 170 pivotVariables_ = new int [maximumRows_]; 171 if (model>pivotVariable() && model>numberRows() == numberRows) 172 CoinMemcpyN(model>pivotVariable(), numberRows, pivotVariables_); 173 else 174 CoinFillN(pivotVariables_, numberRows, 1); 175 } 176 } 177 numberFixed_ = 0; 178 const double * lower = model>columnLower(); 179 const double * upper = model>columnUpper(); 180 const double * solution = model>primalColumnSolution(); 181 const char * integerType = model>integerInformation(); 182 const double * columnScale = model>columnScale(); 183 if (!flags_) 184 columnScale = NULL; // as duals correct 185 int iColumn; 186 sequence_ = 1; 187 double integerTolerance = stuff>integerTolerance_; 188 double mostAway = 0.0; 189 int bestPriority = COIN_INT_MAX; 190 sumInfeasibilities_ = 0.0; 191 numberInfeasibilities_ = 0; 192 int nFix = 0; 193 double gap = CoinMax(model>dualObjectiveLimit()  objectiveValue_, 1.0e4); 129 } 130 CoinMemcpyN(model>pivotVariable(), numberRows, pivotVariables_); 131 } else { 132 CoinMemcpyN(model>primalColumnSolution(), numberColumns, primalSolution_); 133 CoinMemcpyN(model>dualColumnSolution(), numberColumns, dualSolution_); 134 flags_ = 0; 135 CoinMemcpyN(model>dualRowSolution(), numberRows, dualSolution_ + numberColumns); 136 } 137 } else { 138 // size has changed 139 maximumRows_ = CoinMax(maximumRows_, numberRows); 140 maximumColumns_ = CoinMax(maximumColumns_, numberColumns); 141 maximumTotal = maximumRows_ + maximumColumns_; 142 delete weights_; 143 weights_ = NULL; 144 delete[] status_; 145 delete[] primalSolution_; 146 delete[] dualSolution_; 147 delete[] pivotVariables_; 148 status_ = CoinCopyOfArrayPartial(model>statusArray(), maximumTotal, numberTotal); 149 primalSolution_ = new double[maximumTotal * sizeof(double)]; 150 dualSolution_ = new double[maximumTotal * sizeof(double)]; 151 if (arraysExist == 1) { 152 *factorization_ = *model>factorization(); // I think this is OK 153 CoinMemcpyN(model>solutionRegion(), numberTotal, primalSolution_); 154 CoinMemcpyN(model>djRegion(), numberTotal, dualSolution_); //? has duals as well? 155 ClpDualRowSteepest *pivot = dynamic_cast< ClpDualRowSteepest * >(model>dualRowPivot()); 156 if (pivot) { 157 assert(!weights_); 158 weights_ = new ClpDualRowSteepest(*pivot); 159 } 160 } else { 161 CoinMemcpyN(model>primalColumnSolution(), numberColumns, primalSolution_); 162 CoinMemcpyN(model>dualColumnSolution(), numberColumns, dualSolution_); 163 flags_ = 0; 164 CoinMemcpyN(model>dualRowSolution(), numberRows, dualSolution_ + numberColumns); 165 } 166 pivotVariables_ = new int[maximumRows_]; 167 if (model>pivotVariable() && model>numberRows() == numberRows) 168 CoinMemcpyN(model>pivotVariable(), numberRows, pivotVariables_); 169 else 170 CoinFillN(pivotVariables_, numberRows, 1); 171 } 172 } 173 numberFixed_ = 0; 174 const double *lower = model>columnLower(); 175 const double *upper = model>columnUpper(); 176 const double *solution = model>primalColumnSolution(); 177 const char *integerType = model>integerInformation(); 178 const double *columnScale = model>columnScale(); 179 if (!flags_) 180 columnScale = NULL; // as duals correct 181 int iColumn; 182 sequence_ = 1; 183 double integerTolerance = stuff>integerTolerance_; 184 double mostAway = 0.0; 185 int bestPriority = COIN_INT_MAX; 186 sumInfeasibilities_ = 0.0; 187 numberInfeasibilities_ = 0; 188 int nFix = 0; 189 double gap = CoinMax(model>dualObjectiveLimit()  objectiveValue_, 1.0e4); 194 190 #define PSEUDO 3 195 #if PSEUDO ==1PSEUDO==2196 197 ClpPackedMatrix *matrix = model>clpScaledMatrix();198 const double *objective = model>costRegion();199 200 201 202 matrix = dynamic_cast< ClpPackedMatrix*>(model>clpMatrix());203 204 matrix = dynamic_cast< ClpPackedMatrix*>(model>clpMatrix());205 206 const double *element = matrix>getElements();207 const int *row = matrix>getIndices();208 const CoinBigIndex *columnStart = matrix>getVectorStarts();209 const int *columnLength = matrix>getVectorLengths();210 211 const double *dual = dualSolution_ + numberColumns;212 #if PSEUDO ==2213 double * activeWeight = new double[numberRows];214 const double *rowLower = model>rowLower();215 const double *rowUpper = model>rowUpper();216 const double *rowActivity = model>primalRowSolution();217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 #endif 250 #endif 251 const double *downPseudo = stuff>downPseudo_;252 const int *numberDown = stuff>numberDown_;253 const int *numberDownInfeasible = stuff>numberDownInfeasible_;254 const double *upPseudo = stuff>upPseudo_;255 const int *priority = stuff>priority_;256 const int *numberUp = stuff>numberUp_;257 const int *numberUpInfeasible = stuff>numberUpInfeasible_;258 259 260 261 191 #if PSEUDO == 1  PSEUDO == 2 192 // Column copy of matrix 193 ClpPackedMatrix *matrix = model>clpScaledMatrix(); 194 const double *objective = model>costRegion(); 195 if (!objective) { 196 objective = model>objective(); 197 //if (!matrix) 198 matrix = dynamic_cast< ClpPackedMatrix * >(model>clpMatrix()); 199 } else if (!matrix) { 200 matrix = dynamic_cast< ClpPackedMatrix * >(model>clpMatrix()); 201 } 202 const double *element = matrix>getElements(); 203 const int *row = matrix>getIndices(); 204 const CoinBigIndex *columnStart = matrix>getVectorStarts(); 205 const int *columnLength = matrix>getVectorLengths(); 206 double direction = model>optimizationDirection(); 207 const double *dual = dualSolution_ + numberColumns; 208 #if PSEUDO == 2 209 double *activeWeight = new double[numberRows]; 210 const double *rowLower = model>rowLower(); 211 const double *rowUpper = model>rowUpper(); 212 const double *rowActivity = model>primalRowSolution(); 213 double tolerance = 1.0e6; 214 for (int iRow = 0; iRow < numberRows; iRow++) { 215 // could use pi to see if active or activity 216 if (rowActivity[iRow] > rowUpper[iRow]  tolerance 217  rowActivity[iRow] < rowLower[iRow] + tolerance) { 218 activeWeight[iRow] = 0.0; 219 } else { 220 activeWeight[iRow] = 1.0; 221 } 222 } 223 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 224 if (integerType[iColumn]) { 225 double value = solution[iColumn]; 226 if (fabs(value  floor(value + 0.5)) > 1.0e6) { 227 CoinBigIndex start = columnStart[iColumn]; 228 CoinBigIndex end = start + columnLength[iColumn]; 229 for (CoinBigIndex j = start; j < end; j++) { 230 int iRow = row[j]; 231 if (activeWeight[iRow] >= 0.0) 232 activeWeight[iRow] += 1.0; 233 } 234 } 235 } 236 } 237 for (int iRow = 0; iRow < numberRows; iRow++) { 238 if (activeWeight[iRow] > 0.0) { 239 // could use pi 240 activeWeight[iRow] = 1.0 / activeWeight[iRow]; 241 } else { 242 activeWeight[iRow] = 0.0; 243 } 244 } 245 #endif 246 #endif 247 const double *downPseudo = stuff>downPseudo_; 248 const int *numberDown = stuff>numberDown_; 249 const int *numberDownInfeasible = stuff>numberDownInfeasible_; 250 const double *upPseudo = stuff>upPseudo_; 251 const int *priority = stuff>priority_; 252 const int *numberUp = stuff>numberUp_; 253 const int *numberUpInfeasible = stuff>numberUpInfeasible_; 254 int numberBeforeTrust = stuff>numberBeforeTrust_; 255 int stateOfSearch = stuff>stateOfSearch_; 256 int iInteger = 0; 257 // weight at 1.0 is max min (CbcBranch was 0.8,0.1) (ClpNode was 0.9,0.9) 262 258 #define WEIGHT_AFTER 0.9 263 259 #define WEIGHT_BEFORE 0.2 264 260 //Stolen from Constraint Integer Programming book (with epsilon change) 265 261 #define WEIGHT_PRODUCT 266 262 #ifdef WEIGHT_PRODUCT 267 268 #endif 269 #ifndef INFEAS_MULTIPLIER 263 double smallChange = stuff>smallChange_; 264 #endif 265 #ifndef INFEAS_MULTIPLIER 270 266 #define INFEAS_MULTIPLIER 1.0 271 267 #endif 272 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 273 if (integerType[iColumn]) { 274 double value = solution[iColumn]; 275 value = CoinMax(value, static_cast<double> (lower[iColumn])); 276 value = CoinMin(value, static_cast<double> (upper[iColumn])); 277 double nearest = floor(value + 0.5); 278 if (fabs(value  nearest) > integerTolerance) { 279 numberInfeasibilities_++; 280 sumInfeasibilities_ += fabs(value  nearest); 281 #if PSEUDO==1  PSEUDO ==2 282 double upValue = 0.0; 283 double downValue = 0.0; 284 double value2 = direction * objective[iColumn]; 285 //double dj2=value2; 286 if (value2) { 287 if (value2 > 0.0) 288 upValue += 1.5 * value2; 289 else 290 downValue = 1.5 * value2; 291 } 292 CoinBigIndex start = columnStart[iColumn]; 293 CoinBigIndex end = columnStart[iColumn] + columnLength[iColumn]; 294 for (CoinBigIndex j = start; j < end; j++) { 295 int iRow = row[j]; 296 value2 = dual[iRow]; 297 if (value2) { 298 value2 *= element[j]; 299 //dj2 += value2; 300 #if PSEUDO==2 301 assert (activeWeight[iRow] > 0.0  fabs(dual[iRow]) < 1.0e6); 302 value2 *= activeWeight[iRow]; 303 #endif 304 if (value2 > 0.0) 305 upValue += value2; 306 else 307 downValue = value2; 308 } 309 } 310 //assert (fabs(dj2)<1.0e4); 311 int nUp = numberUp[iInteger]; 312 double upValue2 = (upPseudo[iInteger] / (1.0 + nUp)); 313 // Extra for infeasible branches 314 if (nUp) { 315 double ratio = 1.0 + INFEAS_MULTIPLIER*static_cast<double>(numberUpInfeasible[iInteger]) / 316 static_cast<double>(nUp); 317 upValue2 *= ratio; 318 } 319 int nDown = numberDown[iInteger]; 320 double downValue2 = (downPseudo[iInteger] / (1.0 + nDown)); 321 if (nDown) { 322 double ratio = 1.0 + INFEAS_MULTIPLIER*static_cast<double>(numberDownInfeasible[iInteger]) / 323 static_cast<double>(nDown); 324 downValue2 *= ratio; 325 } 326 //printf("col %d  downPi %g up %g, downPs %g up %g\n", 327 // iColumn,upValue,downValue,upValue2,downValue2); 328 upValue = CoinMax(0.1 * upValue, upValue2); 329 downValue = CoinMax(0.1 * downValue, downValue2); 330 //upValue = CoinMax(upValue,1.0e8); 331 //downValue = CoinMax(downValue,1.0e8); 332 upValue *= ceil(value)  value; 333 downValue *= value  floor(value); 334 double infeasibility; 335 //if (depth>1000) 336 //infeasibility = CoinMax(upValue,downValue)+integerTolerance; 337 //else 338 if (stateOfSearch <= 2) { 339 // no solution 340 infeasibility = (1.0  WEIGHT_BEFORE) * CoinMax(upValue, downValue) + 341 WEIGHT_BEFORE * CoinMin(upValue, downValue) + integerTolerance; 342 } else { 268 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 269 if (integerType[iColumn]) { 270 double value = solution[iColumn]; 271 value = CoinMax(value, static_cast< double >(lower[iColumn])); 272 value = CoinMin(value, static_cast< double >(upper[iColumn])); 273 double nearest = floor(value + 0.5); 274 if (fabs(value  nearest) > integerTolerance) { 275 numberInfeasibilities_++; 276 sumInfeasibilities_ += fabs(value  nearest); 277 #if PSEUDO == 1  PSEUDO == 2 278 double upValue = 0.0; 279 double downValue = 0.0; 280 double value2 = direction * objective[iColumn]; 281 //double dj2=value2; 282 if (value2) { 283 if (value2 > 0.0) 284 upValue += 1.5 * value2; 285 else 286 downValue = 1.5 * value2; 287 } 288 CoinBigIndex start = columnStart[iColumn]; 289 CoinBigIndex end = columnStart[iColumn] + columnLength[iColumn]; 290 for (CoinBigIndex j = start; j < end; j++) { 291 int iRow = row[j]; 292 value2 = dual[iRow]; 293 if (value2) { 294 value2 *= element[j]; 295 //dj2 += value2; 296 #if PSEUDO == 2 297 assert(activeWeight[iRow] > 0.0  fabs(dual[iRow]) < 1.0e6); 298 value2 *= activeWeight[iRow]; 299 #endif 300 if (value2 > 0.0) 301 upValue += value2; 302 else 303 downValue = value2; 304 } 305 } 306 //assert (fabs(dj2)<1.0e4); 307 int nUp = numberUp[iInteger]; 308 double upValue2 = (upPseudo[iInteger] / (1.0 + nUp)); 309 // Extra for infeasible branches 310 if (nUp) { 311 double ratio = 1.0 + INFEAS_MULTIPLIER * static_cast< double >(numberUpInfeasible[iInteger]) / static_cast< double >(nUp); 312 upValue2 *= ratio; 313 } 314 int nDown = numberDown[iInteger]; 315 double downValue2 = (downPseudo[iInteger] / (1.0 + nDown)); 316 if (nDown) { 317 double ratio = 1.0 + INFEAS_MULTIPLIER * static_cast< double >(numberDownInfeasible[iInteger]) / static_cast< double >(nDown); 318 downValue2 *= ratio; 319 } 320 //printf("col %d  downPi %g up %g, downPs %g up %g\n", 321 // iColumn,upValue,downValue,upValue2,downValue2); 322 upValue = CoinMax(0.1 * upValue, upValue2); 323 downValue = CoinMax(0.1 * downValue, downValue2); 324 //upValue = CoinMax(upValue,1.0e8); 325 //downValue = CoinMax(downValue,1.0e8); 326 upValue *= ceil(value)  value; 327 downValue *= value  floor(value); 328 double infeasibility; 329 //if (depth>1000) 330 //infeasibility = CoinMax(upValue,downValue)+integerTolerance; 331 //else 332 if (stateOfSearch <= 2) { 333 // no solution 334 infeasibility = (1.0  WEIGHT_BEFORE) * CoinMax(upValue, downValue) + WEIGHT_BEFORE * CoinMin(upValue, downValue) + integerTolerance; 335 } else { 343 336 #ifndef WEIGHT_PRODUCT 344 infeasibility = (1.0  WEIGHT_AFTER) * CoinMax(upValue, downValue) + 345 WEIGHT_AFTER * CoinMin(upValue, downValue) + integerTolerance; 337 infeasibility = (1.0  WEIGHT_AFTER) * CoinMax(upValue, downValue) + WEIGHT_AFTER * CoinMin(upValue, downValue) + integerTolerance; 346 338 #else 347 infeasibility = CoinMax(CoinMax(upValue, downValue), smallChange) * 348 CoinMax(CoinMin(upValue, downValue), smallChange); 349 #endif 350 } 351 estimatedSolution_ += CoinMin(upValue2, downValue2); 352 #elif PSEUDO==3 353 int nUp = numberUp[iInteger]; 354 int nDown = numberDown[iInteger]; 355 // Extra 100% for infeasible branches 356 double upValue = (ceil(value)  value) * (upPseudo[iInteger] / 357 (1.0 + nUp)); 358 if (nUp) { 359 double ratio = 1.0 + INFEAS_MULTIPLIER*static_cast<double>(numberUpInfeasible[iInteger]) / 360 static_cast<double>(nUp); 361 upValue *= ratio; 362 } 363 double downValue = (value  floor(value)) * (downPseudo[iInteger] / 364 (1.0 + nDown)); 365 if (nDown) { 366 double ratio = 1.0 + INFEAS_MULTIPLIER*static_cast<double>(numberDownInfeasible[iInteger]) / 367 static_cast<double>(nDown); 368 downValue *= ratio; 369 } 370 if (nUp < numberBeforeTrust  nDown < numberBeforeTrust) { 371 upValue *= 10.0; 372 downValue *= 10.0; 373 } 374 375 double infeasibility; 376 //if (depth>1000) 377 //infeasibility = CoinMax(upValue,downValue)+integerTolerance; 378 //else 379 if (stateOfSearch <= 2) { 380 // no solution 381 infeasibility = (1.0  WEIGHT_BEFORE) * CoinMax(upValue, downValue) + 382 WEIGHT_BEFORE * CoinMin(upValue, downValue) + integerTolerance; 383 } else { 339 infeasibility = CoinMax(CoinMax(upValue, downValue), smallChange) * CoinMax(CoinMin(upValue, downValue), smallChange); 340 #endif 341 } 342 estimatedSolution_ += CoinMin(upValue2, downValue2); 343 #elif PSEUDO == 3 344 int nUp = numberUp[iInteger]; 345 int nDown = numberDown[iInteger]; 346 // Extra 100% for infeasible branches 347 double upValue = (ceil(value)  value) * (upPseudo[iInteger] / (1.0 + nUp)); 348 if (nUp) { 349 double ratio = 1.0 + INFEAS_MULTIPLIER * static_cast< double >(numberUpInfeasible[iInteger]) / static_cast< double >(nUp); 350 upValue *= ratio; 351 } 352 double downValue = (value  floor(value)) * (downPseudo[iInteger] / (1.0 + nDown)); 353 if (nDown) { 354 double ratio = 1.0 + INFEAS_MULTIPLIER * static_cast< double >(numberDownInfeasible[iInteger]) / static_cast< double >(nDown); 355 downValue *= ratio; 356 } 357 if (nUp < numberBeforeTrust  nDown < numberBeforeTrust) { 358 upValue *= 10.0; 359 downValue *= 10.0; 360 } 361 362 double infeasibility; 363 //if (depth>1000) 364 //infeasibility = CoinMax(upValue,downValue)+integerTolerance; 365 //else 366 if (stateOfSearch <= 2) { 367 // no solution 368 infeasibility = (1.0  WEIGHT_BEFORE) * CoinMax(upValue, downValue) + WEIGHT_BEFORE * CoinMin(upValue, downValue) + integerTolerance; 369 } else { 384 370 #ifndef WEIGHT_PRODUCT 385 infeasibility = (1.0  WEIGHT_AFTER) * CoinMax(upValue, downValue) + 386 WEIGHT_AFTER * CoinMin(upValue, downValue) + integerTolerance; 371 infeasibility = (1.0  WEIGHT_AFTER) * CoinMax(upValue, downValue) + WEIGHT_AFTER * CoinMin(upValue, downValue) + integerTolerance; 387 372 #else 388 infeasibility = CoinMax(CoinMax(upValue, downValue), smallChange) * 389 CoinMax(CoinMin(upValue, downValue), smallChange); 390 //infeasibility += CoinMin(upValue,downValue)*smallChange; 391 #endif 392 } 393 //infeasibility = 0.1*CoinMax(upValue,downValue)+ 394 //0.9*CoinMin(upValue,downValue) + integerTolerance; 395 estimatedSolution_ += CoinMin(upValue, downValue); 373 infeasibility = CoinMax(CoinMax(upValue, downValue), smallChange) * CoinMax(CoinMin(upValue, downValue), smallChange); 374 //infeasibility += CoinMin(upValue,downValue)*smallChange; 375 #endif 376 } 377 //infeasibility = 0.1*CoinMax(upValue,downValue)+ 378 //0.9*CoinMin(upValue,downValue) + integerTolerance; 379 estimatedSolution_ += CoinMin(upValue, downValue); 396 380 #else 397 398 #endif 399 assert(infeasibility > 0.0);400 401 402 403 404 405 406 407 408 409 410 411 #if PSEUDO >0412 413 414 415 381 double infeasibility = fabs(value  nearest); 382 #endif 383 assert(infeasibility > 0.0); 384 if (priority[iInteger] < bestPriority) { 385 mostAway = 0.0; 386 bestPriority = priority[iInteger]; 387 } else if (priority[iInteger] > bestPriority) { 388 infeasibility = 0.0; 389 } 390 if (infeasibility > mostAway) { 391 mostAway = infeasibility; 392 sequence_ = iColumn; 393 branchingValue_ = value; 394 branchState_.branch = 0; 395 #if PSEUDO > 0 396 if (upValue <= downValue) 397 branchState_.firstBranch = 1; // up 398 else 399 branchState_.firstBranch = 0; // down 416 400 #else 417 418 419 420 421 #endif 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 401 if (value <= nearest) 402 branchState_.firstBranch = 1; // up 403 else 404 branchState_.firstBranch = 0; // down 405 #endif 406 } 407 } else if (model>getColumnStatus(iColumn) == ClpSimplex::atLowerBound) { 408 bool fix = false; 409 if (columnScale) { 410 if (dualSolution_[iColumn] > gap * columnScale[iColumn]) 411 fix = true; 412 } else { 413 if (dualSolution_[iColumn] > gap) 414 fix = true; 415 } 416 if (fix) { 417 nFix++; 418 //printf("fixed %d to zero gap %g dj %g %g\n",iColumn, 419 // gap,dualSolution_[iColumn], columnScale ? columnScale[iColumn]:1.0); 420 model>setColumnStatus(iColumn, ClpSimplex::isFixed); 421 } 422 } else if (model>getColumnStatus(iColumn) == ClpSimplex::atUpperBound) { 423 bool fix = false; 424 if (columnScale) { 425 if (dualSolution_[iColumn] > gap * columnScale[iColumn]) 426 fix = true; 427 } else { 428 if (dualSolution_[iColumn] > gap) 429 fix = true; 430 } 431 if (fix) { 432 nFix++; 433 //printf("fixed %d to one gap %g dj %g %g\n",iColumn, 434 // gap,dualSolution_[iColumn], columnScale ? columnScale[iColumn]:1.0); 435 model>setColumnStatus(iColumn, ClpSimplex::isFixed); 436 } 437 } 438 iInteger++; 439 } 440 } 441 //printf("Choosing %d inf %g pri %d\n", 442 // sequence_,mostAway,bestPriority); 459 443 #if PSEUDO == 2 460 delete[] activeWeight;461 #endif 462 463 464 465 delete[] lower_;466 delete[] upper_;467 468 lower_ = new int[maximumIntegers_];469 upper_ = new int[maximumIntegers_];470 471 472 473 474 lower_[iInteger] = static_cast<int>(lower[iColumn]);475 upper_[iInteger] = static_cast<int>(upper[iColumn]);476 477 478 479 480 481 482 483 delete[] fixed_;484 fixed_ = new int[nFix];485 486 487 488 unsigned char *status = model>statusArray();489 490 491 492 493 494 495 assert(solution[iColumn] >= upper[iColumn]  2.0 * integerTolerance);496 497 498 499 500 501 502 444 delete[] activeWeight; 445 #endif 446 if (lower_) { 447 // save bounds 448 if (iInteger > maximumIntegers_) { 449 delete[] lower_; 450 delete[] upper_; 451 maximumIntegers_ = iInteger; 452 lower_ = new int[maximumIntegers_]; 453 upper_ = new int[maximumIntegers_]; 454 } 455 iInteger = 0; 456 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 457 if (integerType[iColumn]) { 458 lower_[iInteger] = static_cast< int >(lower[iColumn]); 459 upper_[iInteger] = static_cast< int >(upper[iColumn]); 460 iInteger++; 461 } 462 } 463 } 464 // Could omit save of fixed if doing full save of bounds 465 if (sequence_ >= 0 && nFix) { 466 if (nFix > maximumFixed_) { 467 delete[] fixed_; 468 fixed_ = new int[nFix]; 469 maximumFixed_ = nFix; 470 } 471 numberFixed_ = 0; 472 unsigned char *status = model>statusArray(); 473 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 474 if (status[iColumn] != status_[iColumn]) { 475 if (solution[iColumn] <= lower[iColumn] + 2.0 * integerTolerance) { 476 model>setColumnUpper(iColumn, lower[iColumn]); 477 fixed_[numberFixed_++] = iColumn; 478 } else { 479 assert(solution[iColumn] >= upper[iColumn]  2.0 * integerTolerance); 480 model>setColumnLower(iColumn, upper[iColumn]); 481 fixed_[numberFixed_++] = iColumn  0x10000000; 482 } 483 } 484 } 485 //printf("%d fixed\n",numberFixed_); 486 } 503 487 } 504 488 … … 506 490 // Copy constructor 507 491 // 508 ClpNode::ClpNode (const ClpNode &)509 { 510 511 492 ClpNode::ClpNode(const ClpNode &) 493 { 494 printf("ClpNode copy not implemented\n"); 495 abort(); 512 496 } 513 497 … … 515 499 // Destructor 516 500 // 517 ClpNode::~ClpNode 518 { 519 520 521 delete[] status_;522 delete[] primalSolution_;523 delete[] dualSolution_;524 delete[] lower_;525 delete[] upper_;526 delete[] pivotVariables_;527 delete[] fixed_;501 ClpNode::~ClpNode() 502 { 503 delete factorization_; 504 delete weights_; 505 delete[] status_; 506 delete[] primalSolution_; 507 delete[] dualSolution_; 508 delete[] lower_; 509 delete[] upper_; 510 delete[] pivotVariables_; 511 delete[] fixed_; 528 512 } 529 513 … … 532 516 // 533 517 ClpNode & 534 ClpNode::operator=(const ClpNode &rhs)535 { 536 537 538 539 540 518 ClpNode::operator=(const ClpNode &rhs) 519 { 520 if (this != &rhs) { 521 printf("ClpNode = not implemented\n"); 522 abort(); 523 } 524 return *this; 541 525 } 542 526 // Create odd arrays 543 void 544 ClpNode::createArrays(ClpSimplex * model) 545 { 546 int numberColumns = model>numberColumns(); 547 const char * integerType = model>integerInformation(); 548 int iColumn; 549 int numberIntegers = 0; 550 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 551 if (integerType[iColumn]) 552 numberIntegers++; 553 } 554 if (numberIntegers > maximumIntegers_  !lower_) { 555 delete [] lower_; 556 delete [] upper_; 557 maximumIntegers_ = numberIntegers; 558 lower_ = new int [numberIntegers]; 559 upper_ = new int [numberIntegers]; 560 } 527 void ClpNode::createArrays(ClpSimplex *model) 528 { 529 int numberColumns = model>numberColumns(); 530 const char *integerType = model>integerInformation(); 531 int iColumn; 532 int numberIntegers = 0; 533 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 534 if (integerType[iColumn]) 535 numberIntegers++; 536 } 537 if (numberIntegers > maximumIntegers_  !lower_) { 538 delete[] lower_; 539 delete[] upper_; 540 maximumIntegers_ = numberIntegers; 541 lower_ = new int[numberIntegers]; 542 upper_ = new int[numberIntegers]; 543 } 561 544 } 562 545 // Clean up as crunch is different model 563 void 564 ClpNode::cleanUpForCrunch() 565 { 566 delete weights_; 567 weights_ = NULL; 546 void ClpNode::cleanUpForCrunch() 547 { 548 delete weights_; 549 weights_ = NULL; 568 550 } 569 551 /* Applies node to model … … 572 554 2  saved bounds and basis etc 573 555 */ 574 void 575 ClpNode::applyNode(ClpSimplex * model, int doBoundsEtc ) 576 { 577 int numberColumns = model>numberColumns(); 578 const double * lower = model>columnLower(); 579 const double * upper = model>columnUpper(); 580 if (doBoundsEtc < 2) { 581 // current bound 582 int way = branchState_.firstBranch; 583 if (branchState_.branch > 0) 584 way = 1  way; 585 if (!way) { 586 // This should also do underlying internal bound 587 model>setColumnUpper(sequence_, floor(branchingValue_)); 588 } else { 589 // This should also do underlying internal bound 590 model>setColumnLower(sequence_, ceil(branchingValue_)); 591 } 592 // apply dj fixings 593 for (int i = 0; i < numberFixed_; i++) { 594 int iColumn = fixed_[i]; 595 if ((iColumn & 0x10000000) != 0) { 596 iColumn &= 0xfffffff; 597 model>setColumnLower(iColumn, upper[iColumn]); 598 } else { 599 model>setColumnUpper(iColumn, lower[iColumn]); 600 } 601 } 602 } else { 603 // restore bounds 604 assert (lower_); 605 int iInteger = 1; 606 const char * integerType = model>integerInformation(); 607 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 608 if (integerType[iColumn]) { 609 iInteger++; 610 if (lower_[iInteger] != static_cast<int> (lower[iColumn])) 611 model>setColumnLower(iColumn, lower_[iInteger]); 612 if (upper_[iInteger] != static_cast<int> (upper[iColumn])) 613 model>setColumnUpper(iColumn, upper_[iInteger]); 614 } 615 } 616 } 617 if (doBoundsEtc && doBoundsEtc < 3) { 618 //model>copyFactorization(*factorization_); 619 model>copyFactorization(*factorization_); 620 ClpDualRowSteepest* pivot = 621 dynamic_cast< ClpDualRowSteepest*>(model>dualRowPivot()); 622 if (pivot && weights_) { 623 pivot>fill(*weights_); 624 } 625 int numberRows = model>numberRows(); 626 int numberTotal = numberRows + numberColumns; 627 CoinMemcpyN(status_, numberTotal, model>statusArray()); 628 if (doBoundsEtc < 2) { 629 CoinMemcpyN(primalSolution_, numberTotal, model>solutionRegion()); 630 CoinMemcpyN(dualSolution_, numberTotal, model>djRegion()); 631 CoinMemcpyN(pivotVariables_, numberRows, model>pivotVariable()); 632 CoinMemcpyN(dualSolution_ + numberColumns, numberRows, model>dualRowSolution()); 633 } else { 634 CoinMemcpyN(primalSolution_, numberColumns, model>primalColumnSolution()); 635 CoinMemcpyN(dualSolution_, numberColumns, model>dualColumnSolution()); 636 CoinMemcpyN(dualSolution_ + numberColumns, numberRows, model>dualRowSolution()); 637 if (model>columnScale()) { 638 // See if just primal will work 639 double * solution = model>primalColumnSolution(); 640 const double * columnScale = model>columnScale(); 641 int i; 642 for (i = 0; i < numberColumns; i++) { 643 solution[i] *= columnScale[i]; 644 } 645 } 646 } 647 model>setObjectiveValue(objectiveValue_); 648 } 556 void ClpNode::applyNode(ClpSimplex *model, int doBoundsEtc) 557 { 558 int numberColumns = model>numberColumns(); 559 const double *lower = model>columnLower(); 560 const double *upper = model>columnUpper(); 561 if (doBoundsEtc < 2) { 562 // current bound 563 int way = branchState_.firstBranch; 564 if (branchState_.branch > 0) 565 way = 1  way; 566 if (!way) { 567 // This should also do underlying internal bound 568 model>setColumnUpper(sequence_, floor(branchingValue_)); 569 } else { 570 // This should also do underlying internal bound 571 model>setColumnLower(sequence_, ceil(branchingValue_)); 572 } 573 // apply dj fixings 574 for (int i = 0; i < numberFixed_; i++) { 575 int iColumn = fixed_[i]; 576 if ((iColumn & 0x10000000) != 0) { 577 iColumn &= 0xfffffff; 578 model>setColumnLower(iColumn, upper[iColumn]); 579 } else { 580 model>setColumnUpper(iColumn, lower[iColumn]); 581 } 582 } 583 } else { 584 // restore bounds 585 assert(lower_); 586 int iInteger = 1; 587 const char *integerType = model>integerInformation(); 588 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 589 if (integerType[iColumn]) { 590 iInteger++; 591 if (lower_[iInteger] != static_cast< int >(lower[iColumn])) 592 model>setColumnLower(iColumn, lower_[iInteger]); 593 if (upper_[iInteger] != static_cast< int >(upper[iColumn])) 594 model>setColumnUpper(iColumn, upper_[iInteger]); 595 } 596 } 597 } 598 if (doBoundsEtc && doBoundsEtc < 3) { 599 //model>copyFactorization(*factorization_); 600 model>copyFactorization(*factorization_); 601 ClpDualRowSteepest *pivot = dynamic_cast< ClpDualRowSteepest * >(model>dualRowPivot()); 602 if (pivot && weights_) { 603 pivot>fill(*weights_); 604 } 605 int numberRows = model>numberRows(); 606 int numberTotal = numberRows + numberColumns; 607 CoinMemcpyN(status_, numberTotal, model>statusArray()); 608 if (doBoundsEtc < 2) { 609 CoinMemcpyN(primalSolution_, numberTotal, model>solutionRegion()); 610 CoinMemcpyN(dualSolution_, numberTotal, model>djRegion()); 611 CoinMemcpyN(pivotVariables_, numberRows, model>pivotVariable()); 612 CoinMemcpyN(dualSolution_ + numberColumns, numberRows, model>dualRowSolution()); 613 } else { 614 CoinMemcpyN(primalSolution_, numberColumns, model>primalColumnSolution()); 615 CoinMemcpyN(dualSolution_, numberColumns, model>dualColumnSolution()); 616 CoinMemcpyN(dualSolution_ + numberColumns, numberRows, model>dualRowSolution()); 617 if (model>columnScale()) { 618 // See if just primal will work 619 double *solution = model>primalColumnSolution(); 620 const double *columnScale = model>columnScale(); 621 int i; 622 for (i = 0; i < numberColumns; i++) { 623 solution[i] *= columnScale[i]; 624 } 625 } 626 } 627 model>setObjectiveValue(objectiveValue_); 628 } 649 629 } 650 630 // Choose a new variable 651 void 652 ClpNode::chooseVariable(ClpSimplex * , ClpNodeStuff * /*info*/) 631 void ClpNode::chooseVariable(ClpSimplex *, ClpNodeStuff * /*info*/) 653 632 { 654 633 #if 0 … … 662 641 } 663 642 // Fix on reduced costs 664 int 665 ClpNode::fixOnReducedCosts(ClpSimplex * ) 666 { 667 668 return 0; 643 int ClpNode::fixOnReducedCosts(ClpSimplex *) 644 { 645 646 return 0; 669 647 } 670 648 /* Way for integer variable 1 down , +1 up */ 671 int 672 ClpNode::way() const 673 { 674 int way = branchState_.firstBranch; 675 if (branchState_.branch > 0) 676 way = 1  way; 677 return way == 0 ? 1 : +1; 649 int ClpNode::way() const 650 { 651 int way = branchState_.firstBranch; 652 if (branchState_.branch > 0) 653 way = 1  way; 654 return way == 0 ? 1 : +1; 678 655 } 679 656 // Return true if branch exhausted 680 bool 681 ClpNode::fathomed() const 682 { 683 return branchState_.branch >= 1 684 ; 657 bool ClpNode::fathomed() const 658 { 659 return branchState_.branch >= 1; 685 660 } 686 661 // Change state of variable i.e. go other way 687 void 688 ClpNode::changeState() 689 { 690 branchState_.branch++; 691 assert (branchState_.branch <= 2); 662 void ClpNode::changeState() 663 { 664 branchState_.branch++; 665 assert(branchState_.branch <= 2); 692 666 } 693 667 //############################################################################# … … 698 672 // Default Constructor 699 673 // 700 ClpNodeStuff::ClpNodeStuff () : 701 integerTolerance_(1.0e7), 702 integerIncrement_(1.0e8), 703 smallChange_(1.0e8), 704 downPseudo_(NULL), 705 upPseudo_(NULL), 706 priority_(NULL), 707 numberDown_(NULL), 708 numberUp_(NULL), 709 numberDownInfeasible_(NULL), 710 numberUpInfeasible_(NULL), 711 saveCosts_(NULL), 712 nodeInfo_(NULL), 713 large_(NULL), 714 whichRow_(NULL), 715 whichColumn_(NULL), 674 ClpNodeStuff::ClpNodeStuff() 675 : integerTolerance_(1.0e7) 676 , integerIncrement_(1.0e8) 677 , smallChange_(1.0e8) 678 , downPseudo_(NULL) 679 , upPseudo_(NULL) 680 , priority_(NULL) 681 , numberDown_(NULL) 682 , numberUp_(NULL) 683 , numberDownInfeasible_(NULL) 684 , numberUpInfeasible_(NULL) 685 , saveCosts_(NULL) 686 , nodeInfo_(NULL) 687 , large_(NULL) 688 , whichRow_(NULL) 689 , whichColumn_(NULL) 690 , 716 691 #ifndef NO_FATHOM_PRINT 717 handler_(NULL), 718 #endif 719 nBound_(0), 720 saveOptions_(0), 721 solverOptions_(0), 722 maximumNodes_(0), 723 numberBeforeTrust_(0), 724 stateOfSearch_(0), 725 nDepth_(1), 726 nNodes_(0), 727 numberNodesExplored_(0), 728 numberIterations_(0), 729 presolveType_(0) 692 handler_(NULL) 693 , 694 #endif 695 nBound_(0) 696 , saveOptions_(0) 697 , solverOptions_(0) 698 , maximumNodes_(0) 699 , numberBeforeTrust_(0) 700 , stateOfSearch_(0) 701 , nDepth_(1) 702 , nNodes_(0) 703 , numberNodesExplored_(0) 704 , numberIterations_(0) 705 , presolveType_(0) 730 706 #ifndef NO_FATHOM_PRINT 731 ,startingDepth_(1), 732 nodeCalled_(1) 733 #endif 734 { 735 707 , startingDepth_(1) 708 , nodeCalled_(1) 709 #endif 710 { 736 711 } 737 712 … … 739 714 // Copy constructor 740 715 // 741 ClpNodeStuff::ClpNodeStuff (const ClpNodeStuff & rhs) 742 : integerTolerance_(rhs.integerTolerance_), 743 integerIncrement_(rhs.integerIncrement_), 744 smallChange_(rhs.smallChange_), 745 downPseudo_(NULL), 746 upPseudo_(NULL), 747 priority_(NULL), 748 numberDown_(NULL), 749 numberUp_(NULL), 750 numberDownInfeasible_(NULL), 751 numberUpInfeasible_(NULL), 752 saveCosts_(NULL), 753 nodeInfo_(NULL), 754 large_(NULL), 755 whichRow_(NULL), 756 whichColumn_(NULL), 716 ClpNodeStuff::ClpNodeStuff(const ClpNodeStuff &rhs) 717 : integerTolerance_(rhs.integerTolerance_) 718 , integerIncrement_(rhs.integerIncrement_) 719 , smallChange_(rhs.smallChange_) 720 , downPseudo_(NULL) 721 , upPseudo_(NULL) 722 , priority_(NULL) 723 , numberDown_(NULL) 724 , numberUp_(NULL) 725 , numberDownInfeasible_(NULL) 726 , numberUpInfeasible_(NULL) 727 , saveCosts_(NULL) 728 , nodeInfo_(NULL) 729 , large_(NULL) 730 , whichRow_(NULL) 731 , whichColumn_(NULL) 732 , 757 733 #ifndef NO_FATHOM_PRINT 758 handler_(rhs.handler_), 759 #endif 760 nBound_(0), 761 saveOptions_(rhs.saveOptions_), 762 solverOptions_(rhs.solverOptions_), 763 maximumNodes_(rhs.maximumNodes_), 764 numberBeforeTrust_(rhs.numberBeforeTrust_), 765 stateOfSearch_(rhs.stateOfSearch_), 766 nDepth_(rhs.nDepth_), 767 nNodes_(rhs.nNodes_), 768 numberNodesExplored_(rhs.numberNodesExplored_), 769 numberIterations_(rhs.numberIterations_), 770 presolveType_(rhs.presolveType_) 734 handler_(rhs.handler_) 735 , 736 #endif 737 nBound_(0) 738 , saveOptions_(rhs.saveOptions_) 739 , solverOptions_(rhs.solverOptions_) 740 , maximumNodes_(rhs.maximumNodes_) 741 , numberBeforeTrust_(rhs.numberBeforeTrust_) 742 , stateOfSearch_(rhs.stateOfSearch_) 743 , nDepth_(rhs.nDepth_) 744 , nNodes_(rhs.nNodes_) 745 , numberNodesExplored_(rhs.numberNodesExplored_) 746 , numberIterations_(rhs.numberIterations_) 747 , presolveType_(rhs.presolveType_) 771 748 #ifndef NO_FATHOM_PRINT 772 ,startingDepth_(rhs.startingDepth_),773 749 , startingDepth_(rhs.startingDepth_) 750 , nodeCalled_(rhs.nodeCalled_) 774 751 #endif 775 752 { … … 779 756 // 780 757 ClpNodeStuff & 781 ClpNodeStuff::operator=(const ClpNodeStuff &rhs)782 { 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 delete[] nodeInfo_;811 812 813 814 815 816 758 ClpNodeStuff::operator=(const ClpNodeStuff &rhs) 759 { 760 if (this != &rhs) { 761 integerTolerance_ = rhs.integerTolerance_; 762 integerIncrement_ = rhs.integerIncrement_; 763 smallChange_ = rhs.smallChange_; 764 downPseudo_ = NULL; 765 upPseudo_ = NULL; 766 priority_ = NULL; 767 numberDown_ = NULL; 768 numberUp_ = NULL; 769 numberDownInfeasible_ = NULL; 770 numberUpInfeasible_ = NULL; 771 saveCosts_ = NULL; 772 nodeInfo_ = NULL; 773 large_ = NULL; 774 whichRow_ = NULL; 775 whichColumn_ = NULL; 776 nBound_ = 0; 777 saveOptions_ = rhs.saveOptions_; 778 solverOptions_ = rhs.solverOptions_; 779 maximumNodes_ = rhs.maximumNodes_; 780 numberBeforeTrust_ = rhs.numberBeforeTrust_; 781 stateOfSearch_ = rhs.stateOfSearch_; 782 int n = maximumNodes(); 783 if (n) { 784 for (int i = 0; i < n; i++) 785 delete nodeInfo_[i]; 786 } 787 delete[] nodeInfo_; 788 nodeInfo_ = NULL; 789 nDepth_ = rhs.nDepth_; 790 nNodes_ = rhs.nNodes_; 791 numberNodesExplored_ = rhs.numberNodesExplored_; 792 numberIterations_ = rhs.numberIterations_; 793 presolveType_ = rhs.presolveType_; 817 794 #ifndef NO_FATHOM_PRINT 818 819 820 821 #endif 822 823 795 handler_ = rhs.handler_; 796 startingDepth_ = rhs.startingDepth_; 797 nodeCalled_ = rhs.nodeCalled_; 798 #endif 799 } 800 return *this; 824 801 } 825 802 // Zaps stuff 1  arrays, 2 ints, 3 both 826 void 827 ClpNodeStuff::zap(int type) 828 { 829 if ((type & 1) != 0) { 830 downPseudo_ = NULL; 831 upPseudo_ = NULL; 832 priority_ = NULL; 833 numberDown_ = NULL; 834 numberUp_ = NULL; 835 numberDownInfeasible_ = NULL; 836 numberUpInfeasible_ = NULL; 837 saveCosts_ = NULL; 838 nodeInfo_ = NULL; 839 large_ = NULL; 840 whichRow_ = NULL; 841 whichColumn_ = NULL; 842 } 843 if ((type & 2) != 0) { 844 nBound_ = 0; 845 saveOptions_ = 0; 846 solverOptions_ = 0; 847 maximumNodes_ = 0; 848 numberBeforeTrust_ = 0; 849 stateOfSearch_ = 0; 850 nDepth_ = 1; 851 nNodes_ = 0; 852 presolveType_ = 0; 853 numberNodesExplored_ = 0; 854 numberIterations_ = 0; 855 } 803 void ClpNodeStuff::zap(int type) 804 { 805 if ((type & 1) != 0) { 806 downPseudo_ = NULL; 807 upPseudo_ = NULL; 808 priority_ = NULL; 809 numberDown_ = NULL; 810 numberUp_ = NULL; 811 numberDownInfeasible_ = NULL; 812 numberUpInfeasible_ = NULL; 813 saveCosts_ = NULL; 814 nodeInfo_ = NULL; 815 large_ = NULL; 816 whichRow_ = NULL; 817 whichColumn_ = NULL; 818 } 819 if ((type & 2) != 0) { 820 nBound_ = 0; 821 saveOptions_ = 0; 822 solverOptions_ = 0; 823 maximumNodes_ = 0; 824 numberBeforeTrust_ = 0; 825 stateOfSearch_ = 0; 826 nDepth_ = 1; 827 nNodes_ = 0; 828 presolveType_ = 0; 829 numberNodesExplored_ = 0; 830 numberIterations_ = 0; 831 } 856 832 } 857 833 … … 859 835 // Destructor 860 836 // 861 ClpNodeStuff::~ClpNodeStuff 862 { 863 delete[] downPseudo_;864 delete[] upPseudo_;865 delete[] priority_;866 delete[] numberDown_;867 delete[] numberUp_;868 delete[] numberDownInfeasible_;869 delete[] numberUpInfeasible_;870 871 872 873 874 875 delete[] nodeInfo_;837 ClpNodeStuff::~ClpNodeStuff() 838 { 839 delete[] downPseudo_; 840 delete[] upPseudo_; 841 delete[] priority_; 842 delete[] numberDown_; 843 delete[] numberUp_; 844 delete[] numberDownInfeasible_; 845 delete[] numberUpInfeasible_; 846 int n = maximumNodes(); 847 if (n) { 848 for (int i = 0; i < n; i++) 849 delete nodeInfo_[i]; 850 } 851 delete[] nodeInfo_; 876 852 #ifdef CLP_INVESTIGATE 877 878 assert(!saveCosts_);879 #endif 880 delete[] saveCosts_;853 // Should be NULL  find out why not? 854 assert(!saveCosts_); 855 #endif 856 delete[] saveCosts_; 881 857 } 882 858 // Return maximum number of nodes 883 int 884 ClpNodeStuff::maximumNodes() const 885 { 886 int n = 0; 859 int ClpNodeStuff::maximumNodes() const 860 { 861 int n = 0; 887 862 #if 0 888 863 if (nDepth_ != 1) { … … 894 869 assert (n == maximumNodes_  (1 + nDepth_)  n == 0); 895 870 #else 896 897 898 assert(n > 0);899 900 #endif 901 871 if (nDepth_ != 1) { 872 n = maximumNodes_  (1 + nDepth_); 873 assert(n > 0); 874 } 875 #endif 876 return n; 902 877 } 903 878 // Return maximum space for nodes 904 int 905 ClpNodeStuff::maximumSpace() const 906 { 907 return maximumNodes_; 879 int ClpNodeStuff::maximumSpace() const 880 { 881 return maximumNodes_; 908 882 } 909 883 /* Fill with pseudocosts */ 910 void 911 ClpNodeStuff::fillPseudoCosts(const double * down, const double * up, 912 const int * priority, 913 const int * numberDown, const int * numberUp, 914 const int * numberDownInfeasible, 915 const int * numberUpInfeasible, 916 int number) 917 { 918 delete [] downPseudo_; 919 delete [] upPseudo_; 920 delete [] priority_; 921 delete [] numberDown_; 922 delete [] numberUp_; 923 delete [] numberDownInfeasible_; 924 delete [] numberUpInfeasible_; 925 downPseudo_ = CoinCopyOfArray(down, number); 926 upPseudo_ = CoinCopyOfArray(up, number); 927 priority_ = CoinCopyOfArray(priority, number); 928 numberDown_ = CoinCopyOfArray(numberDown, number); 929 numberUp_ = CoinCopyOfArray(numberUp, number); 930 numberDownInfeasible_ = CoinCopyOfArray(numberDownInfeasible, number); 931 numberUpInfeasible_ = CoinCopyOfArray(numberUpInfeasible, number); 932 // scale 933 for (int i = 0; i < number; i++) { 934 int n; 935 n = numberDown_[i]; 936 if (n) 937 downPseudo_[i] *= n; 938 n = numberUp_[i]; 939 if (n) 940 upPseudo_[i] *= n; 941 } 884 void ClpNodeStuff::fillPseudoCosts(const double *down, const double *up, 885 const int *priority, 886 const int *numberDown, const int *numberUp, 887 const int *numberDownInfeasible, 888 const int *numberUpInfeasible, 889 int number) 890 { 891 delete[] downPseudo_; 892 delete[] upPseudo_; 893 delete[] priority_; 894 delete[] numberDown_; 895 delete[] numberUp_; 896 delete[] numberDownInfeasible_; 897 delete[] numberUpInfeasible_; 898 downPseudo_ = CoinCopyOfArray(down, number); 899 upPseudo_ = CoinCopyOfArray(up, number); 900 priority_ = CoinCopyOfArray(priority, number); 901 numberDown_ = CoinCopyOfArray(numberDown, number); 902 numberUp_ = CoinCopyOfArray(numberUp, number); 903 numberDownInfeasible_ = CoinCopyOfArray(numberDownInfeasible, number); 904 numberUpInfeasible_ = CoinCopyOfArray(numberUpInfeasible, number); 905 // scale 906 for (int i = 0; i < number; i++) { 907 int n; 908 n = numberDown_[i]; 909 if (n) 910 downPseudo_[i] *= n; 911 n = numberUp_[i]; 912 if (n) 913 upPseudo_[i] *= n; 914 } 942 915 } 943 916 // Update pseudo costs 944 void 945 ClpNodeStuff::update(int way, int sequence, double change, bool feasible) 946 { 947 assert (numberDown_[sequence] >= numberDownInfeasible_[sequence]); 948 assert (numberUp_[sequence] >= numberUpInfeasible_[sequence]); 949 if (way < 0) { 950 numberDown_[sequence]++; 951 if (!feasible) 952 numberDownInfeasible_[sequence]++; 953 downPseudo_[sequence] += CoinMax(change, 1.0e12); 954 } else { 955 numberUp_[sequence]++; 956 if (!feasible) 957 numberUpInfeasible_[sequence]++; 958 upPseudo_[sequence] += CoinMax(change, 1.0e12); 959 } 917 void ClpNodeStuff::update(int way, int sequence, double change, bool feasible) 918 { 919 assert(numberDown_[sequence] >= numberDownInfeasible_[sequence]); 920 assert(numberUp_[sequence] >= numberUpInfeasible_[sequence]); 921 if (way < 0) { 922 numberDown_[sequence]++; 923 if (!feasible) 924 numberDownInfeasible_[sequence]++; 925 downPseudo_[sequence] += CoinMax(change, 1.0e12); 926 } else { 927 numberUp_[sequence]++; 928 if (!feasible) 929 numberUpInfeasible_[sequence]++; 930 upPseudo_[sequence] += CoinMax(change, 1.0e12); 931 } 960 932 } 961 933 //############################################################################# … … 966 938 // Default Constructor 967 939 // 968 ClpHashValue::ClpHashValue () :969 hash_(NULL),970 numberHash_(0),971 maxHash_(0),972 940 ClpHashValue::ClpHashValue() 941 : hash_(NULL) 942 , numberHash_(0) 943 , maxHash_(0) 944 , lastUsed_(1) 973 945 { 974 946 } … … 976 948 // Useful Constructor from model 977 949 // 978 ClpHashValue::ClpHashValue (ClpSimplex * model) :979 hash_(NULL),980 numberHash_(0),981 maxHash_(0),982 983 { 984 985 986 const double *columnLower = model>columnLower();987 const double *columnUpper = model>columnUpper();988 989 const double *rowLower = model>rowLower();990 const double *rowUpper = model>rowUpper();991 const double *objective = model>objective();992 CoinPackedMatrix *matrix = model>matrix();993 const int *columnLength = matrix>getVectorLengths();994 const CoinBigIndex *columnStart = matrix>getVectorStarts();995 const double *elementByColumn = matrix>getElements();996 997 998 999 1000 1001 for ( i = 0; i < maxHash_; i++) {1002 1003 1004 1005 1006 1007 1008 1009 1010 950 ClpHashValue::ClpHashValue(ClpSimplex *model) 951 : hash_(NULL) 952 , numberHash_(0) 953 , maxHash_(0) 954 , lastUsed_(1) 955 { 956 maxHash_ = 1000; 957 int numberColumns = model>numberColumns(); 958 const double *columnLower = model>columnLower(); 959 const double *columnUpper = model>columnUpper(); 960 int numberRows = model>numberRows(); 961 const double *rowLower = model>rowLower(); 962 const double *rowUpper = model>rowUpper(); 963 const double *objective = model>objective(); 964 CoinPackedMatrix *matrix = model>matrix(); 965 const int *columnLength = matrix>getVectorLengths(); 966 const CoinBigIndex *columnStart = matrix>getVectorStarts(); 967 const double *elementByColumn = matrix>getElements(); 968 int i; 969 int ipos; 970 971 hash_ = new CoinHashLink[maxHash_]; 972 973 for (i = 0; i < maxHash_; i++) { 974 hash_[i].value = 1.0e100; 975 hash_[i].index = 1; 976 hash_[i].next = 1; 977 } 978 // Put in +0 979 hash_[0].value = 0.0; 980 hash_[0].index = 0; 981 numberHash_ = 1; 982 /* 1011 983 * Initialize the hash table. Only the index of the first value that 1012 984 * hashes to a value is entered in the table; subsequent values that 1013 985 * collide with it are not entered. 1014 986 */ 1015 for ( i = 0; i < numberColumns; i++) {1016 1017 1018 1019 1020 ipos = hash (value);1021 if ( hash_[ipos].index == 1) {1022 1023 1024 1025 1026 1027 1028 1029 987 for (i = 0; i < numberColumns; i++) { 988 int length = columnLength[i]; 989 CoinBigIndex start = columnStart[i]; 990 for (CoinBigIndex i = start; i < start + length; i++) { 991 double value = elementByColumn[i]; 992 ipos = hash(value); 993 if (hash_[ipos].index == 1) { 994 hash_[ipos].index = numberHash_; 995 numberHash_++; 996 hash_[ipos].value = elementByColumn[i]; 997 } 998 } 999 } 1000 1001 /* 1030 1002 * Now take care of the values that collided in the preceding loop, 1031 1003 * Also do other stuff 1032 1004 */ 1033 for ( i = 0; i < numberRows; i++) {1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 for ( i = 0; i < numberColumns; i++) {1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1005 for (i = 0; i < numberRows; i++) { 1006 if (numberHash_ * 2 > maxHash_) 1007 resize(true); 1008 double value; 1009 value = rowLower[i]; 1010 ipos = index(value); 1011 if (ipos < 0) 1012 addValue(value); 1013 value = rowUpper[i]; 1014 ipos = index(value); 1015 if (ipos < 0) 1016 addValue(value); 1017 } 1018 for (i = 0; i < numberColumns; i++) { 1019 int length = columnLength[i]; 1020 CoinBigIndex start = columnStart[i]; 1021 if (numberHash_ * 2 > maxHash_) 1022 resize(true); 1023 double value; 1024 value = objective[i]; 1025 ipos = index(value); 1026 if (ipos < 0) 1027 addValue(value); 1028 value = columnLower[i]; 1029 ipos = index(value); 1030 if (ipos < 0) 1031 addValue(value); 1032 value = columnUpper[i]; 1033 ipos = index(value); 1034 if (ipos < 0) 1035 addValue(value); 1036 for (CoinBigIndex j = start; j < start + length; j++) { 1037 if (numberHash_ * 2 > maxHash_) 1038 resize(true); 1039 value = elementByColumn[j]; 1040 ipos = index(value); 1041 if (ipos < 0) 1042 addValue(value); 1043 } 1044 } 1045 resize(false); 1074 1046 } 1075 1047 … … 1077 1049 // Copy constructor 1078 1050 // 1079 ClpHashValue::ClpHashValue (const ClpHashValue & rhs) :1080 hash_(NULL),1081 numberHash_(rhs.numberHash_),1082 maxHash_(rhs.maxHash_),1083 1084 { 1085 1086 CoinHashLink *newHash = new CoinHashLink[maxHash_];1087 1088 for ( i = 0; i < maxHash_; i++) {1089 1090 1091 1092 1093 1051 ClpHashValue::ClpHashValue(const ClpHashValue &rhs) 1052 : hash_(NULL) 1053 , numberHash_(rhs.numberHash_) 1054 , maxHash_(rhs.maxHash_) 1055 , lastUsed_(rhs.lastUsed_) 1056 { 1057 if (maxHash_) { 1058 CoinHashLink *newHash = new CoinHashLink[maxHash_]; 1059 int i; 1060 for (i = 0; i < maxHash_; i++) { 1061 newHash[i].value = rhs.hash_[i].value; 1062 newHash[i].index = rhs.hash_[i].index; 1063 newHash[i].next = rhs.hash_[i].next; 1064 } 1065 } 1094 1066 } 1095 1067 … … 1097 1069 // Destructor 1098 1070 // 1099 ClpHashValue::~ClpHashValue 1100 { 1101 delete[] hash_;1071 ClpHashValue::~ClpHashValue() 1072 { 1073 delete[] hash_; 1102 1074 } 1103 1075 … … 1106 1078 // 1107 1079 ClpHashValue & 1108 ClpHashValue::operator=(const ClpHashValue &rhs)1109 { 1110 1111 1112 1113 1114 delete[] hash_;1115 1116 CoinHashLink *newHash = new CoinHashLink[maxHash_];1117 1118 for ( i = 0; i < maxHash_; i++) {1119 1120 1121 1122 1123 1124 1125 1126 1127 1080 ClpHashValue::operator=(const ClpHashValue &rhs) 1081 { 1082 if (this != &rhs) { 1083 numberHash_ = rhs.numberHash_; 1084 maxHash_ = rhs.maxHash_; 1085 lastUsed_ = rhs.lastUsed_; 1086 delete[] hash_; 1087 if (maxHash_) { 1088 CoinHashLink *newHash = new CoinHashLink[maxHash_]; 1089 int i; 1090 for (i = 0; i < maxHash_; i++) { 1091 newHash[i].value = rhs.hash_[i].value; 1092 newHash[i].index = rhs.hash_[i].index; 1093 newHash[i].next = rhs.hash_[i].next; 1094 } 1095 } else { 1096 hash_ = NULL; 1097 } 1098 } 1099 return *this; 1128 1100 } 1129 1101 // Return index or 1 if not found 1130 int 1131 ClpHashValue::index(double value) const 1132 { 1133 if (!value) 1134 return 0; 1135 int ipos = hash ( value); 1136 int returnCode = 1; 1137 while ( hash_[ipos].index >= 0 ) { 1138 if (value == hash_[ipos].value) { 1139 returnCode = hash_[ipos].index; 1140 break; 1141 } else { 1142 int k = hash_[ipos].next; 1143 if ( k == 1 ) { 1144 break; 1145 } else { 1146 ipos = k; 1147 } 1148 } 1149 } 1150 return returnCode; 1102 int ClpHashValue::index(double value) const 1103 { 1104 if (!value) 1105 return 0; 1106 int ipos = hash(value); 1107 int returnCode = 1; 1108 while (hash_[ipos].index >= 0) { 1109 if (value == hash_[ipos].value) { 1110 returnCode = hash_[ipos].index; 1111 break; 1112 } else { 1113 int k = hash_[ipos].next; 1114 if (k == 1) { 1115 break; 1116 } else { 1117 ipos = k; 1118 } 1119 } 1120 } 1121 return returnCode; 1151 1122 } 1152 1123 // Add value to list and return index 1153 int 1154 ClpHashValue::addValue(double value) 1155 { 1156 int ipos = hash ( value); 1157 1158 assert (value != hash_[ipos].value); 1159 if (hash_[ipos].index == 1) { 1160 // can put in here 1161 hash_[ipos].index = numberHash_; 1162 numberHash_++; 1163 hash_[ipos].value = value; 1164 return numberHash_  1; 1165 } 1166 int k = hash_[ipos].next; 1167 while (k != 1) { 1168 ipos = k; 1169 k = hash_[ipos].next; 1170 } 1171 while ( true ) { 1172 ++lastUsed_; 1173 assert (lastUsed_ <= maxHash_); 1174 if ( hash_[lastUsed_].index == 1 ) { 1175 break; 1176 } 1177 } 1178 hash_[ipos].next = lastUsed_; 1179 hash_[lastUsed_].index = numberHash_; 1180 numberHash_++; 1181 hash_[lastUsed_].value = value; 1182 return numberHash_  1; 1124 int ClpHashValue::addValue(double value) 1125 { 1126 int ipos = hash(value); 1127 1128 assert(value != hash_[ipos].value); 1129 if (hash_[ipos].index == 1) { 1130 // can put in here 1131 hash_[ipos].index = numberHash_; 1132 numberHash_++; 1133 hash_[ipos].value = value; 1134 return numberHash_  1; 1135 } 1136 int k = hash_[ipos].next; 1137 while (k != 1) { 1138 ipos = k; 1139 k = hash_[ipos].next; 1140 } 1141 while (true) { 1142 ++lastUsed_; 1143 assert(lastUsed_ <= maxHash_); 1144 if (hash_[lastUsed_].index == 1) { 1145 break; 1146 } 1147 } 1148 hash_[ipos].next = lastUsed_; 1149 hash_[lastUsed_].index = numberHash_; 1150 numberHash_++; 1151 hash_[lastUsed_].value = value; 1152 return numberHash_  1; 1183 1153 } 1184 1154 1185 1155 namespace { 1186 1156 /* 1187 1157 Originally a local static variable in ClpHashValue::hash. 1188 1158 Local static variables are a problem when building DLLs on Windows, but 1189 1159 filelocal constants seem to be ok.  lh, 101016  1190 1160 */ 1191 const int mmult_for_hash[] = { 1192 262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247, 1193 241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829, 1194 221281, 218849, 216319, 213721, 211093, 208673, 206263, 203773, 1195 201233, 198637, 196159, 193603, 191161, 188701, 186149, 183761, 1196 181303, 178873, 176389, 173897, 171469, 169049, 166471, 163871, 1197 161387, 158941, 156437, 153949, 151531, 149159, 146749, 144299, 1198 141709, 139369, 136889, 134591, 132169, 129641, 127343, 124853, 1199 122477, 120163, 117757, 115361, 112979, 110567, 108179, 105727, 1200 103387, 101021, 98639, 96179, 93911, 91583, 89317, 86939, 84521, 1201 82183, 79939, 77587, 75307, 72959, 70793, 68447, 66103 1202 }; 1203 } 1204 int 1205 ClpHashValue::hash ( double value) const 1206 { 1207 1208 union { 1209 double d; 1210 char c[8]; 1211 } v1; 1212 assert (sizeof(double) == 8); 1213 v1.d = value; 1214 int n = 0; 1215 int j; 1216 1217 for ( j = 0; j < 8; ++j ) { 1218 int ichar = v1.c[j]; 1219 n += mmult_for_hash[j] * ichar; 1220 } 1221 return ( abs ( n ) % maxHash_ ); /* integer abs */ 1222 } 1223 void 1224 ClpHashValue::resize(bool increaseMax) 1225 { 1226 int newSize = increaseMax ? ((3 * maxHash_) >> 1) + 1000 : maxHash_; 1227 CoinHashLink * newHash = new CoinHashLink[newSize]; 1228 int i; 1229 for ( i = 0; i < newSize; i++ ) { 1230 newHash[i].value = 1.0e100; 1231 newHash[i].index = 1; 1232 newHash[i].next = 1; 1233 } 1234 // swap 1235 CoinHashLink * oldHash = hash_; 1236 hash_ = newHash; 1237 int oldSize = maxHash_; 1238 maxHash_ = newSize; 1239 /* 1161 const int mmult_for_hash[] = { 1162 262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247, 1163 241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829, 1164 221281, 218849, 216319, 213721, 211093, 208673, 206263, 203773, 1165 201233, 198637, 196159, 193603, 191161, 188701, 186149, 183761, 1166 181303, 178873, 176389, 173897, 171469, 169049, 166471, 163871, 1167 161387, 158941, 156437, 153949, 151531, 149159, 146749, 144299, 1168 141709, 139369, 136889, 134591, 132169, 129641, 127343, 124853, 1169 122477, 120163, 117757, 115361, 112979, 110567, 108179, 105727, 1170 103387, 101021, 98639, 96179, 93911, 91583, 89317, 86939, 84521, 1171 82183, 79939, 77587, 75307, 72959, 70793, 68447, 66103 1172 }; 1173 } 1174 int ClpHashValue::hash(double value) const 1175 { 1176 1177 union { 1178 double d; 1179 char c[8]; 1180 } v1; 1181 assert(sizeof(double) == 8); 1182 v1.d = value; 1183 int n = 0; 1184 int j; 1185 1186 for (j = 0; j < 8; ++j) { 1187 int ichar = v1.c[j]; 1188 n += mmult_for_hash[j] * ichar; 1189 } 1190 return (abs(n) % maxHash_); /* integer abs */ 1191 } 1192 void ClpHashValue::resize(bool increaseMax) 1193 { 1194 int newSize = increaseMax ? ((3 * maxHash_) >> 1) + 1000 : maxHash_; 1195 CoinHashLink *newHash = new CoinHashLink[newSize]; 1196 int i; 1197 for (i = 0; i < newSize; i++) { 1198 newHash[i].value = 1.0e100; 1199 newHash[i].index = 1; 1200 newHash[i].next = 1; 1201 } 1202 // swap 1203 CoinHashLink *oldHash = hash_; 1204 hash_ = newHash; 1205 int oldSize = maxHash_; 1206 maxHash_ = newSize; 1207 /* 1240 1208 * Initialize the hash table. Only the index of the first value that 1241 1209 * hashes to a value is entered in the table; subsequent values that 1242 1210 * collide with it are not entered. 1243 1211 */ 1244 1245 1246 for ( i = 0; i < oldSize; i++) {1247 1248 ipos = hash (oldHash[i].value);1249 if ( hash_[ipos].index == 1) {1250 1251 1252 1253 1254 1255 1256 1257 1258 1212 int ipos; 1213 int n = 0; 1214 for (i = 0; i < oldSize; i++) { 1215 if (oldHash[i].index >= 0) { 1216 ipos = hash(oldHash[i].value); 1217 if (hash_[ipos].index == 1) { 1218 hash_[ipos].index = n; 1219 n++; 1220 hash_[ipos].value = oldHash[i].value; 1221 // unmark 1222 oldHash[i].index = 1; 1223 } 1224 } 1225 } 1226 /* 1259 1227 * Now take care of the values that collided in the preceding loop, 1260 1228 * by finding some other entry in the table for them. … … 1262 1230 * there must be room for them. 1263 1231 */ 1264 lastUsed_ = 1; 1265 for ( i = 0; i < oldSize; ++i ) { 1266 if (oldHash[i].index >= 0) { 1267 double value = oldHash[i].value; 1268 ipos = hash ( value); 1269 int k; 1270 while ( true ) { 1271 assert (value != hash_[ipos].value); 1272 k = hash_[ipos].next; 1273 if ( k == 1 ) { 1274 while ( true ) { 1275 ++lastUsed_; 1276 assert (lastUsed_ <= maxHash_); 1277 if ( hash_[lastUsed_].index == 1 ) { 1278 break; 1279 } 1280 } 1281 hash_[ipos].next = lastUsed_; 1282 hash_[lastUsed_].index = n; 1283 n++; 1284 hash_[lastUsed_].value = value; 1285 break; 1286 } else { 1287 ipos = k; 1288 } 1289 } 1232 lastUsed_ = 1; 1233 for (i = 0; i < oldSize; ++i) { 1234 if (oldHash[i].index >= 0) { 1235 double value = oldHash[i].value; 1236 ipos = hash(value); 1237 int k; 1238 while (true) { 1239 assert(value != hash_[ipos].value); 1240 k = hash_[ipos].next; 1241 if (k == 1) { 1242 while (true) { 1243 ++lastUsed_; 1244 assert(lastUsed_ <= maxHash_); 1245 if (hash_[lastUsed_].index == 1) { 1246 break; 1247 } 1290 1248 } 1291 } 1292 assert (n == numberHash_); 1293 delete [] oldHash; 1294 } 1249 hash_[ipos].next = lastUsed_; 1250 hash_[lastUsed_].index = n; 1251 n++; 1252 hash_[lastUsed_].value = value; 1253 break; 1254 } else { 1255 ipos = k; 1256 } 1257 } 1258 } 1259 } 1260 assert(n == numberHash_); 1261 delete[] oldHash; 1262 } 1263 1264 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 1265 */
Note: See TracChangeset
for help on using the changeset viewer.