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

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Clp/src/ClpPEDualRowDantzig.cpp
r2149 r2385 25 25 // 26 26 ClpPEDualRowDantzig::ClpPEDualRowDantzig(double psi) 27 : ClpDualRowDantzig(), modelPE_(NULL), psi_(psi), 28 iCurrent_(0), iInterval_(100), updateCompatibles_(true), 29 coDegenCompatibles_(0), coConsecutiveCompatibles_(0) 27 : ClpDualRowDantzig() 28 , modelPE_(NULL) 29 , psi_(psi) 30 , iCurrent_(0) 31 , iInterval_(100) 32 , updateCompatibles_(true) 33 , coDegenCompatibles_(0) 34 , coConsecutiveCompatibles_(0) 30 35 { 31 36 } … … 34 39 // Copy constructor 35 40 // 36 ClpPEDualRowDantzig::ClpPEDualRowDantzig(const ClpPEDualRowDantzig & 37 : ClpDualRowDantzig(source)38 { 39 modelPE_= NULL;40 psi_= source.psi_;41 iCurrent_= source.iCurrent_;42 iInterval_= source.iInterval_;43 44 45 41 ClpPEDualRowDantzig::ClpPEDualRowDantzig(const ClpPEDualRowDantzig &source) 42 : ClpDualRowDantzig(source) 43 { 44 modelPE_ = NULL; 45 psi_ = source.psi_; 46 iCurrent_ = source.iCurrent_; 47 iInterval_ = source.iInterval_; 48 updateCompatibles_ = source.updateCompatibles_; 49 coDegenCompatibles_ = source.coDegenCompatibles_; 50 coConsecutiveCompatibles_ = source.coConsecutiveCompatibles_; 46 51 } 47 52 … … 49 54 // Destructor 50 55 // 51 ClpPEDualRowDantzig::~ClpPEDualRowDantzig 56 ClpPEDualRowDantzig::~ClpPEDualRowDantzig() 52 57 { 53 58 delete modelPE_; … … 58 63 // 59 64 ClpPEDualRowDantzig & 60 ClpPEDualRowDantzig::operator=(const ClpPEDualRowDantzig &rhs)61 { 62 63 64 65 modelPE_=NULL;66 67 65 ClpPEDualRowDantzig::operator=(const ClpPEDualRowDantzig &rhs) 66 { 67 if (this != &rhs) { 68 ClpDualRowDantzig::operator=(rhs); 69 delete modelPE_; 70 modelPE_ = NULL; 71 } 72 return *this; 68 73 } 69 74 … … 71 76 // Clone 72 77 // 73 ClpDualRowPivot * ClpPEDualRowDantzig::clone(bool CopyData) const 74 { 75 if (CopyData) { 76 return new ClpPEDualRowDantzig(*this); 77 } else { 78 return new ClpPEDualRowDantzig(psi_); 79 } 80 } 81 78 ClpDualRowPivot *ClpPEDualRowDantzig::clone(bool CopyData) const 79 { 80 if (CopyData) { 81 return new ClpPEDualRowDantzig(*this); 82 } else { 83 return new ClpPEDualRowDantzig(psi_); 84 } 85 } 82 86 83 87 // Returns pivot row, 1 if none 84 int 85 ClpPEDualRowDantzig::pivotRow() 86 { 87 assert(model_); 88 89 /* Determine whether the set of compatible variables should be updated 88 int ClpPEDualRowDantzig::pivotRow() 89 { 90 assert(model_); 91 92 /* Determine whether the set of compatible variables should be updated 90 93 */ 91 // store the number of degenerate pivots on compatible variables and the 92 // overal number of degenerate pivots 93 double progress = fabs(modelPE_>lastObjectiveValue()  model_>objectiveValue()); 94 bool isLastDegenerate = progress <= 1.0e12*fabs(model_>objectiveValue()) ? true:false; 95 if ( isLastDegenerate ) { 96 modelPE_>addDegeneratePivot(); 97 modelPE_>addDegeneratePivotConsecutive(); 98 99 if ( modelPE_>isLastPivotCompatible() ) { 100 modelPE_>addDegenerateCompatiblePivot(); 101 } 102 } 103 else { 104 modelPE_>resetDegeneratePivotsConsecutive(); 105 } 106 107 // the compatible variables are updated when the number of degenerate pivots 108 // on compatible variables is more than 20% the overall number of degenerate pivots 109 if ( modelPE_>isLastPivotCompatible() ) { 110 coConsecutiveCompatibles_++; 111 if (isLastDegenerate) { 112 coDegenCompatibles_++; 113 if ( coConsecutiveCompatibles_ >= 10 && 5*coDegenCompatibles_*model_>numberIterations() > modelPE_>coDegeneratePivots()*coConsecutiveCompatibles_ ) { 114 updateCompatibles_ = true; 115 } 116 } 117 } 118 119 if (modelPE_>doStatistics()) { 120 // For results comparison. 121 // count the number of degenerate variables if psi==1 122 // add the time spent in counting to the time limit 123 124 modelPE_>startTimer(); 125 if (psi_ >= 1 && iCurrent_ >= 100) { 126 modelPE_>updateDualDegenerates(); 127 modelPE_>updateDualDegeneratesAvg(100); 128 model_>setMaximumSeconds(36000.0+modelPE_>timeCompatibility()CoinCpuTime()); 129 iCurrent_ = 0; 130 } 131 modelPE_>stopTimer(); 132 } 133 134 // Update the set of compatible variables if necessary 135 // 136 if (modelPE_>doStatistics()) 137 modelPE_>startTimer(); 138 double psiTmp = psi_; 139 if ( (psi_ < 1.0) && (iCurrent_ >= iInterval_) && (updateCompatibles_iCurrent_ >= 1000) ) 140 { 141 // the compatible variables are never updated if the last pivot is non degenerate 142 // this could be counterproductive 143 if (isLastDegenerate) { 144 145 modelPE_>updateDualDegenerates(); 146 modelPE_>identifyCompatibleRows(model_>rowArray(2), 147 model_>rowArray(1)); 148 149 if (modelPE_>doStatistics()) { 150 // update the average number of degenerates and compatibles for statistics 151 modelPE_>updateDualDegeneratesAvg(iCurrent_); 152 modelPE_>updateCompatibleRowsAvg(iCurrent_); 153 } 94 // store the number of degenerate pivots on compatible variables and the 95 // overal number of degenerate pivots 96 double progress = fabs(modelPE_>lastObjectiveValue()  model_>objectiveValue()); 97 bool isLastDegenerate = progress <= 1.0e12 * fabs(model_>objectiveValue()) ? true : false; 98 if (isLastDegenerate) { 99 modelPE_>addDegeneratePivot(); 100 modelPE_>addDegeneratePivotConsecutive(); 101 102 if (modelPE_>isLastPivotCompatible()) { 103 modelPE_>addDegenerateCompatiblePivot(); 104 } 105 } else { 106 modelPE_>resetDegeneratePivotsConsecutive(); 107 } 108 109 // the compatible variables are updated when the number of degenerate pivots 110 // on compatible variables is more than 20% the overall number of degenerate pivots 111 if (modelPE_>isLastPivotCompatible()) { 112 coConsecutiveCompatibles_++; 113 if (isLastDegenerate) { 114 coDegenCompatibles_++; 115 if (coConsecutiveCompatibles_ >= 10 && 5 * coDegenCompatibles_ * model_>numberIterations() > modelPE_>coDegeneratePivots() * coConsecutiveCompatibles_) { 116 updateCompatibles_ = true; 117 } 118 } 119 } 120 121 if (modelPE_>doStatistics()) { 122 // For results comparison. 123 // count the number of degenerate variables if psi==1 124 // add the time spent in counting to the time limit 125 126 modelPE_>startTimer(); 127 if (psi_ >= 1 && iCurrent_ >= 100) { 128 modelPE_>updateDualDegenerates(); 129 modelPE_>updateDualDegeneratesAvg(100); 130 model_>setMaximumSeconds(36000.0 + modelPE_>timeCompatibility()  CoinCpuTime()); 131 iCurrent_ = 0; 132 } 133 modelPE_>stopTimer(); 134 } 135 136 // Update the set of compatible variables if necessary 137 // 138 if (modelPE_>doStatistics()) 139 modelPE_>startTimer(); 140 double psiTmp = psi_; 141 if ((psi_ < 1.0) && (iCurrent_ >= iInterval_) && (updateCompatibles_  iCurrent_ >= 1000)) { 142 // the compatible variables are never updated if the last pivot is non degenerate 143 // this could be counterproductive 144 if (isLastDegenerate) { 145 146 modelPE_>updateDualDegenerates(); 147 modelPE_>identifyCompatibleRows(model_>rowArray(2), 148 model_>rowArray(1)); 149 150 if (modelPE_>doStatistics()) { 151 // update the average number of degenerates and compatibles for statistics 152 modelPE_>updateDualDegeneratesAvg(iCurrent_); 153 modelPE_>updateCompatibleRowsAvg(iCurrent_); 154 } 154 155 155 156 #if PE_DEBUG >= 1 156 std::cout << "Number of compatible rows = " << modelPE_>coCompatibleRows() << " ; average = " << modelPE_>coCompatibleRowsAvg() << std::endl; 157 std::cout << "Number of degenerates = " << modelPE_>coDualDegenerates() << " ; average = " << modelPE_>coDualDegeneratesAvg() << std::endl; 158 #endif 159 160 // the checking frequency is modified to reflect what appears to be needed 161 if (iCurrent_ == iInterval_) iInterval_ = std::max(50, iInterval_50); 162 else iInterval_ = std::min(300, iInterval_+50); 163 164 // reset all the indicators that are used to decide whether the compatible 165 // variables must be updated 166 iCurrent_ = 0; 167 updateCompatibles_ = false; 168 coConsecutiveCompatibles_ = 0; 169 coDegenCompatibles_ = 0; 170 } 171 else iInterval_++; 172 } 173 // otherwise, update the value of the priority factor depending on the number of 174 // consecutive degenerate pivots 175 // 176 else { 177 // the idea is that when a lot of consecutive pivots are degenerate, there is 178 // a potentially hign added value in putting a very high priroity on compatible 179 // variables 180 if (modelPE_>coDegeneratePivotsConsecutive() >= 10) { 181 psiTmp = 0.01; 157 std::cout << "Number of compatible rows = " << modelPE_>coCompatibleRows() << " ; average = " << modelPE_>coCompatibleRowsAvg() << std::endl; 158 std::cout << "Number of degenerates = " << modelPE_>coDualDegenerates() << " ; average = " << modelPE_>coDualDegeneratesAvg() << std::endl; 159 #endif 160 161 // the checking frequency is modified to reflect what appears to be needed 162 if (iCurrent_ == iInterval_) 163 iInterval_ = std::max(50, iInterval_  50); 164 else 165 iInterval_ = std::min(300, iInterval_ + 50); 166 167 // reset all the indicators that are used to decide whether the compatible 168 // variables must be updated 169 iCurrent_ = 0; 170 updateCompatibles_ = false; 171 coConsecutiveCompatibles_ = 0; 172 coDegenCompatibles_ = 0; 173 } else 174 iInterval_++; 175 } 176 // otherwise, update the value of the priority factor depending on the number of 177 // consecutive degenerate pivots 178 // 179 else { 180 // the idea is that when a lot of consecutive pivots are degenerate, there is 181 // a potentially hign added value in putting a very high priroity on compatible 182 // variables 183 if (modelPE_>coDegeneratePivotsConsecutive() >= 10) { 184 psiTmp = 0.01; 182 185 183 186 #if PE_DEBUG >= 1 184 std::cout << "Lower the priority factor to " << psiTmp << std::endl; 185 std::cout << "Consecutive degenerate pivots=" << modelPE_>coDegeneratePivotsConsecutive() << std::endl; 186 #endif 187 } 188 } 189 iCurrent_++; 190 if (modelPE_>doStatistics()) 191 modelPE_>stopTimer(); 192 193 194 // Do the pricing and give priority to dual compatible variables 195 // 196 int iRow; 197 const int * pivotVariable = model_>pivotVariable(); 198 double tolerance = model_>currentPrimalTolerance(); 199 // we can't really trust infeasibilities if there is primal error 200 if (model_>largestPrimalError() > 1.0e8) 201 tolerance *= model_>largestPrimalError() / 1.0e8; 202 double largest = 0.0; 203 double largestComp = 0.0; 204 int chosenRow = 1; 205 int chosenRowComp = 1; 206 int numberRows = model_>numberRows(); 187 std::cout << "Lower the priority factor to " << psiTmp << std::endl; 188 std::cout << "Consecutive degenerate pivots=" << modelPE_>coDegeneratePivotsConsecutive() << std::endl; 189 #endif 190 } 191 } 192 iCurrent_++; 193 if (modelPE_>doStatistics()) 194 modelPE_>stopTimer(); 195 196 // Do the pricing and give priority to dual compatible variables 197 // 198 int iRow; 199 const int *pivotVariable = model_>pivotVariable(); 200 double tolerance = model_>currentPrimalTolerance(); 201 // we can't really trust infeasibilities if there is primal error 202 if (model_>largestPrimalError() > 1.0e8) 203 tolerance *= model_>largestPrimalError() / 1.0e8; 204 double largest = 0.0; 205 double largestComp = 0.0; 206 int chosenRow = 1; 207 int chosenRowComp = 1; 208 int numberRows = model_>numberRows(); 207 209 #ifdef CLP_DUAL_COLUMN_MULTIPLIER 208 209 #endif 210 211 // only check the compatible variables when the bidimensional factor is less than 1212 // and the ratio of compatible variables is larger than 0.01213 // the percentage of compatible variables is computed as the ratio to the 214 // smallest number among columns and rows215 216 double ratioCompatibles = static_cast<double> ( modelPE_>coCompatibleRows())/ 217 static_cast<double> (std::min(model_>numberRows(),model_>numberColumns())); 218 219 if (psi_ >= 1.0 ratioCompatibles < 0.01)checkCompatibles = false;220 221 // check the infeasibility of the variables (there is no partial pricing!)222 223 224 225 226 227 double infeas = CoinMax(value  upper, lower  value);228 double largestMax = std::max(psi_*largest, largestComp); 229 210 int numberColumns = model_>numberColumns(); 211 #endif 212 213 // only check the compatible variables when the bidimensional factor is less than 1 214 // and the ratio of compatible variables is larger than 0.01 215 // the percentage of compatible variables is computed as the ratio to the 216 // smallest number among columns and rows 217 bool checkCompatibles = true; 218 double ratioCompatibles = static_cast< double >(modelPE_>coCompatibleRows()) / static_cast< double >(std::min(model_>numberRows(), model_>numberColumns())); 219 220 if (psi_ >= 1.0  ratioCompatibles < 0.01) 221 checkCompatibles = false; 222 223 // check the infeasibility of the variables (there is no partial pricing!) 224 for (iRow = 0; iRow < numberRows; iRow++) { 225 int iSequence = pivotVariable[iRow]; 226 double value = model_>solution(iSequence); 227 double lower = model_>lower(iSequence); 228 double upper = model_>upper(iSequence); 229 double infeas = CoinMax(value  upper, lower  value); 230 double largestMax = std::max(psi_ * largest, largestComp); 231 if (infeas > tolerance) { 230 232 #ifdef CLP_DUAL_COLUMN_MULTIPLIER 231 if (iSequence < numberColumns) 232 infeas *= CLP_DUAL_COLUMN_MULTIPLIER; 233 #endif 234 if (infeas > largestMax ) { 235 if (model_>flagged(iSequence)) { 236 } 237 else if (checkCompatibles && modelPE_>isCompatibleRow(iRow) && infeas > largestComp) { 238 chosenRowComp = iRow; 239 largestComp = infeas; 240 } 241 else if ( infeas > largest ) { 242 chosenRow = iRow; 243 largest = infeas; 244 } 245 } 246 } 247 } 248 249 // choose a compatible or an incompatible row depending on the 250 // largest values and on the factor of preference psi_ 251 if (modelPE_>doStatistics()) 252 modelPE_>startTimer(); 253 if ( chosenRowComp >= 0 && largestComp >= psiTmp * largest) { 254 chosenRow = chosenRowComp; 255 256 if (modelPE_>doStatistics()) { 257 // record the number of pivots done on compatible variables 258 // that would not have been done without positive edge 259 if (largestComp < largest) 260 modelPE_>addPriorityPivot(); 261 } 233 if (iSequence < numberColumns) 234 infeas *= CLP_DUAL_COLUMN_MULTIPLIER; 235 #endif 236 if (infeas > largestMax) { 237 if (model_>flagged(iSequence)) { 238 } else if (checkCompatibles && modelPE_>isCompatibleRow(iRow) && infeas > largestComp) { 239 chosenRowComp = iRow; 240 largestComp = infeas; 241 } else if (infeas > largest) { 242 chosenRow = iRow; 243 largest = infeas; 244 } 245 } 246 } 247 } 248 249 // choose a compatible or an incompatible row depending on the 250 // largest values and on the factor of preference psi_ 251 if (modelPE_>doStatistics()) 252 modelPE_>startTimer(); 253 if (chosenRowComp >= 0 && largestComp >= psiTmp * largest) { 254 chosenRow = chosenRowComp; 255 256 if (modelPE_>doStatistics()) { 257 // record the number of pivots done on compatible variables 258 // that would not have been done without positive edge 259 if (largestComp < largest) 260 modelPE_>addPriorityPivot(); 261 } 262 262 #if PE_DEBUG >= 1 263 modelPE_>checkCompatibilityRow(chosenRow); 264 #endif 265 } 266 if ( psi_ < 1 && modelPE_>isCompatibleRow(chosenRow) ) { 267 modelPE_>isLastPivotCompatible(true); 268 modelPE_>addCompatiblePivot(); 269 } 270 else 271 modelPE_>isLastPivotCompatible(false); 272 if (modelPE_>doStatistics()) 273 modelPE_>stopTimer(); 274 275 modelPE_>updateLastObjectiveValue(); 276 return chosenRow; 277 } 278 279 263 modelPE_>checkCompatibilityRow(chosenRow); 264 #endif 265 } 266 if (psi_ < 1 && modelPE_>isCompatibleRow(chosenRow)) { 267 modelPE_>isLastPivotCompatible(true); 268 modelPE_>addCompatiblePivot(); 269 } else 270 modelPE_>isLastPivotCompatible(false); 271 if (modelPE_>doStatistics()) 272 modelPE_>stopTimer(); 273 274 modelPE_>updateLastObjectiveValue(); 275 return chosenRow; 276 } 280 277 281 278 // 282 279 // updateWeights 283 // Update the compatible variables and 284 // call the base class method to update weights 285 // 286 287 double ClpPEDualRowDantzig::updateWeights(CoinIndexedVector * 288 CoinIndexedVector *spare,289 CoinIndexedVector *spare2,290 CoinIndexedVector *updatedColumn)291 { 292 293 294 280 // Update the compatible variables and 281 // call the base class method to update weights 282 // 283 284 double ClpPEDualRowDantzig::updateWeights(CoinIndexedVector *input, 285 CoinIndexedVector *spare, 286 CoinIndexedVector *spare2, 287 CoinIndexedVector *updatedColumn) 288 { 289 double value = ClpDualRowDantzig::updateWeights(input, spare, spare2, updatedColumn); 290 291 return value; 295 292 } 296 293 /* Save weights  this may initialize weights as well 297 294 This is as parent but may initialize ClpPESimplex 298 295 */ 299 void 300 ClpPEDualRowDantzig::saveWeights(ClpSimplex * model, int mode) 296 void ClpPEDualRowDantzig::saveWeights(ClpSimplex *model, int mode) 301 297 { 302 298 // See if we need to initialize ClpPESimplex 303 if (!modelPE_ model!=modelPE_>clpModel()) {299 if (!modelPE_  model != modelPE_>clpModel()) { 304 300 delete modelPE_; 305 301 modelPE_ = new ClpPESimplex(model); 306 302 } 307 ClpDualRowDantzig::saveWeights(model, mode);308 } 309 310 311 303 ClpDualRowDantzig::saveWeights(model, mode); 304 } 305 306 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 307 */
Note: See TracChangeset
for help on using the changeset viewer.