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

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Clp/src/AbcDualRowDantzig.cpp
r1910 r2385 3 3 // Corporation and others, Copyright (C) 2012, FasterCoin. All Rights Reserved. 4 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 5 7 6 #include "CoinPragma.hpp" … … 22 21 // Default Constructor 23 22 // 24 AbcDualRowDantzig::AbcDualRowDantzig 25 : AbcDualRowPivot() ,26 23 AbcDualRowDantzig::AbcDualRowDantzig() 24 : AbcDualRowPivot() 25 , infeasible_(NULL) 27 26 { 28 27 type_ = 1; … … 32 31 // Copy constructor 33 32 // 34 AbcDualRowDantzig::AbcDualRowDantzig (const AbcDualRowDantzig &rhs)35 : AbcDualRowPivot(rhs) ,36 33 AbcDualRowDantzig::AbcDualRowDantzig(const AbcDualRowDantzig &rhs) 34 : AbcDualRowPivot(rhs) 35 , infeasible_(NULL) 37 36 { 38 37 model_ = rhs.model_; … … 43 42 infeasible_ = NULL; 44 43 } 45 } 44 } 46 45 } 47 46 … … 49 48 // Destructor 50 49 // 51 AbcDualRowDantzig::~AbcDualRowDantzig 50 AbcDualRowDantzig::~AbcDualRowDantzig() 52 51 { 53 52 delete infeasible_; … … 58 57 // 59 58 AbcDualRowDantzig & 60 AbcDualRowDantzig::operator=(const AbcDualRowDantzig &rhs)59 AbcDualRowDantzig::operator=(const AbcDualRowDantzig &rhs) 61 60 { 62 61 if (this != &rhs) { … … 78 77 4) restore weights 79 78 */ 80 void 81 AbcDualRowDantzig::saveWeights(AbcSimplex * model, int mode) 79 void AbcDualRowDantzig::saveWeights(AbcSimplex *model, int mode) 82 80 { 83 81 model_ = model; … … 85 83 if (mode == 1) { 86 84 // Check if size has changed 87 if (infeasible_ &&infeasible_>capacity() != numberRows) {85 if (infeasible_ && infeasible_>capacity() != numberRows) { 88 86 // size has changed  clear everything 89 87 delete infeasible_; 90 88 infeasible_ = NULL; 91 89 } 92 } else if (mode != 3 && !infeasible_) {93 94 90 } else if (mode != 3 && !infeasible_) { 91 infeasible_ = new CoinIndexedVector(); 92 infeasible_>reserve(numberRows); 95 93 } 96 94 if (mode >= 2) { … … 99 97 } 100 98 // Recompute infeasibilities 101 void 102 AbcDualRowDantzig::recomputeInfeasibilities() 99 void AbcDualRowDantzig::recomputeInfeasibilities() 103 100 { 104 101 int numberRows = model_>numberRows(); 105 102 infeasible_>clear(); 106 103 double tolerance = model_>currentPrimalTolerance(); 107 const double * 108 const double * 109 const double * 104 const double *COIN_RESTRICT solutionBasic = model_>solutionBasic(); 105 const double *COIN_RESTRICT lowerBasic = model_>lowerBasic(); 106 const double *COIN_RESTRICT upperBasic = model_>upperBasic(); 110 107 for (int iRow = 0; iRow < numberRows; iRow++) { 111 108 double value = solutionBasic[iRow]; … … 116 113 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 117 114 if (lower == upper) 118 115 value *= CLP_DUAL_FIXED_COLUMN_MULTIPLIER; // bias towards taking out fixed variables 119 116 #endif 120 117 // store in list … … 124 121 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 125 122 if (lower == upper) 126 123 value *= CLP_DUAL_FIXED_COLUMN_MULTIPLIER; // bias towards taking out fixed variables 127 124 #endif 128 125 // store in list … … 131 128 } 132 129 } 133 #if ABC_PARALLEL ==2134 static void choose(CoinIndexedVector * 135 int & chosenRowSave,double &largestSave, int first, int last,136 137 { 138 if (last first>256) {139 int mid =(last+first)>>1;140 int chosenRow2 =chosenRowSave;141 double largest2 =largestSave;142 cilk_spawn choose(infeasible, chosenRow2,largest2, first, mid,143 144 choose(infeasible, chosenRowSave,largestSave, mid, last,145 130 #if ABC_PARALLEL == 2 131 static void choose(CoinIndexedVector *infeasible, 132 int &chosenRowSave, double &largestSave, int first, int last, 133 double tolerance) 134 { 135 if (last  first > 256) { 136 int mid = (last + first) >> 1; 137 int chosenRow2 = chosenRowSave; 138 double largest2 = largestSave; 139 cilk_spawn choose(infeasible, chosenRow2, largest2, first, mid, 140 tolerance); 141 choose(infeasible, chosenRowSave, largestSave, mid, last, 142 tolerance); 146 143 cilk_sync; 147 if (largest2 >largestSave) {148 largestSave =largest2;149 chosenRowSave =chosenRow2;144 if (largest2 > largestSave) { 145 largestSave = largest2; 146 chosenRowSave = chosenRow2; 150 147 } 151 148 } else { 152 const int * index=infeasible>getIndices();153 const double * infeas=infeasible>denseVector();154 double largest =largestSave;155 int chosenRow =chosenRowSave;149 const int *index = infeasible>getIndices(); 150 const double *infeas = infeasible>denseVector(); 151 double largest = largestSave; 152 int chosenRow = chosenRowSave; 156 153 for (int i = first; i < last; i++) { 157 154 int iRow = index[i]; 158 155 double value = infeas[iRow]; 159 156 if (value > largest) { 160 largest=value;161 chosenRow=iRow;157 largest = value; 158 chosenRow = iRow; 162 159 } 163 160 } 164 chosenRowSave =chosenRow;165 largestSave =largest;161 chosenRowSave = chosenRow; 162 largestSave = largest; 166 163 } 167 164 } 168 165 #endif 169 166 // Returns pivot row, 1 if none 170 int 171 AbcDualRowDantzig::pivotRow() 167 int AbcDualRowDantzig::pivotRow() 172 168 { 173 169 assert(model_); 174 double * 175 int * 170 double *COIN_RESTRICT infeas = infeasible_>denseVector(); 171 int *COIN_RESTRICT index = infeasible_>getIndices(); 176 172 int number = infeasible_>getNumElements(); 177 173 double tolerance = model_>currentPrimalTolerance(); … … 180 176 tolerance *= model_>largestPrimalError() / 1.0e8; 181 177 int numberRows = model_>numberRows(); 182 const double * COIN_RESTRICT solutionBasic=model_>solutionBasic();183 const double * COIN_RESTRICT lowerBasic=model_>lowerBasic();184 const double * COIN_RESTRICT upperBasic=model_>upperBasic();185 const int * 178 const double *COIN_RESTRICT solutionBasic = model_>solutionBasic(); 179 const double *COIN_RESTRICT lowerBasic = model_>lowerBasic(); 180 const double *COIN_RESTRICT upperBasic = model_>upperBasic(); 181 const int *pivotVariable = model_>pivotVariable(); 186 182 // code so has list of infeasibilities (like steepest) 187 int numberWanted =CoinMax(2000,numberRows>>4);188 numberWanted =CoinMax(numberWanted,number>>2);183 int numberWanted = CoinMax(2000, numberRows >> 4); 184 numberWanted = CoinMax(numberWanted, number >> 2); 189 185 if (model_>largestPrimalError() > 1.0e3) 190 186 numberWanted = number + 1; // be safe … … 193 189 start[1] = number; 194 190 start[2] = 0; 195 double dstart = static_cast< double>(number) * model_>randomNumberGenerator()>randomDouble();196 start[0] = static_cast< int>(dstart);191 double dstart = static_cast< double >(number) * model_>randomNumberGenerator()>randomDouble(); 192 start[0] = static_cast< int >(dstart); 197 193 start[3] = start[0]; 198 194 double largest = tolerance; 199 195 int chosenRow = 1; 200 int saveNumberWanted =numberWanted;196 int saveNumberWanted = numberWanted; 201 197 #ifdef DO_REDUCE 202 bool doReduce =true;203 int lastChosen =1;204 double lastLargest =0.0;198 bool doReduce = true; 199 int lastChosen = 1; 200 double lastLargest = 0.0; 205 201 #endif 206 202 for (int iPass = 0; iPass < 2; iPass++) { 207 int endThis = start[2 *iPass+1];208 int startThis =start[2*iPass];209 while (startThis <endThis) {210 int end = CoinMin(endThis, startThis+numberWanted);211 #ifdef DO_REDUCE 203 int endThis = start[2 * iPass + 1]; 204 int startThis = start[2 * iPass]; 205 while (startThis < endThis) { 206 int end = CoinMin(endThis, startThis + numberWanted); 207 #ifdef DO_REDUCE 212 208 if (doReduce) { 213 choose(infeasible,chosenRow,largest,startThis,end,tolerance); 214 if (chosenRow!=lastChosen) { 215 assert (chosenRow>=0); 216 if (model_>flagged(pivotVariable[chosenRow]) 217 (solutionBasic[chosenRow] <= upperBasic[chosenRow] + tolerance && 218 solutionBasic[chosenRow] >= lowerBasic[chosenRow]  tolerance)) { 219 doReduce=false; 220 chosenRow=lastChosen; 221 largest=lastLargest; 222 } else { 223 lastChosen=chosenRow; 224 lastLargest=largest; 225 } 226 } 209 choose(infeasible, chosenRow, largest, startThis, end, tolerance); 210 if (chosenRow != lastChosen) { 211 assert(chosenRow >= 0); 212 if (model_>flagged(pivotVariable[chosenRow])  (solutionBasic[chosenRow] <= upperBasic[chosenRow] + tolerance && solutionBasic[chosenRow] >= lowerBasic[chosenRow]  tolerance)) { 213 doReduce = false; 214 chosenRow = lastChosen; 215 largest = lastLargest; 216 } else { 217 lastChosen = chosenRow; 218 lastLargest = largest; 219 } 220 } 227 221 } 228 222 if (!doReduce) { 229 223 #endif 230 for (int i = startThis; i < end; i++) { 231 int iRow = index[i]; 232 double value = infeas[iRow]; 233 if (value > largest) { 234 if (!model_>flagged(pivotVariable[iRow])) { 235 if (solutionBasic[iRow] > upperBasic[iRow] + tolerance  236 solutionBasic[iRow] < lowerBasic[iRow]  tolerance) { 237 chosenRow = iRow; 238 largest = value; 239 } 240 } 241 } 242 } 224 for (int i = startThis; i < end; i++) { 225 int iRow = index[i]; 226 double value = infeas[iRow]; 227 if (value > largest) { 228 if (!model_>flagged(pivotVariable[iRow])) { 229 if (solutionBasic[iRow] > upperBasic[iRow] + tolerance  solutionBasic[iRow] < lowerBasic[iRow]  tolerance) { 230 chosenRow = iRow; 231 largest = value; 232 } 233 } 234 } 235 } 243 236 #ifdef DO_REDUCE 244 237 } 245 238 #endif 246 numberWanted =(endstartThis);239 numberWanted = (end  startThis); 247 240 if (!numberWanted) { 248 if(chosenRow>=0)249 250 251 numberWanted=(saveNumberWanted+1)>>1;241 if (chosenRow >= 0) 242 break; 243 else 244 numberWanted = (saveNumberWanted + 1) >> 1; 252 245 } 253 startThis =end;246 startThis = end; 254 247 } 255 248 if (!numberWanted) { 256 if (chosenRow>=0)257 249 if (chosenRow >= 0) 250 break; 258 251 else 259 numberWanted=(saveNumberWanted+1)>>1;252 numberWanted = (saveNumberWanted + 1) >> 1; 260 253 } 261 254 } … … 264 257 // FT update and returns pivot alpha 265 258 double 266 AbcDualRowDantzig::updateWeights(CoinIndexedVector & input,CoinIndexedVector &updatedColumn)259 AbcDualRowDantzig::updateWeights(CoinIndexedVector &input, CoinIndexedVector &updatedColumn) 267 260 { 268 261 // Do FT update … … 271 264 double alpha = 0.0; 272 265 // look at updated column 273 double * 266 double *work = updatedColumn.denseVector(); 274 267 int pivotRow = model_>lastPivotRow(); 275 assert 276 277 assert 268 assert(pivotRow == model_>pivotRow()); 269 270 assert(!updatedColumn.packedMode()); 278 271 alpha = work[pivotRow]; 279 272 return alpha; 280 273 } 281 double 282 AbcDualRowDantzig::updateWeights1(CoinIndexedVector & input,CoinIndexedVector &updateColumn)283 { 284 return updateWeights(input, updateColumn);285 } 286 #if ABC_PARALLEL ==2274 double 275 AbcDualRowDantzig::updateWeights1(CoinIndexedVector &input, CoinIndexedVector &updateColumn) 276 { 277 return updateWeights(input, updateColumn); 278 } 279 #if ABC_PARALLEL == 2 287 280 static void update(int first, int last, 288 const int * COIN_RESTRICT which, double * COIN_RESTRICT work, 289 const double * COIN_RESTRICT lowerBasic,double *COIN_RESTRICT solutionBasic,290 const double * COIN_RESTRICT upperBasic,double theta,double tolerance)291 { 292 if (last first>256) {293 int mid =(last+first)>>1;294 cilk_spawn update(first, mid,which,work,lowerBasic,solutionBasic,295 upperBasic,theta,tolerance);296 update(mid, last,which,work,lowerBasic,solutionBasic,297 upperBasic,theta,tolerance);281 const int *COIN_RESTRICT which, double *COIN_RESTRICT work, 282 const double *COIN_RESTRICT lowerBasic, double *COIN_RESTRICT solutionBasic, 283 const double *COIN_RESTRICT upperBasic, double theta, double tolerance) 284 { 285 if (last  first > 256) { 286 int mid = (last + first) >> 1; 287 cilk_spawn update(first, mid, which, work, lowerBasic, solutionBasic, 288 upperBasic, theta, tolerance); 289 update(mid, last, which, work, lowerBasic, solutionBasic, 290 upperBasic, theta, tolerance); 298 291 cilk_sync; 299 292 } else { … … 308 301 solutionBasic[iRow] = value; 309 302 if (value < lower  tolerance) { 310 311 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 312 313 303 value = lower; 304 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 305 if (lower == upper) 306 value *= CLP_DUAL_FIXED_COLUMN_MULTIPLIER; // bias towards taking out fixed variables 314 307 #endif 315 308 } else if (value > upper + tolerance) { 316 317 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 318 319 309 value = upper; 310 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 311 if (lower == upper) 312 value *= CLP_DUAL_FIXED_COLUMN_MULTIPLIER; // bias towards taking out fixed variables 320 313 #endif 321 314 } else { 322 323 value=0.0;315 // feasible 316 value = 0.0; 324 317 } 325 318 // store 326 work[iRow] =fabs(value);319 work[iRow] = fabs(value); 327 320 } 328 321 } … … 333 326 Computes change in objective function 334 327 */ 335 void 336 AbcDualRowDantzig::updatePrimalSolution(CoinIndexedVector & primalUpdate, 337 double theta) 338 { 339 double * COIN_RESTRICT work = primalUpdate.denseVector(); 328 void AbcDualRowDantzig::updatePrimalSolution(CoinIndexedVector &primalUpdate, 329 double theta) 330 { 331 double *COIN_RESTRICT work = primalUpdate.denseVector(); 340 332 int numberNonZero = primalUpdate.getNumElements(); 341 int * 333 int *which = primalUpdate.getIndices(); 342 334 double tolerance = model_>currentPrimalTolerance(); 343 double * 344 double * 345 const double * 346 const double * 347 assert 335 double *COIN_RESTRICT infeas = infeasible_>denseVector(); 336 double *COIN_RESTRICT solutionBasic = model_>solutionBasic(); 337 const double *COIN_RESTRICT lowerBasic = model_>lowerBasic(); 338 const double *COIN_RESTRICT upperBasic = model_>upperBasic(); 339 assert(!primalUpdate.packedMode()); 348 340 #if 0 //ABC_PARALLEL==2 349 341 update(0,numberNonZero,which,work, … … 369 361 int iRow = which[i]; 370 362 double updateValue = work[iRow]; 371 work[iRow] =0.0;363 work[iRow] = 0.0; 372 364 double value = solutionBasic[iRow]; 373 365 double change = theta * updateValue; … … 380 372 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 381 373 if (lower == upper) 382 374 value *= CLP_DUAL_FIXED_COLUMN_MULTIPLIER; // bias towards taking out fixed variables 383 375 #endif 384 376 // store in list 385 377 if (infeas[iRow]) 386 378 infeas[iRow] = fabs(value); // already there 387 379 else 388 380 infeasible_>quickAdd(iRow, fabs(value)); 389 381 } else if (value > upper + tolerance) { 390 382 value = upper; 391 383 #ifdef CLP_DUAL_FIXED_COLUMN_MULTIPLIER 392 384 if (lower == upper) 393 385 value *= CLP_DUAL_FIXED_COLUMN_MULTIPLIER; // bias towards taking out fixed variables 394 386 #endif 395 387 // store in list 396 388 if (infeas[iRow]) 397 389 infeas[iRow] = fabs(value); // already there 398 390 else 399 391 infeasible_>quickAdd(iRow, fabs(value)); 400 392 } else { 401 393 // feasible  was it infeasible  if so set tiny 402 394 if (infeas[iRow]) 403 395 infeas[iRow] = COIN_INDEXED_REALLY_TINY_ELEMENT; 404 396 } 405 397 } … … 410 402 // Clone 411 403 // 412 AbcDualRowPivot * 404 AbcDualRowPivot *AbcDualRowDantzig::clone(bool CopyData) const 413 405 { 414 406 if (CopyData) { … … 418 410 } 419 411 } 412 413 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 414 */
Note: See TracChangeset
for help on using the changeset viewer.