Changeset 2464 for trunk/Cbc/src/CbcModel.cpp
- Timestamp:
- Jan 3, 2019 2:03:23 PM (2 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Cbc/src/CbcModel.cpp
r2419 r2464 6 6 #if defined(_MSC_VER) 7 7 // Turn off compiler warning about long names 8 # pragma warning(disable:4786)8 #pragma warning(disable : 4786) 9 9 #endif 10 10 … … 87 87 typedef struct { 88 88 double useCutoff; 89 CbcModel * 89 CbcModel *model; 90 90 int switches; 91 91 } rootBundle; 92 static void * doRootCbcThread(void *voidInfo);92 static void *doRootCbcThread(void *voidInfo); 93 93 94 94 namespace { … … 100 100 static int gcd(int a, int b) 101 101 { 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 102 int remainder = -1; 103 // make sure a<=b (will always remain so) 104 if (a > b) { 105 // Swap a and b 106 int temp = a; 107 a = b; 108 b = temp; 109 } 110 // if zero then gcd is nonzero (zero may occur in rhs of packed) 111 if (!a) { 112 if (b) { 113 return b; 114 } else { 115 printf("**** gcd given two zeros!!\n"); 116 abort(); 117 } 118 } 119 while (remainder) { 120 remainder = b % a; 121 b = a; 122 a = remainder; 123 } 124 return b; 125 125 } 126 127 128 129 126 130 127 #ifdef CHECK_NODE_FULL … … 142 139 */ 143 140 144 void verifyTreeNodes (const CbcTree *branchingTree, const CbcModel &model)141 void verifyTreeNodes(const CbcTree *branchingTree, const CbcModel &model) 145 142 146 143 { 147 if (model.getNodeCount() == 661) return; 148 printf("*** CHECKING tree after %d nodes\n", model.getNodeCount()) ; 149 150 int j ; 151 int nNodes = branchingTree->size() ; 152 # define MAXINFO 1000 153 int *count = new int [MAXINFO] ; 154 CbcNodeInfo **info = new CbcNodeInfo*[MAXINFO] ; 155 int nInfo = 0 ; 156 /* 144 if (model.getNodeCount() == 661) 145 return; 146 printf("*** CHECKING tree after %d nodes\n", model.getNodeCount()); 147 148 int j; 149 int nNodes = branchingTree->size(); 150 #define MAXINFO 1000 151 int *count = new int[MAXINFO]; 152 CbcNodeInfo **info = new CbcNodeInfo *[MAXINFO]; 153 int nInfo = 0; 154 /* 157 155 Collect all CbcNodeInfo objects in info, by starting from each live node and 158 156 traversing back to the root. Nodes in the live set should have unexplored … … 164 162 common ancestor. 165 163 */ 166 for (j = 0 ; j < nNodes ; j++) { 167 CbcNode *node = branchingTree->nodePointer(j) ; 168 if (!node) 169 continue; 170 CbcNodeInfo *nodeInfo = node->nodeInfo() ; 171 int change = node->nodeInfo()->numberBranchesLeft() ; 172 assert(change) ; 173 while (nodeInfo) { 174 int k ; 175 for (k = 0 ; k < nInfo ; k++) { 176 if (nodeInfo == info[k]) break ; 177 } 178 if (k == nInfo) { 179 assert(nInfo < MAXINFO) ; 180 nInfo++ ; 181 info[k] = nodeInfo ; 182 count[k] = 0 ; 183 } 184 nodeInfo = nodeInfo->parent() ; 185 } 186 } 187 /* 164 for (j = 0; j < nNodes; j++) { 165 CbcNode *node = branchingTree->nodePointer(j); 166 if (!node) 167 continue; 168 CbcNodeInfo *nodeInfo = node->nodeInfo(); 169 int change = node->nodeInfo()->numberBranchesLeft(); 170 assert(change); 171 while (nodeInfo) { 172 int k; 173 for (k = 0; k < nInfo; k++) { 174 if (nodeInfo == info[k]) 175 break; 176 } 177 if (k == nInfo) { 178 assert(nInfo < MAXINFO); 179 nInfo++; 180 info[k] = nodeInfo; 181 count[k] = 0; 182 } 183 nodeInfo = nodeInfo->parent(); 184 } 185 } 186 /* 188 187 Walk the info array. For each nodeInfo, look up its parent in info and 189 188 increment the corresponding count. 190 189 */ 191 for (j = 0 ; j < nInfo ; j++) { 192 CbcNodeInfo *nodeInfo = info[j] ; 193 nodeInfo = nodeInfo->parent() ; 194 if (nodeInfo) { 195 int k ; 196 for (k = 0 ; k < nInfo ; k++) { 197 if (nodeInfo == info[k]) break ; 198 } 199 assert (k < nInfo) ; 200 count[k]++ ; 201 } 202 } 203 /* 190 for (j = 0; j < nInfo; j++) { 191 CbcNodeInfo *nodeInfo = info[j]; 192 nodeInfo = nodeInfo->parent(); 193 if (nodeInfo) { 194 int k; 195 for (k = 0; k < nInfo; k++) { 196 if (nodeInfo == info[k]) 197 break; 198 } 199 assert(k < nInfo); 200 count[k]++; 201 } 202 } 203 /* 204 204 Walk the info array one more time and check that the invariant holds. The 205 205 number of references (numberPointingToThis()) should equal the sum of the … … 207 207 references (unexplored branches, numberBranchesLeft()). 208 208 */ 209 for (j = 0; j < nInfo; j++) { 210 CbcNodeInfo * nodeInfo = info[j] ; 211 if (nodeInfo) { 212 int k ; 213 for (k = 0; k < nInfo; k++) 214 if (nodeInfo == info[k]) 215 break ; 216 printf("Nodeinfo %x - %d left, %d count\n", 217 nodeInfo, 218 nodeInfo->numberBranchesLeft(), 219 nodeInfo->numberPointingToThis()) ; 220 assert(nodeInfo->numberPointingToThis() == 221 count[k] + nodeInfo->numberBranchesLeft()) ; 222 } 223 } 224 225 delete [] count ; 226 delete [] info ; 227 228 return ; 209 for (j = 0; j < nInfo; j++) { 210 CbcNodeInfo *nodeInfo = info[j]; 211 if (nodeInfo) { 212 int k; 213 for (k = 0; k < nInfo; k++) 214 if (nodeInfo == info[k]) 215 break; 216 printf("Nodeinfo %x - %d left, %d count\n", 217 nodeInfo, 218 nodeInfo->numberBranchesLeft(), 219 nodeInfo->numberPointingToThis()); 220 assert(nodeInfo->numberPointingToThis() == count[k] + nodeInfo->numberBranchesLeft()); 221 } 222 } 223 224 delete[] count; 225 delete[] info; 226 227 return; 229 228 } 230 229 231 #endif /* CHECK_NODE_FULL */ 232 233 234 230 #endif /* CHECK_NODE_FULL */ 235 231 236 232 #ifdef CHECK_CUT_COUNTS … … 239 235 Routine to verify that cut reference counts are correct. 240 236 */ 241 void verifyCutCounts (const CbcTree *branchingTree, CbcModel &model)237 void verifyCutCounts(const CbcTree *branchingTree, CbcModel &model) 242 238 243 239 { 244 printf("*** CHECKING cuts after %d nodes\n", model.getNodeCount());245 246 int j;247 int nNodes = branchingTree->size();248 249 240 printf("*** CHECKING cuts after %d nodes\n", model.getNodeCount()); 241 242 int j; 243 int nNodes = branchingTree->size(); 244 245 /* 250 246 cut.tempNumber_ exists for the purpose of doing this verification. Clear it 251 247 in all cuts. We traverse the tree by starting from each live node and working 252 248 back to the root. At each CbcNodeInfo, check for cuts. 253 249 */ 254 for (j = 0 ; j < nNodes ; j++) { 255 CbcNode *node = branchingTree->nodePointer(j) ; 256 CbcNodeInfo * nodeInfo = node->nodeInfo() ; 257 assert (node->nodeInfo()->numberBranchesLeft()) ; 258 while (nodeInfo) { 259 int k ; 260 for (k = 0 ; k < nodeInfo->numberCuts() ; k++) { 261 CbcCountRowCut *cut = nodeInfo->cuts()[k] ; 262 if (cut) cut->tempNumber_ = 0; 263 } 264 nodeInfo = nodeInfo->parent() ; 265 } 266 } 267 /* 250 for (j = 0; j < nNodes; j++) { 251 CbcNode *node = branchingTree->nodePointer(j); 252 CbcNodeInfo *nodeInfo = node->nodeInfo(); 253 assert(node->nodeInfo()->numberBranchesLeft()); 254 while (nodeInfo) { 255 int k; 256 for (k = 0; k < nodeInfo->numberCuts(); k++) { 257 CbcCountRowCut *cut = nodeInfo->cuts()[k]; 258 if (cut) 259 cut->tempNumber_ = 0; 260 } 261 nodeInfo = nodeInfo->parent(); 262 } 263 } 264 /* 268 265 Walk the live set again, this time collecting the list of cuts in use at each 269 266 node. addCuts1 will collect the cuts in model.addedCuts_. Take into account 270 267 that when we recreate the basis for a node, we compress out the slack cuts. 271 268 */ 272 for (j = 0 ; j < nNodes; j++) {273 CoinWarmStartBasis *debugws = model.getEmptyBasis();274 CbcNode *node = branchingTree->nodePointer(j);275 276 int change = node->nodeInfo()->numberBranchesLeft();277 278 279 node->objectiveValue());280 281 model.addCuts1(node, debugws);282 283 int i;284 int numberRowsAtContinuous = model.numberRowsAtContinuous();285 CbcCountRowCut **addedCuts = model.addedCuts();286 for (i = 0 ; i < model.currentNumberCuts(); i++) {287 CoinWarmStartBasis::Status status =288 debugws->getArtifStatus(i + numberRowsAtContinuous) ;289 if (status != CoinWarmStartBasis::basic && addedCuts[i]) {290 addedCuts[i]->tempNumber_ += change ;291 292 } 293 294 while (nodeInfo) {295 nodeInfo = nodeInfo->parent() ;296 if (nodeInfo)printf(" -> %x", nodeInfo);297 298 printf("\n");299 delete debugws;300 301 269 for (j = 0; j < nNodes; j++) { 270 CoinWarmStartBasis *debugws = model.getEmptyBasis(); 271 CbcNode *node = branchingTree->nodePointer(j); 272 CbcNodeInfo *nodeInfo = node->nodeInfo(); 273 int change = node->nodeInfo()->numberBranchesLeft(); 274 printf("Node %d %x (info %x) var %d way %d obj %g", j, node, 275 node->nodeInfo(), node->columnNumber(), node->way(), 276 node->objectiveValue()); 277 278 model.addCuts1(node, debugws); 279 280 int i; 281 int numberRowsAtContinuous = model.numberRowsAtContinuous(); 282 CbcCountRowCut **addedCuts = model.addedCuts(); 283 for (i = 0; i < model.currentNumberCuts(); i++) { 284 CoinWarmStartBasis::Status status = debugws->getArtifStatus(i + numberRowsAtContinuous); 285 if (status != CoinWarmStartBasis::basic && addedCuts[i]) { 286 addedCuts[i]->tempNumber_ += change; 287 } 288 } 289 290 while (nodeInfo) { 291 nodeInfo = nodeInfo->parent(); 292 if (nodeInfo) 293 printf(" -> %x", nodeInfo); 294 } 295 printf("\n"); 296 delete debugws; 297 } 298 /* 302 299 The moment of truth: We've tallied up the references by direct scan of the search tree. Check for agreement with the count in the cut. 303 300 304 301 TODO: Rewrite to check and print mismatch only when tempNumber_ == 0? 305 302 */ 306 for (j = 0 ; j < nNodes; j++) {307 CbcNode *node = branchingTree->nodePointer(j);308 309 310 int k;311 for (k = 0 ; k < nodeInfo->numberCuts(); k++) {312 CbcCountRowCut *cut = nodeInfo->cuts()[k];313 314 315 316 cut, cut->tempNumber_, cut->numberPointingToThis());317 318 319 cut, cut->tempNumber_, cut->numberPointingToThis());320 cut->tempNumber_ = -1;321 322 323 nodeInfo = nodeInfo->parent();324 325 326 327 return;303 for (j = 0; j < nNodes; j++) { 304 CbcNode *node = branchingTree->nodePointer(j); 305 CbcNodeInfo *nodeInfo = node->nodeInfo(); 306 while (nodeInfo) { 307 int k; 308 for (k = 0; k < nodeInfo->numberCuts(); k++) { 309 CbcCountRowCut *cut = nodeInfo->cuts()[k]; 310 if (cut && cut->tempNumber_ >= 0) { 311 if (cut->tempNumber_ != cut->numberPointingToThis()) 312 printf("mismatch %x %d %x %d %d\n", nodeInfo, k, 313 cut, cut->tempNumber_, cut->numberPointingToThis()); 314 else 315 printf(" match %x %d %x %d %d\n", nodeInfo, k, 316 cut, cut->tempNumber_, cut->numberPointingToThis()); 317 cut->tempNumber_ = -1; 318 } 319 } 320 nodeInfo = nodeInfo->parent(); 321 } 322 } 323 324 return; 328 325 } 329 326 330 327 #endif /* CHECK_CUT_COUNTS */ 331 332 333 328 334 329 #ifdef CHECK_CUT_SIZE … … 337 332 Routine to verify that cut reference counts are correct. 338 333 */ 339 void verifyCutSize (const CbcTree *branchingTree, CbcModel &model)334 void verifyCutSize(const CbcTree *branchingTree, CbcModel &model) 340 335 { 341 336 342 int j;343 int nNodes = branchingTree->size();344 345 346 337 int j; 338 int nNodes = branchingTree->size(); 339 int totalCuts = 0; 340 341 /* 347 342 cut.tempNumber_ exists for the purpose of doing this verification. Clear it 348 343 in all cuts. We traverse the tree by starting from each live node and working 349 344 back to the root. At each CbcNodeInfo, check for cuts. 350 345 */ 351 for (j = 0 ; j < nNodes; j++) {352 CbcNode *node = branchingTree->nodePointer(j);353 CbcNodeInfo * nodeInfo = node->nodeInfo();354 assert (node->nodeInfo()->numberBranchesLeft());355 356 357 nodeInfo = nodeInfo->parent();358 359 360 printf("*** CHECKING cuts (size) after %d nodes - %d cuts\n", model.getNodeCount(), totalCuts);361 return;346 for (j = 0; j < nNodes; j++) { 347 CbcNode *node = branchingTree->nodePointer(j); 348 CbcNodeInfo *nodeInfo = node->nodeInfo(); 349 assert(node->nodeInfo()->numberBranchesLeft()); 350 while (nodeInfo) { 351 totalCuts += nodeInfo->numberCuts(); 352 nodeInfo = nodeInfo->parent(); 353 } 354 } 355 printf("*** CHECKING cuts (size) after %d nodes - %d cuts\n", model.getNodeCount(), totalCuts); 356 return; 362 357 } 363 358 … … 368 363 /* End unnamed namespace for CbcModel.cpp */ 369 364 370 371 void 372 CbcModel::analyzeObjective () 365 void CbcModel::analyzeObjective() 373 366 /* 374 367 Try to find a minimum change in the objective function. The first scan … … 387 380 */ 388 381 { 389 const double *objective = getObjCoefficients();390 const double *lower = getColLower();391 const double *upper = getColUpper();392 382 const double *objective = getObjCoefficients(); 383 const double *lower = getColLower(); 384 const double *upper = getColUpper(); 385 /* 393 386 Scan continuous and integer variables to see if continuous 394 387 are cover or network with integral rhs. 395 388 */ 396 double continuousMultiplier = 1.0; 397 double * coeffMultiplier = NULL; 398 double largestObj = 0.0; 399 double smallestObj = COIN_DBL_MAX; 400 { 401 const double *rowLower = getRowLower() ; 402 const double *rowUpper = getRowUpper() ; 403 int numberRows = solver_->getNumRows() ; 404 double * rhs = new double [numberRows]; 405 memset(rhs, 0, numberRows*sizeof(double)); 406 int iColumn; 407 int numberColumns = solver_->getNumCols() ; 408 // Column copy of matrix 409 int problemType = -1; 410 const double * element = solver_->getMatrixByCol()->getElements(); 411 const int * row = solver_->getMatrixByCol()->getIndices(); 412 const CoinBigIndex * columnStart = solver_->getMatrixByCol()->getVectorStarts(); 413 const int * columnLength = solver_->getMatrixByCol()->getVectorLengths(); 414 int numberInteger = 0; 415 int numberIntegerObj = 0; 416 int numberGeneralIntegerObj = 0; 417 int numberIntegerWeight = 0; 418 int numberContinuousObj = 0; 419 double cost = COIN_DBL_MAX; 420 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 421 if (upper[iColumn] == lower[iColumn]) { 422 CoinBigIndex start = columnStart[iColumn]; 423 CoinBigIndex end = start + columnLength[iColumn]; 424 for (CoinBigIndex j = start; j < end; j++) { 425 int iRow = row[j]; 426 rhs[iRow] += lower[iColumn] * element[j]; 427 } 428 } else { 429 double objValue = objective[iColumn]; 430 if (solver_->isInteger(iColumn)) 431 numberInteger++; 432 if (objValue) { 433 if (!solver_->isInteger(iColumn)) { 434 numberContinuousObj++; 435 } else { 436 largestObj = CoinMax(largestObj, fabs(objValue)); 437 smallestObj = CoinMin(smallestObj, fabs(objValue)); 438 numberIntegerObj++; 439 if (cost == COIN_DBL_MAX) 440 cost = objValue; 441 else if (cost != objValue) 442 cost = -COIN_DBL_MAX; 443 int gap = static_cast<int> (upper[iColumn] - lower[iColumn]); 444 if (gap > 1) { 445 numberGeneralIntegerObj++; 446 numberIntegerWeight += gap; 447 } 448 } 449 } 389 double continuousMultiplier = 1.0; 390 double *coeffMultiplier = NULL; 391 double largestObj = 0.0; 392 double smallestObj = COIN_DBL_MAX; 393 { 394 const double *rowLower = getRowLower(); 395 const double *rowUpper = getRowUpper(); 396 int numberRows = solver_->getNumRows(); 397 double *rhs = new double[numberRows]; 398 memset(rhs, 0, numberRows * sizeof(double)); 399 int iColumn; 400 int numberColumns = solver_->getNumCols(); 401 // Column copy of matrix 402 int problemType = -1; 403 const double *element = solver_->getMatrixByCol()->getElements(); 404 const int *row = solver_->getMatrixByCol()->getIndices(); 405 const CoinBigIndex *columnStart = solver_->getMatrixByCol()->getVectorStarts(); 406 const int *columnLength = solver_->getMatrixByCol()->getVectorLengths(); 407 int numberInteger = 0; 408 int numberIntegerObj = 0; 409 int numberGeneralIntegerObj = 0; 410 int numberIntegerWeight = 0; 411 int numberContinuousObj = 0; 412 double cost = COIN_DBL_MAX; 413 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 414 if (upper[iColumn] == lower[iColumn]) { 415 CoinBigIndex start = columnStart[iColumn]; 416 CoinBigIndex end = start + columnLength[iColumn]; 417 for (CoinBigIndex j = start; j < end; j++) { 418 int iRow = row[j]; 419 rhs[iRow] += lower[iColumn] * element[j]; 420 } 421 } else { 422 double objValue = objective[iColumn]; 423 if (solver_->isInteger(iColumn)) 424 numberInteger++; 425 if (objValue) { 426 if (!solver_->isInteger(iColumn)) { 427 numberContinuousObj++; 428 } else { 429 largestObj = CoinMax(largestObj, fabs(objValue)); 430 smallestObj = CoinMin(smallestObj, fabs(objValue)); 431 numberIntegerObj++; 432 if (cost == COIN_DBL_MAX) 433 cost = objValue; 434 else if (cost != objValue) 435 cost = -COIN_DBL_MAX; 436 int gap = static_cast<int>(upper[iColumn] - lower[iColumn]); 437 if (gap > 1) { 438 numberGeneralIntegerObj++; 439 numberIntegerWeight += gap; 450 440 } 451 } 452 int iType = 0; 453 if (!numberContinuousObj && numberIntegerObj <= 5 && numberIntegerWeight <= 100 && 454 numberIntegerObj*3 < numberObjects_ && !parentModel_ && solver_->getNumRows() > 100) 455 iType = 1 + 4 + (((moreSpecialOptions_&536870912)==0) ? 2 : 0); 456 else if (!numberContinuousObj && numberIntegerObj <= 100 && 457 numberIntegerObj*5 < numberObjects_ && numberIntegerWeight <= 100 && 458 !parentModel_ && 459 solver_->getNumRows() > 100 && cost != -COIN_DBL_MAX) 460 iType = 4 + (((moreSpecialOptions_&536870912)==0) ? 2 : 0); 461 else if (!numberContinuousObj && numberIntegerObj <= 100 && 462 numberIntegerObj*5 < numberObjects_ && 463 !parentModel_ && 464 solver_->getNumRows() > 100 && cost != -COIN_DBL_MAX) 465 iType = 8; 466 int iTest = getMaximumNodes(); 467 if (iTest >= 987654320 && iTest < 987654330 && numberObjects_ && !parentModel_) { 468 iType = iTest - 987654320; 469 printf("Testing %d integer variables out of %d objects (%d integer) have cost of %g - %d continuous\n", 470 numberIntegerObj, numberObjects_, numberInteger, cost, numberContinuousObj); 471 if (iType == 9) 472 exit(77); 473 if (numberContinuousObj) 474 iType = 0; 475 } 476 477 //if (!numberContinuousObj&&(numberIntegerObj<=5||cost!=-COIN_DBL_MAX)&& 478 //numberIntegerObj*3<numberObjects_&&!parentModel_&&solver_->getNumRows()>100) { 479 if (iType) { 480 /* 441 } 442 } 443 } 444 } 445 int iType = 0; 446 if (!numberContinuousObj && numberIntegerObj <= 5 && numberIntegerWeight <= 100 && numberIntegerObj * 3 < numberObjects_ && !parentModel_ && solver_->getNumRows() > 100) 447 iType = 1 + 4 + (((moreSpecialOptions_ & 536870912) == 0) ? 2 : 0); 448 else if (!numberContinuousObj && numberIntegerObj <= 100 && numberIntegerObj * 5 < numberObjects_ && numberIntegerWeight <= 100 && !parentModel_ && solver_->getNumRows() > 100 && cost != -COIN_DBL_MAX) 449 iType = 4 + (((moreSpecialOptions_ & 536870912) == 0) ? 2 : 0); 450 else if (!numberContinuousObj && numberIntegerObj <= 100 && numberIntegerObj * 5 < numberObjects_ && !parentModel_ && solver_->getNumRows() > 100 && cost != -COIN_DBL_MAX) 451 iType = 8; 452 int iTest = getMaximumNodes(); 453 if (iTest >= 987654320 && iTest < 987654330 && numberObjects_ && !parentModel_) { 454 iType = iTest - 987654320; 455 printf("Testing %d integer variables out of %d objects (%d integer) have cost of %g - %d continuous\n", 456 numberIntegerObj, numberObjects_, numberInteger, cost, numberContinuousObj); 457 if (iType == 9) 458 exit(77); 459 if (numberContinuousObj) 460 iType = 0; 461 } 462 463 //if (!numberContinuousObj&&(numberIntegerObj<=5||cost!=-COIN_DBL_MAX)&& 464 //numberIntegerObj*3<numberObjects_&&!parentModel_&&solver_->getNumRows()>100) { 465 if (iType) { 466 /* 481 467 A) put high priority on (if none) 482 468 B) create artificial objective (if clp) 483 469 */ 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 << general << CoinMessageEol;511 512 513 514 515 516 517 << general << CoinMessageEol;518 519 520 521 522 CbcSimpleInteger * thisOne = dynamic_cast <CbcSimpleInteger *>(object_[i]);523 524 525 526 527 528 529 530 470 int iPriority = -1; 471 for (int i = 0; i < numberObjects_; i++) { 472 int k = object_[i]->priority(); 473 if (iPriority == -1) 474 iPriority = k; 475 else if (iPriority != k) 476 iPriority = -2; 477 } 478 bool branchOnSatisfied = ((iType & 1) != 0); 479 bool createFake = ((iType & 2) != 0); 480 bool randomCost = ((iType & 4) != 0); 481 if (iPriority >= 0) { 482 char general[200]; 483 if (cost == -COIN_DBL_MAX) { 484 sprintf(general, "%d integer variables out of %d objects (%d integer) have costs - high priority", 485 numberIntegerObj, numberObjects_, numberInteger); 486 } else if (cost == COIN_DBL_MAX) { 487 sprintf(general, "No integer variables out of %d objects (%d integer) have costs", 488 numberObjects_, numberInteger); 489 branchOnSatisfied = false; 490 } else { 491 sprintf(general, "%d integer variables out of %d objects (%d integer) have cost of %g - high priority", 492 numberIntegerObj, numberObjects_, numberInteger, cost); 493 } 494 messageHandler()->message(CBC_GENERAL, 495 messages()) 496 << general << CoinMessageEol; 497 sprintf(general, "branch on satisfied %c create fake objective %c random cost %c", 498 branchOnSatisfied ? 'Y' : 'N', 499 createFake ? 'Y' : 'N', 500 randomCost ? 'Y' : 'N'); 501 messageHandler()->message(CBC_GENERAL, 502 messages()) 503 << general << CoinMessageEol; 504 // switch off clp type branching 505 // no ? fastNodeDepth_ = -1; 506 int highPriority = (branchOnSatisfied) ? -999 : 100; 507 for (int i = 0; i < numberObjects_; i++) { 508 CbcSimpleInteger *thisOne = dynamic_cast<CbcSimpleInteger *>(object_[i]); 509 object_[i]->setPriority(1000); 510 if (thisOne) { 511 int iColumn = thisOne->columnNumber(); 512 if (objective[iColumn]) 513 thisOne->setPriority(highPriority); 514 } 515 } 516 } 531 517 #ifdef COIN_HAS_CLP 532 OsiClpSolverInterface *clpSolver533 = dynamic_cast<OsiClpSolverInterface *>(solver_);534 535 536 537 double * fakeObj = new double[numberColumns];538 539 const CoinPackedMatrix *matrixByCol = clpSolver->getMatrixByCol();540 541 542 543 const int *columnLength = matrixByCol->getVectorLengths();544 const double *solution = clpSolver->getColSolution();518 OsiClpSolverInterface *clpSolver 519 = dynamic_cast<OsiClpSolverInterface *>(solver_); 520 if (clpSolver && createFake) { 521 // Create artificial objective to be used when all else fixed 522 int numberColumns = clpSolver->getNumCols(); 523 double *fakeObj = new double[numberColumns]; 524 // Column copy 525 const CoinPackedMatrix *matrixByCol = clpSolver->getMatrixByCol(); 526 //const double * element = matrixByCol.getElements(); 527 //const int * row = matrixByCol.getIndices(); 528 //const CoinBigIndex * columnStart = matrixByCol.getVectorStarts(); 529 const int *columnLength = matrixByCol->getVectorLengths(); 530 const double *solution = clpSolver->getColSolution(); 545 531 #ifdef JJF_ZERO 546 int nAtBound = 0; 547 for (int i = 0; i < numberColumns; i++) { 548 double lowerValue = lower[i]; 549 double upperValue = upper[i]; 550 if (clpSolver->isInteger(i)) { 551 double lowerValue = lower[i]; 552 double upperValue = upper[i]; 553 double value = solution[i]; 554 if (value < lowerValue + 1.0e-6 || 555 value > upperValue - 1.0e-6) 556 nAtBound++; 557 } 558 } 559 #endif 560 /* 532 int nAtBound = 0; 533 for (int i = 0; i < numberColumns; i++) { 534 double lowerValue = lower[i]; 535 double upperValue = upper[i]; 536 if (clpSolver->isInteger(i)) { 537 double lowerValue = lower[i]; 538 double upperValue = upper[i]; 539 double value = solution[i]; 540 if (value < lowerValue + 1.0e-6 || value > upperValue - 1.0e-6) 541 nAtBound++; 542 } 543 } 544 #endif 545 /* 561 546 Generate a random objective function for problems where the given objective 562 547 function is not terribly useful. (Nearly feasible, single integer variable, 563 548 that sort of thing. 564 549 */ 565 CoinDrand48(true, 1234567); 566 for (int i = 0; i < numberColumns; i++) { 567 double lowerValue = lower[i]; 568 double upperValue = upper[i]; 569 double value = (randomCost) ? ceil((CoinDrand48() + 0.5) * 1000) 570 : i + 1 + columnLength[i] * 1000; 571 value *= 0.001; 572 //value += columnLength[i]; 573 if (lowerValue > -1.0e5 || upperValue < 1.0e5) { 574 if (fabs(lowerValue) > fabs(upperValue)) 575 value = - value; 576 if (clpSolver->isInteger(i)) { 577 double solValue = solution[i]; 578 // Better to add in 0.5 or 1.0?? 579 if (solValue < lowerValue + 1.0e-6) 580 value = fabs(value) + 0.5; //fabs(value*1.5); 581 else if (solValue > upperValue - 1.0e-6) 582 value = -fabs(value) - 0.5; //-fabs(value*1.5); 583 } 584 } else { 585 value = 0.0; 586 } 587 fakeObj[i] = value; 588 } 589 // pass to solver 590 clpSolver->setFakeObjective(fakeObj); 591 delete [] fakeObj; 550 CoinDrand48(true, 1234567); 551 for (int i = 0; i < numberColumns; i++) { 552 double lowerValue = lower[i]; 553 double upperValue = upper[i]; 554 double value = (randomCost) ? ceil((CoinDrand48() + 0.5) * 1000) 555 : i + 1 + columnLength[i] * 1000; 556 value *= 0.001; 557 //value += columnLength[i]; 558 if (lowerValue > -1.0e5 || upperValue < 1.0e5) { 559 if (fabs(lowerValue) > fabs(upperValue)) 560 value = -value; 561 if (clpSolver->isInteger(i)) { 562 double solValue = solution[i]; 563 // Better to add in 0.5 or 1.0?? 564 if (solValue < lowerValue + 1.0e-6) 565 value = fabs(value) + 0.5; //fabs(value*1.5); 566 else if (solValue > upperValue - 1.0e-6) 567 value = -fabs(value) - 0.5; //-fabs(value*1.5); 592 568 } 593 #endif 594 } else if (largestObj < smallestObj*5.0 && !parentModel_ && 595 !numberContinuousObj && 596 !numberGeneralIntegerObj && 597 numberIntegerObj*2 < CoinMin(numberColumns,20)) { 598 // up priorities on costed 599 int iPriority = -1; 600 for (int i = 0; i < numberObjects_; i++) { 601 int k = object_[i]->priority(); 602 if (iPriority == -1) 603 iPriority = k; 604 else if (iPriority != k) 605 iPriority = -2; 569 } else { 570 value = 0.0; 571 } 572 fakeObj[i] = value; 573 } 574 // pass to solver 575 clpSolver->setFakeObjective(fakeObj); 576 delete[] fakeObj; 577 } 578 #endif 579 } else if (largestObj < smallestObj * 5.0 && !parentModel_ && !numberContinuousObj && !numberGeneralIntegerObj && numberIntegerObj * 2 < CoinMin(numberColumns, 20)) { 580 // up priorities on costed 581 int iPriority = -1; 582 for (int i = 0; i < numberObjects_; i++) { 583 int k = object_[i]->priority(); 584 if (iPriority == -1) 585 iPriority = k; 586 else if (iPriority != k) 587 iPriority = -2; 588 } 589 if (iPriority >= 100) { 590 #if CBC_USEFUL_PRINTING > 1 591 printf("Setting variables with obj to high priority\n"); 592 #endif 593 for (int i = 0; i < numberObjects_; i++) { 594 CbcSimpleInteger *obj = dynamic_cast<CbcSimpleInteger *>(object_[i]); 595 if (obj) { 596 int iColumn = obj->columnNumber(); 597 if (objective[iColumn]) 598 object_[i]->setPriority(iPriority - 1); 599 } 600 } 601 } 602 } 603 int iRow; 604 for (iRow = 0; iRow < numberRows; iRow++) { 605 if (rowLower[iRow] > -1.0e20 && fabs(rowLower[iRow] - rhs[iRow] - floor(rowLower[iRow] - rhs[iRow] + 0.5)) > 1.0e-10) { 606 continuousMultiplier = 0.0; 607 break; 608 } 609 if (rowUpper[iRow] < 1.0e20 && fabs(rowUpper[iRow] - rhs[iRow] - floor(rowUpper[iRow] - rhs[iRow] + 0.5)) > 1.0e-10) { 610 continuousMultiplier = 0.0; 611 break; 612 } 613 // set rhs to limiting value 614 if (rowLower[iRow] != rowUpper[iRow]) { 615 if (rowLower[iRow] > -1.0e20) { 616 if (rowUpper[iRow] < 1.0e20) { 617 // no good 618 continuousMultiplier = 0.0; 619 break; 620 } else { 621 rhs[iRow] = rowLower[iRow] - rhs[iRow]; 622 if (problemType < 0) 623 problemType = 3; // set cover 624 else if (problemType != 3) 625 problemType = 4; 626 } 627 } else { 628 rhs[iRow] = rowUpper[iRow] - rhs[iRow]; 629 if (problemType < 0) 630 problemType = 1; // set partitioning <= 631 else if (problemType != 1) 632 problemType = 4; 633 } 634 } else { 635 rhs[iRow] = rowUpper[iRow] - rhs[iRow]; 636 if (problemType < 0) 637 problemType = 3; // set partitioning == 638 else if (problemType != 2) 639 problemType = 2; 640 } 641 if (fabs(rhs[iRow] - 1.0) > 1.0e-12) 642 problemType = 4; 643 } 644 if (continuousMultiplier) { 645 // 1 network, 2 cover, 4 negative cover 646 int possible = 7; 647 bool unitRhs = true; 648 // See which rows could be set cover 649 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 650 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 651 CoinBigIndex start = columnStart[iColumn]; 652 CoinBigIndex end = start + columnLength[iColumn]; 653 for (CoinBigIndex j = start; j < end; j++) { 654 double value = element[j]; 655 if (value == 1.0) { 656 } else if (value == -1.0) { 657 rhs[row[j]] = -0.5; 658 } else { 659 rhs[row[j]] = -COIN_DBL_MAX; 606 660 } 607 if (iPriority >= 100) { 608 #if CBC_USEFUL_PRINTING>1 609 printf("Setting variables with obj to high priority\n"); 610 #endif 611 for (int i = 0; i < numberObjects_; i++) { 612 CbcSimpleInteger * obj = 613 dynamic_cast <CbcSimpleInteger *>(object_[i]) ; 614 if (obj) { 615 int iColumn = obj->columnNumber(); 616 if (objective[iColumn]) 617 object_[i]->setPriority(iPriority - 1); 618 } 619 } 661 } 662 } 663 } 664 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 665 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 666 if (!isInteger(iColumn)) { 667 CoinBigIndex start = columnStart[iColumn]; 668 CoinBigIndex end = start + columnLength[iColumn]; 669 double rhsValue = 0.0; 670 // 1 all ones, -1 all -1s, 2 all +- 1, 3 no good 671 int type = 0; 672 for (CoinBigIndex j = start; j < end; j++) { 673 double value = element[j]; 674 if (fabs(value) != 1.0) { 675 type = 3; 676 break; 677 } else if (value == 1.0) { 678 if (!type) 679 type = 1; 680 else if (type != 1) 681 type = 2; 682 } else { 683 if (!type) 684 type = -1; 685 else if (type != -1) 686 type = 2; 687 } 688 int iRow = row[j]; 689 if (rhs[iRow] == -COIN_DBL_MAX) { 690 type = 3; 691 break; 692 } else if (rhs[iRow] == -0.5) { 693 // different values 694 unitRhs = false; 695 } else if (rhsValue) { 696 if (rhsValue != rhs[iRow]) 697 unitRhs = false; 698 } else { 699 rhsValue = rhs[iRow]; 700 } 620 701 } 621 } 622 int iRow; 623 for (iRow = 0; iRow < numberRows; iRow++) { 624 if (rowLower[iRow] > -1.0e20 && 625 fabs(rowLower[iRow] - rhs[iRow] - floor(rowLower[iRow] - rhs[iRow] + 0.5)) > 1.0e-10) { 626 continuousMultiplier = 0.0; 702 // if no elements OK 703 if (type == 3) { 704 // no good 705 possible = 0; 706 break; 707 } else if (type == 2) { 708 if (end - start > 2) { 709 // no good 710 possible = 0; 711 break; 712 } else { 713 // only network 714 possible &= 1; 715 if (!possible) 716 break; 717 } 718 } else if (type == 1) { 719 // only cover 720 possible &= 2; 721 if (!possible) 722 break; 723 } else if (type == -1) { 724 // only negative cover 725 possible &= 4; 726 if (!possible) 627 727 break; 628 728 } 629 if (rowUpper[iRow] < 1.0e20 && 630 fabs(rowUpper[iRow] - rhs[iRow] - floor(rowUpper[iRow] - rhs[iRow] + 0.5)) > 1.0e-10) { 631 continuousMultiplier = 0.0; 729 } 730 } 731 } 732 if ((possible == 2 || possible == 4) && !unitRhs) { 733 #if COIN_DEVELOP > 1 734 printf("XXXXXX Continuous all +1 but different rhs\n"); 735 #endif 736 possible = 0; 737 } 738 // may be all integer 739 if (possible != 7) { 740 if (!possible) 741 continuousMultiplier = 0.0; 742 else if (possible == 1) 743 continuousMultiplier = 1.0; 744 else 745 continuousMultiplier = 0.0; // 0.5 was incorrect; 746 #if COIN_DEVELOP > 1 747 if (continuousMultiplier) 748 printf("XXXXXX multiplier of %g\n", continuousMultiplier); 749 #endif 750 if (continuousMultiplier == 0.5) { 751 coeffMultiplier = new double[numberColumns]; 752 bool allOne = true; 753 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 754 coeffMultiplier[iColumn] = 1.0; 755 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 756 if (!isInteger(iColumn)) { 757 CoinBigIndex start = columnStart[iColumn]; 758 int iRow = row[start]; 759 double value = rhs[iRow]; 760 assert(value >= 0.0); 761 if (value != 0.0 && value != 1.0) 762 allOne = false; 763 coeffMultiplier[iColumn] = 0.5 * value; 764 } 765 } 766 } 767 if (allOne) { 768 // back to old way 769 delete[] coeffMultiplier; 770 coeffMultiplier = NULL; 771 } 772 } 773 } else { 774 // all integer 775 problemType_ = problemType; 776 #if COIN_DEVELOP > 1 777 printf("Problem type is %d\n", problemType_); 778 #endif 779 } 780 } 781 782 // But try again 783 if (continuousMultiplier < 1.0) { 784 memset(rhs, 0, numberRows * sizeof(double)); 785 int *count = new int[numberRows]; 786 memset(count, 0, numberRows * sizeof(int)); 787 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 788 CoinBigIndex start = columnStart[iColumn]; 789 CoinBigIndex end = start + columnLength[iColumn]; 790 if (upper[iColumn] == lower[iColumn]) { 791 for (CoinBigIndex j = start; j < end; j++) { 792 int iRow = row[j]; 793 rhs[iRow] += lower[iColumn] * element[j]; 794 } 795 } else if (solver_->isInteger(iColumn)) { 796 for (CoinBigIndex j = start; j < end; j++) { 797 int iRow = row[j]; 798 if (fabs(element[j] - floor(element[j] + 0.5)) > 1.0e-10) 799 rhs[iRow] = COIN_DBL_MAX; 800 } 801 } else { 802 for (CoinBigIndex j = start; j < end; j++) { 803 int iRow = row[j]; 804 count[iRow]++; 805 if (fabs(element[j]) != 1.0) 806 rhs[iRow] = COIN_DBL_MAX; 807 } 808 } 809 } 810 // now look at continuous 811 bool allGood = true; 812 double direction = solver_->getObjSense(); 813 int numberObj = 0; 814 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 815 if (upper[iColumn] > lower[iColumn]) { 816 double objValue = objective[iColumn] * direction; 817 if (objValue && !solver_->isInteger(iColumn)) { 818 numberObj++; 819 CoinBigIndex start = columnStart[iColumn]; 820 CoinBigIndex end = start + columnLength[iColumn]; 821 if (objValue > 0.0) { 822 // wants to be as low as possible 823 if (lower[iColumn] < -1.0e10 || fabs(lower[iColumn] - floor(lower[iColumn] + 0.5)) > 1.0e-10) { 824 allGood = false; 825 break; 826 } else if (upper[iColumn] < 1.0e10 && fabs(upper[iColumn] - floor(upper[iColumn] + 0.5)) > 1.0e-10) { 827 allGood = false; 828 break; 829 } 830 bool singletonRow = true; 831 bool equality = false; 832 for (CoinBigIndex j = start; j < end; j++) { 833 int iRow = row[j]; 834 if (count[iRow] > 1) 835 singletonRow = false; 836 else if (rowLower[iRow] == rowUpper[iRow]) 837 equality = true; 838 double rhsValue = rhs[iRow]; 839 double lowerValue = rowLower[iRow]; 840 double upperValue = rowUpper[iRow]; 841 if (rhsValue < 1.0e20) { 842 if (lowerValue > -1.0e20) 843 lowerValue -= rhsValue; 844 if (upperValue < 1.0e20) 845 upperValue -= rhsValue; 846 } 847 if (fabs(rhsValue) > 1.0e20 || fabs(rhsValue - floor(rhsValue + 0.5)) > 1.0e-10 848 || fabs(element[j]) != 1.0) { 849 // no good 850 allGood = false; 851 break; 852 } 853 if (element[j] > 0.0) { 854 if (lowerValue > -1.0e20 && fabs(lowerValue - floor(lowerValue + 0.5)) > 1.0e-10) { 855 // no good 856 allGood = false; 857 break; 858 } 859 } else { 860 if (upperValue < 1.0e20 && fabs(upperValue - floor(upperValue + 0.5)) > 1.0e-10) { 861 // no good 862 allGood = false; 863 break; 864 } 865 } 866 } 867 if (!singletonRow && end > start + 1 && !equality) 868 allGood = false; 869 if (!allGood) 870 break; 871 } else { 872 // wants to be as high as possible 873 if (upper[iColumn] > 1.0e10 || fabs(upper[iColumn] - floor(upper[iColumn] + 0.5)) > 1.0e-10) { 874 allGood = false; 875 break; 876 } else if (lower[iColumn] > -1.0e10 && fabs(lower[iColumn] - floor(lower[iColumn] + 0.5)) > 1.0e-10) { 877 allGood = false; 878 break; 879 } 880 bool singletonRow = true; 881 bool equality = false; 882 for (CoinBigIndex j = start; j < end; j++) { 883 int iRow = row[j]; 884 if (count[iRow] > 1) 885 singletonRow = false; 886 else if (rowLower[iRow] == rowUpper[iRow]) 887 equality = true; 888 double rhsValue = rhs[iRow]; 889 double lowerValue = rowLower[iRow]; 890 double upperValue = rowUpper[iRow]; 891 if (rhsValue < 1.0e20) { 892 if (lowerValue > -1.0e20) 893 lowerValue -= rhsValue; 894 if (upperValue < 1.0e20) 895 upperValue -= rhsValue; 896 } 897 if (fabs(rhsValue) > 1.0e20 || fabs(rhsValue - floor(rhsValue + 0.5)) > 1.0e-10 898 || fabs(element[j]) != 1.0) { 899 // no good 900 allGood = false; 901 break; 902 } 903 if (element[j] < 0.0) { 904 if (lowerValue > -1.0e20 && fabs(lowerValue - floor(lowerValue + 0.5)) > 1.0e-10) { 905 // no good 906 allGood = false; 907 break; 908 } 909 } else { 910 if (upperValue < 1.0e20 && fabs(upperValue - floor(upperValue + 0.5)) > 1.0e-10) { 911 // no good 912 allGood = false; 913 break; 914 } 915 } 916 } 917 if (!singletonRow && end > start + 1 && !equality) 918 allGood = false; 919 if (!allGood) 632 920 break; 633 921 } 634 // set rhs to limiting value 635 if (rowLower[iRow] != rowUpper[iRow]) { 636 if (rowLower[iRow] > -1.0e20) { 637 if (rowUpper[iRow] < 1.0e20) { 638 // no good 639 continuousMultiplier = 0.0; 640 break; 641 } else { 642 rhs[iRow] = rowLower[iRow] - rhs[iRow]; 643 if (problemType < 0) 644 problemType = 3; // set cover 645 else if (problemType != 3) 646 problemType = 4; 647 } 648 } else { 649 rhs[iRow] = rowUpper[iRow] - rhs[iRow]; 650 if (problemType < 0) 651 problemType = 1; // set partitioning <= 652 else if (problemType != 1) 653 problemType = 4; 654 } 655 } else { 656 rhs[iRow] = rowUpper[iRow] - rhs[iRow]; 657 if (problemType < 0) 658 problemType = 3; // set partitioning == 659 else if (problemType != 2) 660 problemType = 2; 661 } 662 if (fabs(rhs[iRow] - 1.0) > 1.0e-12) 663 problemType = 4; 664 } 665 if (continuousMultiplier) { 666 // 1 network, 2 cover, 4 negative cover 667 int possible = 7; 668 bool unitRhs = true; 669 // See which rows could be set cover 670 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 671 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 672 CoinBigIndex start = columnStart[iColumn]; 673 CoinBigIndex end = start + columnLength[iColumn]; 674 for (CoinBigIndex j = start; j < end; j++) { 675 double value = element[j]; 676 if (value == 1.0) { 677 } else if (value == -1.0) { 678 rhs[row[j]] = -0.5; 679 } else { 680 rhs[row[j]] = -COIN_DBL_MAX; 681 } 682 } 683 } 684 } 685 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 686 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 687 if (!isInteger(iColumn)) { 688 CoinBigIndex start = columnStart[iColumn]; 689 CoinBigIndex end = start + columnLength[iColumn]; 690 double rhsValue = 0.0; 691 // 1 all ones, -1 all -1s, 2 all +- 1, 3 no good 692 int type = 0; 693 for (CoinBigIndex j = start; j < end; j++) { 694 double value = element[j]; 695 if (fabs(value) != 1.0) { 696 type = 3; 697 break; 698 } else if (value == 1.0) { 699 if (!type) 700 type = 1; 701 else if (type != 1) 702 type = 2; 703 } else { 704 if (!type) 705 type = -1; 706 else if (type != -1) 707 type = 2; 708 } 709 int iRow = row[j]; 710 if (rhs[iRow] == -COIN_DBL_MAX) { 711 type = 3; 712 break; 713 } else if (rhs[iRow] == -0.5) { 714 // different values 715 unitRhs = false; 716 } else if (rhsValue) { 717 if (rhsValue != rhs[iRow]) 718 unitRhs = false; 719 } else { 720 rhsValue = rhs[iRow]; 721 } 722 } 723 // if no elements OK 724 if (type == 3) { 725 // no good 726 possible = 0; 727 break; 728 } else if (type == 2) { 729 if (end - start > 2) { 730 // no good 731 possible = 0; 732 break; 733 } else { 734 // only network 735 possible &= 1; 736 if (!possible) 737 break; 738 } 739 } else if (type == 1) { 740 // only cover 741 possible &= 2; 742 if (!possible) 743 break; 744 } else if (type == -1) { 745 // only negative cover 746 possible &= 4; 747 if (!possible) 748 break; 749 } 750 } 751 } 752 } 753 if ((possible == 2 || possible == 4) && !unitRhs) { 754 #if COIN_DEVELOP>1 755 printf("XXXXXX Continuous all +1 but different rhs\n"); 756 #endif 757 possible = 0; 758 } 759 // may be all integer 760 if (possible != 7) { 761 if (!possible) 762 continuousMultiplier = 0.0; 763 else if (possible == 1) 764 continuousMultiplier = 1.0; 765 else 766 continuousMultiplier = 0.0; // 0.5 was incorrect; 767 #if COIN_DEVELOP>1 768 if (continuousMultiplier) 769 printf("XXXXXX multiplier of %g\n", continuousMultiplier); 770 #endif 771 if (continuousMultiplier == 0.5) { 772 coeffMultiplier = new double [numberColumns]; 773 bool allOne = true; 774 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 775 coeffMultiplier[iColumn] = 1.0; 776 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 777 if (!isInteger(iColumn)) { 778 CoinBigIndex start = columnStart[iColumn]; 779 int iRow = row[start]; 780 double value = rhs[iRow]; 781 assert (value >= 0.0); 782 if (value != 0.0 && value != 1.0) 783 allOne = false; 784 coeffMultiplier[iColumn] = 0.5 * value; 785 } 786 } 787 } 788 if (allOne) { 789 // back to old way 790 delete [] coeffMultiplier; 791 coeffMultiplier = NULL; 792 } 793 } 794 } else { 795 // all integer 796 problemType_ = problemType; 797 #if COIN_DEVELOP>1 798 printf("Problem type is %d\n", problemType_); 799 #endif 800 } 801 } 802 803 // But try again 804 if (continuousMultiplier < 1.0) { 805 memset(rhs, 0, numberRows*sizeof(double)); 806 int * count = new int [numberRows]; 807 memset(count, 0, numberRows*sizeof(int)); 808 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 809 CoinBigIndex start = columnStart[iColumn]; 810 CoinBigIndex end = start + columnLength[iColumn]; 811 if (upper[iColumn] == lower[iColumn]) { 812 for (CoinBigIndex j = start; j < end; j++) { 813 int iRow = row[j]; 814 rhs[iRow] += lower[iColumn] * element[j]; 815 } 816 } else if (solver_->isInteger(iColumn)) { 817 for (CoinBigIndex j = start; j < end; j++) { 818 int iRow = row[j]; 819 if (fabs(element[j] - floor(element[j] + 0.5)) > 1.0e-10) 820 rhs[iRow] = COIN_DBL_MAX; 821 } 822 } else { 823 for (CoinBigIndex j = start; j < end; j++) { 824 int iRow = row[j]; 825 count[iRow]++; 826 if (fabs(element[j]) != 1.0) 827 rhs[iRow] = COIN_DBL_MAX; 828 } 829 } 830 } 831 // now look at continuous 832 bool allGood = true; 833 double direction = solver_->getObjSense() ; 834 int numberObj = 0; 835 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 836 if (upper[iColumn] > lower[iColumn]) { 837 double objValue = objective[iColumn] * direction; 838 if (objValue && !solver_->isInteger(iColumn)) { 839 numberObj++; 840 CoinBigIndex start = columnStart[iColumn]; 841 CoinBigIndex end = start + columnLength[iColumn]; 842 if (objValue > 0.0) { 843 // wants to be as low as possible 844 if (lower[iColumn] < -1.0e10 || fabs(lower[iColumn] - floor(lower[iColumn] + 0.5)) > 1.0e-10) { 845 allGood = false; 846 break; 847 } else if (upper[iColumn] < 1.0e10 && fabs(upper[iColumn] - floor(upper[iColumn] + 0.5)) > 1.0e-10) { 848 allGood = false; 849 break; 850 } 851 bool singletonRow = true; 852 bool equality = false; 853 for (CoinBigIndex j = start; j < end; j++) { 854 int iRow = row[j]; 855 if (count[iRow] > 1) 856 singletonRow = false; 857 else if (rowLower[iRow] == rowUpper[iRow]) 858 equality = true; 859 double rhsValue = rhs[iRow]; 860 double lowerValue = rowLower[iRow]; 861 double upperValue = rowUpper[iRow]; 862 if (rhsValue < 1.0e20) { 863 if (lowerValue > -1.0e20) 864 lowerValue -= rhsValue; 865 if (upperValue < 1.0e20) 866 upperValue -= rhsValue; 867 } 868 if (fabs(rhsValue) > 1.0e20 || fabs(rhsValue - floor(rhsValue + 0.5)) > 1.0e-10 869 || fabs(element[j]) != 1.0) { 870 // no good 871 allGood = false; 872 break; 873 } 874 if (element[j] > 0.0) { 875 if (lowerValue > -1.0e20 && fabs(lowerValue - floor(lowerValue + 0.5)) > 1.0e-10) { 876 // no good 877 allGood = false; 878 break; 879 } 880 } else { 881 if (upperValue < 1.0e20 && fabs(upperValue - floor(upperValue + 0.5)) > 1.0e-10) { 882 // no good 883 allGood = false; 884 break; 885 } 886 } 887 } 888 if (!singletonRow && end > start + 1 && !equality) 889 allGood = false; 890 if (!allGood) 891 break; 892 } else { 893 // wants to be as high as possible 894 if (upper[iColumn] > 1.0e10 || fabs(upper[iColumn] - floor(upper[iColumn] + 0.5)) > 1.0e-10) { 895 allGood = false; 896 break; 897 } else if (lower[iColumn] > -1.0e10 && fabs(lower[iColumn] - floor(lower[iColumn] + 0.5)) > 1.0e-10) { 898 allGood = false; 899 break; 900 } 901 bool singletonRow = true; 902 bool equality = false; 903 for (CoinBigIndex j = start; j < end; j++) { 904 int iRow = row[j]; 905 if (count[iRow] > 1) 906 singletonRow = false; 907 else if (rowLower[iRow] == rowUpper[iRow]) 908 equality = true; 909 double rhsValue = rhs[iRow]; 910 double lowerValue = rowLower[iRow]; 911 double upperValue = rowUpper[iRow]; 912 if (rhsValue < 1.0e20) { 913 if (lowerValue > -1.0e20) 914 lowerValue -= rhsValue; 915 if (upperValue < 1.0e20) 916 upperValue -= rhsValue; 917 } 918 if (fabs(rhsValue) > 1.0e20 || fabs(rhsValue - floor(rhsValue + 0.5)) > 1.0e-10 919 || fabs(element[j]) != 1.0) { 920 // no good 921 allGood = false; 922 break; 923 } 924 if (element[j] < 0.0) { 925 if (lowerValue > -1.0e20 && fabs(lowerValue - floor(lowerValue + 0.5)) > 1.0e-10) { 926 // no good 927 allGood = false; 928 break; 929 } 930 } else { 931 if (upperValue < 1.0e20 && fabs(upperValue - floor(upperValue + 0.5)) > 1.0e-10) { 932 // no good 933 allGood = false; 934 break; 935 } 936 } 937 } 938 if (!singletonRow && end > start + 1 && !equality) 939 allGood = false; 940 if (!allGood) 941 break; 942 } 943 } 944 } 945 } 946 delete [] count; 947 if (allGood) { 948 #if COIN_DEVELOP>1 949 if (numberObj) 950 printf("YYYY analysis says all continuous with costs will be integer\n"); 951 #endif 952 continuousMultiplier = 1.0; 953 } 954 } 955 delete [] rhs; 956 } 957 /* 922 } 923 } 924 } 925 delete[] count; 926 if (allGood) { 927 #if COIN_DEVELOP > 1 928 if (numberObj) 929 printf("YYYY analysis says all continuous with costs will be integer\n"); 930 #endif 931 continuousMultiplier = 1.0; 932 } 933 } 934 delete[] rhs; 935 } 936 /* 958 937 Take a first scan to see if there are unfixed continuous variables in the 959 938 objective. If so, the minimum objective change could be arbitrarily small. … … 963 942 fathoming discipline to strict. 964 943 */ 965 double maximumCost = 0.0;966 967 int iColumn;968 int numberColumns = getNumCols();969 970 944 double maximumCost = 0.0; 945 //double trueIncrement=0.0; 946 int iColumn; 947 int numberColumns = getNumCols(); 948 double scaleFactor = 1.0; // due to rhs etc 949 /* 971 950 Original model did not have integer bounds. 972 951 */ 973 if ((specialOptions_&65536) == 0) {974 952 if ((specialOptions_ & 65536) == 0) { 953 /* be on safe side (later look carefully as may be able to 975 954 to get 0.5 say if bounds are multiples of 0.5 */ 976 for (iColumn = 0 ; iColumn < numberColumns ; iColumn++) { 977 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 978 double value; 979 value = fabs(lower[iColumn]); 980 if (floor(value + 0.5) != value) { 981 scaleFactor = CoinMin(scaleFactor, 0.5); 982 if (floor(2.0*value + 0.5) != 2.0*value) { 983 scaleFactor = CoinMin(scaleFactor, 0.25); 984 if (floor(4.0*value + 0.5) != 4.0*value) { 985 scaleFactor = 0.0; 986 } 987 } 988 } 989 value = fabs(upper[iColumn]); 990 if (floor(value + 0.5) != value) { 991 scaleFactor = CoinMin(scaleFactor, 0.5); 992 if (floor(2.0*value + 0.5) != 2.0*value) { 993 scaleFactor = CoinMin(scaleFactor, 0.25); 994 if (floor(4.0*value + 0.5) != 4.0*value) { 995 scaleFactor = 0.0; 996 } 997 } 998 } 955 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 956 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 957 double value; 958 value = fabs(lower[iColumn]); 959 if (floor(value + 0.5) != value) { 960 scaleFactor = CoinMin(scaleFactor, 0.5); 961 if (floor(2.0 * value + 0.5) != 2.0 * value) { 962 scaleFactor = CoinMin(scaleFactor, 0.25); 963 if (floor(4.0 * value + 0.5) != 4.0 * value) { 964 scaleFactor = 0.0; 999 965 } 1000 } 1001 } 1002 bool possibleMultiple = continuousMultiplier != 0.0 && scaleFactor != 0.0 ; 1003 if (possibleMultiple) { 1004 for (iColumn = 0 ; iColumn < numberColumns ; iColumn++) { 1005 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 1006 maximumCost = CoinMax(maximumCost, fabs(objective[iColumn])) ; 966 } 967 } 968 value = fabs(upper[iColumn]); 969 if (floor(value + 0.5) != value) { 970 scaleFactor = CoinMin(scaleFactor, 0.5); 971 if (floor(2.0 * value + 0.5) != 2.0 * value) { 972 scaleFactor = CoinMin(scaleFactor, 0.25); 973 if (floor(4.0 * value + 0.5) != 4.0 * value) { 974 scaleFactor = 0.0; 1007 975 } 1008 } 1009 } 1010 setIntParam(CbcModel::CbcFathomDiscipline, possibleMultiple) ; 1011 /* 976 } 977 } 978 } 979 } 980 } 981 bool possibleMultiple = continuousMultiplier != 0.0 && scaleFactor != 0.0; 982 if (possibleMultiple) { 983 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 984 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 985 maximumCost = CoinMax(maximumCost, fabs(objective[iColumn])); 986 } 987 } 988 } 989 setIntParam(CbcModel::CbcFathomDiscipline, possibleMultiple); 990 /* 1012 991 If a nontrivial increment is possible, try and figure it out. We're looking 1013 992 for gcd(c<j>) for all c<j> that are coefficients of unfixed integer … … 1018 997 2520.0 is used as it is a nice multiple of 2,3,5,7 1019 998 */ 1020 if (possibleMultiple && maximumCost) { 1021 int increment = 0 ; 1022 double multiplier = 2520.0 ; 1023 while (10.0*multiplier*maximumCost < 1.0e8) 1024 multiplier *= 10.0 ; 1025 int bigIntegers = 0; // Count of large costs which are integer 1026 for (iColumn = 0 ; iColumn < numberColumns ; iColumn++) { 1027 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 1028 double objValue = fabs(objective[iColumn]); 1029 if (!isInteger(iColumn)) { 1030 if (!coeffMultiplier) 1031 objValue *= continuousMultiplier; 1032 else 1033 objValue *= coeffMultiplier[iColumn]; 1034 } 1035 if (objValue) { 1036 double value = objValue * multiplier ; 1037 if (value < 2.1e9) { 1038 int nearest = static_cast<int> (floor(value + 0.5)) ; 1039 if (fabs(value - floor(value + 0.5)) > 1.0e-8) { 1040 increment = 0 ; 1041 break ; 1042 } else if (!increment) { 1043 increment = nearest ; 1044 } else { 1045 increment = gcd(increment, nearest) ; 1046 } 1047 } else { 1048 // large value - may still be multiple of 1.0 1049 if (fabs(objValue - floor(objValue + 0.5)) > 1.0e-8) { 1050 increment = 0; 1051 break; 1052 } else { 1053 bigIntegers++; 1054 } 1055 } 1056 } 999 if (possibleMultiple && maximumCost) { 1000 int increment = 0; 1001 double multiplier = 2520.0; 1002 while (10.0 * multiplier * maximumCost < 1.0e8) 1003 multiplier *= 10.0; 1004 int bigIntegers = 0; // Count of large costs which are integer 1005 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 1006 if (upper[iColumn] > lower[iColumn] + 1.0e-8) { 1007 double objValue = fabs(objective[iColumn]); 1008 if (!isInteger(iColumn)) { 1009 if (!coeffMultiplier) 1010 objValue *= continuousMultiplier; 1011 else 1012 objValue *= coeffMultiplier[iColumn]; 1013 } 1014 if (objValue) { 1015 double value = objValue * multiplier; 1016 if (value < 2.1e9) { 1017 int nearest = static_cast<int>(floor(value + 0.5)); 1018 if (fabs(value - floor(value + 0.5)) > 1.0e-8) { 1019 increment = 0; 1020 break; 1021 } else if (!increment) { 1022 increment = nearest; 1023 } else { 1024 increment = gcd(increment, nearest); 1057 1025 } 1058 } 1059 delete [] coeffMultiplier; 1060 /* 1026 } else { 1027 // large value - may still be multiple of 1.0 1028 if (fabs(objValue - floor(objValue + 0.5)) > 1.0e-8) { 1029 increment = 0; 1030 break; 1031 } else { 1032 bigIntegers++; 1033 } 1034 } 1035 } 1036 } 1037 } 1038 delete[] coeffMultiplier; 1039 /* 1061 1040 If the increment beats the current value for objective change, install it. 1062 1041 */ 1063 1064 double value = increment;1065 double cutoff = getDblParam(CbcModel::CbcCutoffIncrement);1066 1067 1068 increment = gcd(increment, static_cast<int>(multiplier));1069 1070 1071 value /= multiplier;1072 1073 1074 if (value*0.999 > cutoff) {1075 1076 1077 << value << CoinMessageEol;1078 setDblParam(CbcModel::CbcCutoffIncrement, CoinMax(value*0.999,value-1.0e-4));1079 1080 1081 1082 1083 return;1042 if (increment) { 1043 double value = increment; 1044 double cutoff = getDblParam(CbcModel::CbcCutoffIncrement); 1045 if (bigIntegers) { 1046 // allow for 1.0 1047 increment = gcd(increment, static_cast<int>(multiplier)); 1048 value = increment; 1049 } 1050 value /= multiplier; 1051 value *= scaleFactor; 1052 //trueIncrement=CoinMax(cutoff,value);; 1053 if (value * 0.999 > cutoff) { 1054 messageHandler()->message(CBC_INTEGERINCREMENT, 1055 messages()) 1056 << value << CoinMessageEol; 1057 setDblParam(CbcModel::CbcCutoffIncrement, CoinMax(value * 0.999, value - 1.0e-4)); 1058 } 1059 } 1060 } 1061 1062 return; 1084 1063 } 1085 1064 … … 1087 1066 saveModel called (carved out of) BranchandBound 1088 1067 */ 1089 void CbcModel::saveModel(OsiSolverInterface * saveSolver, double * checkCutoffForRestart, bool *feasible)1068 void CbcModel::saveModel(OsiSolverInterface *saveSolver, double *checkCutoffForRestart, bool *feasible) 1090 1069 { 1091 if (saveSolver && (specialOptions_&32768) != 0) { 1092 // See if worth trying reduction 1093 *checkCutoffForRestart = getCutoff(); 1094 bool tryNewSearch = solverCharacteristics_->reducedCostsAccurate() && 1095 (*checkCutoffForRestart < 1.0e20); 1096 int numberColumns = getNumCols(); 1097 if (tryNewSearch) { 1098 #if CBC_USEFUL_PRINTING>1 1099 printf("after %d nodes, cutoff %g - looking\n", 1100 numberNodes_, getCutoff()); 1101 #endif 1102 saveSolver->resolve(); 1103 double direction = saveSolver->getObjSense() ; 1104 double gap = *checkCutoffForRestart - saveSolver->getObjValue() * direction ; 1105 double tolerance; 1106 saveSolver->getDblParam(OsiDualTolerance, tolerance) ; 1107 if (gap <= 0.0) 1108 gap = tolerance; 1109 gap += 100.0 * tolerance; 1110 double integerTolerance = getDblParam(CbcIntegerTolerance) ; 1111 1112 const double *lower = saveSolver->getColLower() ; 1113 const double *upper = saveSolver->getColUpper() ; 1114 const double *solution = saveSolver->getColSolution() ; 1115 const double *reducedCost = saveSolver->getReducedCost() ; 1116 1117 int numberFixed = 0 ; 1118 int numberFixed2 = 0; 1119 for (int i = 0 ; i < numberIntegers_ ; i++) { 1120 int iColumn = integerVariable_[i] ; 1121 double djValue = direction * reducedCost[iColumn] ; 1122 if (upper[iColumn] - lower[iColumn] > integerTolerance) { 1123 if (solution[iColumn] < lower[iColumn] + integerTolerance && djValue > gap) { 1124 saveSolver->setColUpper(iColumn, lower[iColumn]) ; 1125 numberFixed++ ; 1126 } else if (solution[iColumn] > upper[iColumn] - integerTolerance && -djValue > gap) { 1127 saveSolver->setColLower(iColumn, upper[iColumn]) ; 1128 numberFixed++ ; 1129 } 1130 } else { 1131 numberFixed2++; 1132 } 1133 } 1070 if (saveSolver && (specialOptions_ & 32768) != 0) { 1071 // See if worth trying reduction 1072 *checkCutoffForRestart = getCutoff(); 1073 bool tryNewSearch = solverCharacteristics_->reducedCostsAccurate() && (*checkCutoffForRestart < 1.0e20); 1074 int numberColumns = getNumCols(); 1075 if (tryNewSearch) { 1076 #if CBC_USEFUL_PRINTING > 1 1077 printf("after %d nodes, cutoff %g - looking\n", 1078 numberNodes_, getCutoff()); 1079 #endif 1080 saveSolver->resolve(); 1081 double direction = saveSolver->getObjSense(); 1082 double gap = *checkCutoffForRestart - saveSolver->getObjValue() * direction; 1083 double tolerance; 1084 saveSolver->getDblParam(OsiDualTolerance, tolerance); 1085 if (gap <= 0.0) 1086 gap = tolerance; 1087 gap += 100.0 * tolerance; 1088 double integerTolerance = getDblParam(CbcIntegerTolerance); 1089 1090 const double *lower = saveSolver->getColLower(); 1091 const double *upper = saveSolver->getColUpper(); 1092 const double *solution = saveSolver->getColSolution(); 1093 const double *reducedCost = saveSolver->getReducedCost(); 1094 1095 int numberFixed = 0; 1096 int numberFixed2 = 0; 1097 for (int i = 0; i < numberIntegers_; i++) { 1098 int iColumn = integerVariable_[i]; 1099 double djValue = direction * reducedCost[iColumn]; 1100 if (upper[iColumn] - lower[iColumn] > integerTolerance) { 1101 if (solution[iColumn] < lower[iColumn] + integerTolerance && djValue > gap) { 1102 saveSolver->setColUpper(iColumn, lower[iColumn]); 1103 numberFixed++; 1104 } else if (solution[iColumn] > upper[iColumn] - integerTolerance && -djValue > gap) { 1105 saveSolver->setColLower(iColumn, upper[iColumn]); 1106 numberFixed++; 1107 } 1108 } else { 1109 numberFixed2++; 1110 } 1111 } 1134 1112 #ifdef COIN_DEVELOP 1135 1113 /* 1136 1114 We're debugging. (specialOptions 1) 1137 1115 */ 1138 if ((specialOptions_&1) != 0) { 1139 const OsiRowCutDebugger *debugger = saveSolver->getRowCutDebugger() ; 1140 if (debugger) { 1141 printf("Contains optimal\n") ; 1142 OsiSolverInterface * temp = saveSolver->clone(); 1143 const double * solution = debugger->optimalSolution(); 1144 const double *lower = temp->getColLower() ; 1145 const double *upper = temp->getColUpper() ; 1146 int n = temp->getNumCols(); 1147 for (int i = 0; i < n; i++) { 1148 if (temp->isInteger(i)) { 1149 double value = floor(solution[i] + 0.5); 1150 assert (value >= lower[i] && value <= upper[i]); 1151 temp->setColLower(i, value); 1152 temp->setColUpper(i, value); 1153 } 1154 } 1155 temp->writeMps("reduced_fix"); 1156 delete temp; 1157 saveSolver->writeMps("reduced"); 1158 } else { 1159 abort(); 1160 } 1116 if ((specialOptions_ & 1) != 0) { 1117 const OsiRowCutDebugger *debugger = saveSolver->getRowCutDebugger(); 1118 if (debugger) { 1119 printf("Contains optimal\n"); 1120 OsiSolverInterface *temp = saveSolver->clone(); 1121 const double *solution = debugger->optimalSolution(); 1122 const double *lower = temp->getColLower(); 1123 const double *upper = temp->getColUpper(); 1124 int n = temp->getNumCols(); 1125 for (int i = 0; i < n; i++) { 1126 if (temp->isInteger(i)) { 1127 double value = floor(solution[i] + 0.5); 1128 assert(value >= lower[i] && value <= upper[i]); 1129 temp->setColLower(i, value); 1130 temp->setColUpper(i, value); 1161 1131 } 1162 printf("Restart could fix %d integers (%d already fixed)\n", 1163 numberFixed + numberFixed2, numberFixed2); 1164 #endif 1165 numberFixed += numberFixed2; 1166 if (numberFixed*20 < numberColumns) 1167 tryNewSearch = false; 1168 } 1169 if (tryNewSearch) { 1170 // back to solver without cuts? 1171 OsiSolverInterface * solver2 = continuousSolver_->clone(); 1172 const double *lower = saveSolver->getColLower() ; 1173 const double *upper = saveSolver->getColUpper() ; 1174 for (int i = 0 ; i < numberIntegers_ ; i++) { 1175 int iColumn = integerVariable_[i] ; 1176 solver2->setColLower(iColumn, lower[iColumn]); 1177 solver2->setColUpper(iColumn, upper[iColumn]); 1178 } 1179 // swap 1180 delete saveSolver; 1181 saveSolver = solver2; 1182 double * newSolution = new double[numberColumns]; 1183 double objectiveValue = *checkCutoffForRestart; 1184 CbcSerendipity heuristic(*this); 1185 if (bestSolution_) 1186 heuristic.setInputSolution(bestSolution_, bestObjective_); 1187 heuristic.setFractionSmall(0.9); 1188 heuristic.setFeasibilityPumpOptions(1008013); 1189 // Use numberNodes to say how many are original rows 1190 heuristic.setNumberNodes(continuousSolver_->getNumRows()); 1132 } 1133 temp->writeMps("reduced_fix"); 1134 delete temp; 1135 saveSolver->writeMps("reduced"); 1136 } else { 1137 abort(); 1138 } 1139 } 1140 printf("Restart could fix %d integers (%d already fixed)\n", 1141 numberFixed + numberFixed2, numberFixed2); 1142 #endif 1143 numberFixed += numberFixed2; 1144 if (numberFixed * 20 < numberColumns) 1145 tryNewSearch = false; 1146 } 1147 if (tryNewSearch) { 1148 // back to solver without cuts? 1149 OsiSolverInterface *solver2 = continuousSolver_->clone(); 1150 const double *lower = saveSolver->getColLower(); 1151 const double *upper = saveSolver->getColUpper(); 1152 for (int i = 0; i < numberIntegers_; i++) { 1153 int iColumn = integerVariable_[i]; 1154 solver2->setColLower(iColumn, lower[iColumn]); 1155 solver2->setColUpper(iColumn, upper[iColumn]); 1156 } 1157 // swap 1158 delete saveSolver; 1159 saveSolver = solver2; 1160 double *newSolution = new double[numberColumns]; 1161 double objectiveValue = *checkCutoffForRestart; 1162 CbcSerendipity heuristic(*this); 1163 if (bestSolution_) 1164 heuristic.setInputSolution(bestSolution_, bestObjective_); 1165 heuristic.setFractionSmall(0.9); 1166 heuristic.setFeasibilityPumpOptions(1008013); 1167 // Use numberNodes to say how many are original rows 1168 heuristic.setNumberNodes(continuousSolver_->getNumRows()); 1191 1169 #ifdef COIN_DEVELOP 1192 if (continuousSolver_->getNumRows() < 1193 saveSolver->getNumRows()) 1194 printf("%d rows added ZZZZZ\n", 1195 solver_->getNumRows() - continuousSolver_->getNumRows()); 1196 #endif 1197 int returnCode = heuristic.smallBranchAndBound(saveSolver, 1198 -1, newSolution, 1199 objectiveValue, 1200 *checkCutoffForRestart, "Reduce"); 1201 if (returnCode < 0) { 1170 if (continuousSolver_->getNumRows() < saveSolver->getNumRows()) 1171 printf("%d rows added ZZZZZ\n", 1172 solver_->getNumRows() - continuousSolver_->getNumRows()); 1173 #endif 1174 int returnCode = heuristic.smallBranchAndBound(saveSolver, 1175 -1, newSolution, 1176 objectiveValue, 1177 *checkCutoffForRestart, "Reduce"); 1178 if (returnCode < 0) { 1202 1179 #ifdef COIN_DEVELOP 1203 1204 #endif 1205 delete[] newSolution;1206 1207 if ((returnCode&1) != 0) {1208 1209 1210 1211 1212 setBestSolution(CBC_ROUNDING, objectiveValue, newSolution);1213 1214 delete[] newSolution;1215 1216 1180 printf("Restart - not small enough to do search after fixing\n"); 1181 #endif 1182 delete[] newSolution; 1183 } else { 1184 if ((returnCode & 1) != 0) { 1185 // increment number of solutions so other heuristics can test 1186 numberSolutions_++; 1187 numberHeuristicSolutions_++; 1188 lastHeuristic_ = NULL; 1189 setBestSolution(CBC_ROUNDING, objectiveValue, newSolution); 1190 } 1191 delete[] newSolution; 1192 *feasible = false; // stop search 1193 } 1217 1194 #if 0 // probably not needed def CBC_THREAD 1218 1195 if (master_) { … … 1232 1209 } 1233 1210 #endif 1234 1235 1211 } 1212 } 1236 1213 } 1237 1214 /* … … 1240 1217 void CbcModel::AddIntegers() 1241 1218 { 1242 int numberColumns = continuousSolver_->getNumCols(); 1243 int numberRows = continuousSolver_->getNumRows(); 1244 int numberOriginalIntegers = numberIntegers_; 1245 int * del = new int [CoinMax(numberColumns, numberRows)]; 1246 int * original = new int [numberColumns]; 1247 char * possibleRow = new char [numberRows]; 1219 int numberColumns = continuousSolver_->getNumCols(); 1220 int numberRows = continuousSolver_->getNumRows(); 1221 int numberOriginalIntegers = numberIntegers_; 1222 int *del = new int[CoinMax(numberColumns, numberRows)]; 1223 int *original = new int[numberColumns]; 1224 char *possibleRow = new char[numberRows]; 1225 { 1226 const CoinPackedMatrix *rowCopy = continuousSolver_->getMatrixByRow(); 1227 const int *column = rowCopy->getIndices(); 1228 const int *rowLength = rowCopy->getVectorLengths(); 1229 const CoinBigIndex *rowStart = rowCopy->getVectorStarts(); 1230 const double *rowLower = continuousSolver_->getRowLower(); 1231 const double *rowUpper = continuousSolver_->getRowUpper(); 1232 const double *element = rowCopy->getElements(); 1233 for (int i = 0; i < numberRows; i++) { 1234 int nLeft = 0; 1235 bool possible = false; 1236 if (rowLower[i] < -1.0e20) { 1237 double value = rowUpper[i]; 1238 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1239 possible = true; 1240 } else if (rowUpper[i] > 1.0e20) { 1241 double value = rowLower[i]; 1242 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1243 possible = true; 1244 } else { 1245 double value = rowUpper[i]; 1246 if (rowLower[i] == rowUpper[i] && fabs(value - floor(value + 0.5)) < 1.0e-8) 1247 possible = true; 1248 } 1249 double allSame = (possible) ? 0.0 : -1.0; 1250 for (CoinBigIndex j = rowStart[i]; 1251 j < rowStart[i] + rowLength[i]; j++) { 1252 int iColumn = column[j]; 1253 if (continuousSolver_->isInteger(iColumn)) { 1254 if (fabs(element[j]) != 1.0) 1255 possible = false; 1256 } else { 1257 nLeft++; 1258 if (!allSame) { 1259 allSame = fabs(element[j]); 1260 } else if (allSame > 0.0) { 1261 if (allSame != fabs(element[j])) 1262 allSame = -1.0; 1263 } 1264 } 1265 } 1266 if (nLeft == rowLength[i] && allSame > 0.0) 1267 possibleRow[i] = 2; 1268 else if (possible || !nLeft) 1269 possibleRow[i] = 1; 1270 else 1271 possibleRow[i] = 0; 1272 } 1273 } 1274 int nDel = 0; 1275 for (int i = 0; i < numberColumns; i++) { 1276 original[i] = i; 1277 if (continuousSolver_->isInteger(i)) 1278 del[nDel++] = i; 1279 } 1280 { 1281 // we must not exclude current best solution (rounding errors) 1282 // also not if large values 1283 const int *row = continuousSolver_->getMatrixByCol()->getIndices(); 1284 const CoinBigIndex *columnStart = continuousSolver_->getMatrixByCol()->getVectorStarts(); 1285 const int *columnLength = continuousSolver_->getMatrixByCol()->getVectorLengths(); 1286 const double *solution = continuousSolver_->getColSolution(); 1287 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 1288 if (!continuousSolver_->isInteger(iColumn)) { 1289 double value = bestSolution_ ? bestSolution_[iColumn] : 0.0; 1290 double value2 = solution[iColumn]; 1291 if (fabs(value - floor(value + 0.5)) > 1.0e-8 || fabs(value2) > 1.0e3) { 1292 CoinBigIndex start = columnStart[iColumn]; 1293 CoinBigIndex end = start + columnLength[iColumn]; 1294 for (CoinBigIndex j = start; j < end; j++) { 1295 int iRow = row[j]; 1296 possibleRow[iRow] = 0; 1297 } 1298 } 1299 } 1300 } 1301 } 1302 int nExtra = 0; 1303 OsiSolverInterface *copy1 = continuousSolver_->clone(); 1304 int nPass = 0; 1305 while (nDel && nPass < 10) { 1306 nPass++; 1307 OsiSolverInterface *copy2 = copy1->clone(); 1308 int nLeft = 0; 1309 for (int i = 0; i < nDel; i++) 1310 original[del[i]] = -1; 1311 for (int i = 0; i < numberColumns; i++) { 1312 int kOrig = original[i]; 1313 if (kOrig >= 0) 1314 original[nLeft++] = kOrig; 1315 } 1316 assert(nLeft == numberColumns - nDel); 1317 copy2->deleteCols(nDel, del); 1318 numberColumns = copy2->getNumCols(); 1319 const CoinPackedMatrix *rowCopy = copy2->getMatrixByRow(); 1320 numberRows = rowCopy->getNumRows(); 1321 const int *column = rowCopy->getIndices(); 1322 const int *rowLength = rowCopy->getVectorLengths(); 1323 const CoinBigIndex *rowStart = rowCopy->getVectorStarts(); 1324 const double *rowLower = copy2->getRowLower(); 1325 const double *rowUpper = copy2->getRowUpper(); 1326 const double *element = rowCopy->getElements(); 1327 const CoinPackedMatrix *columnCopy = copy2->getMatrixByCol(); 1328 const int *columnLength = columnCopy->getVectorLengths(); 1329 nDel = 0; 1330 // Could do gcd stuff on ones with costs 1331 for (int i = 0; i < numberRows; i++) { 1332 if (!rowLength[i]) { 1333 del[nDel++] = i; 1334 } else if (possibleRow[i]) { 1335 if (rowLength[i] == 1) { 1336 CoinBigIndex k = rowStart[i]; 1337 int iColumn = column[k]; 1338 if (!copy2->isInteger(iColumn)) { 1339 double mult = 1.0 / fabs(element[k]); 1340 if (rowLower[i] < -1.0e20) { 1341 // treat rhs as multiple of 1 unless elements all same 1342 double value = ((possibleRow[i] == 2) ? rowUpper[i] : 1.0) * mult; 1343 if (fabs(value - floor(value + 0.5)) < 1.0e-8) { 1344 del[nDel++] = i; 1345 if (columnLength[iColumn] == 1) { 1346 copy2->setInteger(iColumn); 1347 int kOrig = original[iColumn]; 1348 setOptionalInteger(kOrig); 1349 } 1350 } 1351 } else if (rowUpper[i] > 1.0e20) { 1352 // treat rhs as multiple of 1 unless elements all same 1353 double value = ((possibleRow[i] == 2) ? rowLower[i] : 1.0) * mult; 1354 if (fabs(value - floor(value + 0.5)) < 1.0e-8) { 1355 del[nDel++] = i; 1356 if (columnLength[iColumn] == 1) { 1357 copy2->setInteger(iColumn); 1358 int kOrig = original[iColumn]; 1359 setOptionalInteger(kOrig); 1360 } 1361 } 1362 } else { 1363 // treat rhs as multiple of 1 unless elements all same 1364 double value = ((possibleRow[i] == 2) ? rowUpper[i] : 1.0) * mult; 1365 if (rowLower[i] == rowUpper[i] && fabs(value - floor(value + 0.5)) < 1.0e-8) { 1366 del[nDel++] = i; 1367 copy2->setInteger(iColumn); 1368 int kOrig = original[iColumn]; 1369 setOptionalInteger(kOrig); 1370 } 1371 } 1372 } 1373 } else { 1374 // only if all singletons 1375 bool possible = false; 1376 if (rowLower[i] < -1.0e20) { 1377 double value = rowUpper[i]; 1378 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1379 possible = true; 1380 } else if (rowUpper[i] > 1.0e20) { 1381 double value = rowLower[i]; 1382 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1383 possible = true; 1384 } else { 1385 double value = rowUpper[i]; 1386 if (rowLower[i] == rowUpper[i] && fabs(value - floor(value + 0.5)) < 1.0e-8) 1387 possible = true; 1388 } 1389 if (possible) { 1390 for (CoinBigIndex j = rowStart[i]; 1391 j < rowStart[i] + rowLength[i]; j++) { 1392 int iColumn = column[j]; 1393 if (columnLength[iColumn] != 1 || fabs(element[j]) != 1.0) { 1394 possible = false; 1395 break; 1396 } 1397 } 1398 if (possible) { 1399 for (CoinBigIndex j = rowStart[i]; 1400 j < rowStart[i] + rowLength[i]; j++) { 1401 int iColumn = column[j]; 1402 if (!copy2->isInteger(iColumn)) { 1403 copy2->setInteger(iColumn); 1404 int kOrig = original[iColumn]; 1405 setOptionalInteger(kOrig); 1406 } 1407 } 1408 del[nDel++] = i; 1409 } 1410 } 1411 } 1412 } 1413 } 1414 if (nDel) { 1415 copy2->deleteRows(nDel, del); 1416 // pack down possible 1417 int n = 0; 1418 for (int i = 0; i < nDel; i++) 1419 possibleRow[del[i]] = -1; 1420 for (int i = 0; i < numberRows; i++) { 1421 if (possibleRow[i] >= 0) 1422 possibleRow[n++] = possibleRow[i]; 1423 } 1424 } 1425 if (nDel != numberRows) { 1426 nDel = 0; 1427 for (int i = 0; i < numberColumns; i++) { 1428 if (copy2->isInteger(i)) { 1429 del[nDel++] = i; 1430 nExtra++; 1431 } 1432 } 1433 } else { 1434 nDel = 0; 1435 } 1436 delete copy1; 1437 copy1 = copy2->clone(); 1438 delete copy2; 1439 } 1440 // See if what's left is a network 1441 bool couldBeNetwork = false; 1442 if (copy1->getNumRows() && copy1->getNumCols()) { 1443 #ifdef COIN_HAS_CLP 1444 OsiClpSolverInterface *clpSolver 1445 = dynamic_cast<OsiClpSolverInterface *>(copy1); 1446 if (false && clpSolver) { 1447 numberRows = clpSolver->getNumRows(); 1448 char *rotate = new char[numberRows]; 1449 int n = clpSolver->getModelPtr()->findNetwork(rotate, 1.0); 1450 delete[] rotate; 1451 #if CBC_USEFUL_PRINTING > 1 1452 printf("INTA network %d rows out of %d\n", n, numberRows); 1453 #endif 1454 if (CoinAbs(n) == numberRows) { 1455 couldBeNetwork = true; 1456 for (int i = 0; i < numberRows; i++) { 1457 if (!possibleRow[i]) { 1458 couldBeNetwork = false; 1459 #if CBC_USEFUL_PRINTING > 1 1460 printf("but row %d is bad\n", i); 1461 #endif 1462 break; 1463 } 1464 } 1465 } 1466 } else 1467 #endif 1248 1468 { 1249 const CoinPackedMatrix * rowCopy = continuousSolver_->getMatrixByRow(); 1250 const int * column = rowCopy->getIndices(); 1251 const int * rowLength = rowCopy->getVectorLengths(); 1252 const CoinBigIndex * rowStart = rowCopy->getVectorStarts(); 1253 const double * rowLower = continuousSolver_->getRowLower(); 1254 const double * rowUpper = continuousSolver_->getRowUpper(); 1255 const double * element = rowCopy->getElements(); 1256 for (int i = 0; i < numberRows; i++) { 1257 int nLeft = 0; 1258 bool possible = false; 1259 if (rowLower[i] < -1.0e20) { 1260 double value = rowUpper[i]; 1261 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1262 possible = true; 1263 } else if (rowUpper[i] > 1.0e20) { 1264 double value = rowLower[i]; 1265 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1266 possible = true; 1267 } else { 1268 double value = rowUpper[i]; 1269 if (rowLower[i] == rowUpper[i] && 1270 fabs(value - floor(value + 0.5)) < 1.0e-8) 1271 possible = true; 1469 numberColumns = copy1->getNumCols(); 1470 numberRows = copy1->getNumRows(); 1471 const double *rowLower = copy1->getRowLower(); 1472 const double *rowUpper = copy1->getRowUpper(); 1473 couldBeNetwork = true; 1474 for (int i = 0; i < numberRows; i++) { 1475 if (rowLower[i] > -1.0e20 && fabs(rowLower[i] - floor(rowLower[i] + 0.5)) > 1.0e-12) { 1476 couldBeNetwork = false; 1477 break; 1478 } 1479 if (rowUpper[i] < 1.0e20 && fabs(rowUpper[i] - floor(rowUpper[i] + 0.5)) > 1.0e-12) { 1480 couldBeNetwork = false; 1481 break; 1482 } 1483 if (possibleRow[i] == 0) { 1484 couldBeNetwork = false; 1485 break; 1486 } 1487 } 1488 if (couldBeNetwork) { 1489 const CoinPackedMatrix *matrixByCol = copy1->getMatrixByCol(); 1490 const double *element = matrixByCol->getElements(); 1491 //const int * row = matrixByCol->getIndices(); 1492 const CoinBigIndex *columnStart = matrixByCol->getVectorStarts(); 1493 const int *columnLength = matrixByCol->getVectorLengths(); 1494 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 1495 CoinBigIndex start = columnStart[iColumn]; 1496 CoinBigIndex end = start + columnLength[iColumn]; 1497 if (end > start + 2) { 1498 couldBeNetwork = false; 1499 break; 1500 } 1501 int type = 0; 1502 for (CoinBigIndex j = start; j < end; j++) { 1503 double value = element[j]; 1504 if (fabs(value) != 1.0) { 1505 couldBeNetwork = false; 1506 break; 1507 } else if (value == 1.0) { 1508 if ((type & 1) == 0) 1509 type |= 1; 1510 else 1511 type = 7; 1512 } else if (value == -1.0) { 1513 if ((type & 2) == 0) 1514 type |= 2; 1515 else 1516 type = 7; 1272 1517 } 1273 double allSame = (possible) ? 0.0 : -1.0; 1274 for (CoinBigIndex j = rowStart[i]; 1275 j < rowStart[i] + rowLength[i]; j++) { 1276 int iColumn = column[j]; 1277 if (continuousSolver_->isInteger(iColumn)) { 1278 if (fabs(element[j]) != 1.0) 1279 possible = false; 1280 } else { 1281 nLeft++; 1282 if (!allSame) { 1283 allSame = fabs(element[j]); 1284 } else if (allSame>0.0) { 1285 if (allSame!=fabs(element[j])) 1286 allSame = -1.0; 1287 } 1288 } 1289 } 1290 if (nLeft == rowLength[i] && allSame > 0.0) 1291 possibleRow[i] = 2; 1292 else if (possible || !nLeft) 1293 possibleRow[i] = 1; 1294 else 1295 possibleRow[i] = 0; 1296 } 1297 } 1298 int nDel = 0; 1299 for (int i = 0; i < numberColumns; i++) { 1300 original[i] = i; 1301 if (continuousSolver_->isInteger(i)) 1302 del[nDel++] = i; 1303 } 1304 { 1305 // we must not exclude current best solution (rounding errors) 1306 // also not if large values 1307 const int * row = continuousSolver_->getMatrixByCol()->getIndices(); 1308 const CoinBigIndex * columnStart = continuousSolver_->getMatrixByCol()->getVectorStarts(); 1309 const int * columnLength = continuousSolver_->getMatrixByCol()->getVectorLengths(); 1310 const double * solution = continuousSolver_->getColSolution(); 1311 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 1312 if (!continuousSolver_->isInteger(iColumn)) { 1313 double value = bestSolution_ ? bestSolution_[iColumn] : 0.0; 1314 double value2 = solution[iColumn]; 1315 if (fabs(value-floor(value+0.5))>1.0e-8 || 1316 fabs(value2)>1.0e3) { 1317 CoinBigIndex start = columnStart[iColumn]; 1318 CoinBigIndex end = start + columnLength[iColumn]; 1319 for (CoinBigIndex j = start; j < end; j++) { 1320 int iRow = row[j]; 1321 possibleRow[iRow]=0; 1322 } 1323 } 1324 } 1325 } 1326 } 1327 int nExtra = 0; 1328 OsiSolverInterface * copy1 = continuousSolver_->clone(); 1329 int nPass = 0; 1330 while (nDel && nPass < 10) { 1331 nPass++; 1332 OsiSolverInterface * copy2 = copy1->clone(); 1333 int nLeft = 0; 1334 for (int i = 0; i < nDel; i++) 1335 original[del[i]] = -1; 1336 for (int i = 0; i < numberColumns; i++) { 1337 int kOrig = original[i]; 1338 if (kOrig >= 0) 1339 original[nLeft++] = kOrig; 1340 } 1341 assert (nLeft == numberColumns - nDel); 1342 copy2->deleteCols(nDel, del); 1343 numberColumns = copy2->getNumCols(); 1344 const CoinPackedMatrix * rowCopy = copy2->getMatrixByRow(); 1345 numberRows = rowCopy->getNumRows(); 1346 const int * column = rowCopy->getIndices(); 1347 const int * rowLength = rowCopy->getVectorLengths(); 1348 const CoinBigIndex * rowStart = rowCopy->getVectorStarts(); 1349 const double * rowLower = copy2->getRowLower(); 1350 const double * rowUpper = copy2->getRowUpper(); 1351 const double * element = rowCopy->getElements(); 1352 const CoinPackedMatrix * columnCopy = copy2->getMatrixByCol(); 1353 const int * columnLength = columnCopy->getVectorLengths(); 1354 nDel = 0; 1355 // Could do gcd stuff on ones with costs 1356 for (int i = 0; i < numberRows; i++) { 1357 if (!rowLength[i]) { 1358 del[nDel++] = i; 1359 } else if (possibleRow[i]) { 1360 if (rowLength[i] == 1) { 1361 CoinBigIndex k = rowStart[i]; 1362 int iColumn = column[k]; 1363 if (!copy2->isInteger(iColumn)) { 1364 double mult = 1.0 / fabs(element[k]); 1365 if (rowLower[i] < -1.0e20) { 1366 // treat rhs as multiple of 1 unless elements all same 1367 double value = ((possibleRow[i]==2) ? rowUpper[i] : 1.0) * mult; 1368 if (fabs(value - floor(value + 0.5)) < 1.0e-8) { 1369 del[nDel++] = i; 1370 if (columnLength[iColumn] == 1) { 1371 copy2->setInteger(iColumn); 1372 int kOrig = original[iColumn]; 1373 setOptionalInteger(kOrig); 1374 } 1375 } 1376 } else if (rowUpper[i] > 1.0e20) { 1377 // treat rhs as multiple of 1 unless elements all same 1378 double value = ((possibleRow[i]==2) ? rowLower[i] : 1.0) * mult; 1379 if (fabs(value - floor(value + 0.5)) < 1.0e-8) { 1380 del[nDel++] = i; 1381 if (columnLength[iColumn] == 1) { 1382 copy2->setInteger(iColumn); 1383 int kOrig = original[iColumn]; 1384 setOptionalInteger(kOrig); 1385 } 1386 } 1387 } else { 1388 // treat rhs as multiple of 1 unless elements all same 1389 double value = ((possibleRow[i]==2) ? rowUpper[i] : 1.0) * mult; 1390 if (rowLower[i] == rowUpper[i] && 1391 fabs(value - floor(value + 0.5)) < 1.0e-8) { 1392 del[nDel++] = i; 1393 copy2->setInteger(iColumn); 1394 int kOrig = original[iColumn]; 1395 setOptionalInteger(kOrig); 1396 } 1397 } 1398 } 1399 } else { 1400 // only if all singletons 1401 bool possible = false; 1402 if (rowLower[i] < -1.0e20) { 1403 double value = rowUpper[i]; 1404 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1405 possible = true; 1406 } else if (rowUpper[i] > 1.0e20) { 1407 double value = rowLower[i]; 1408 if (fabs(value - floor(value + 0.5)) < 1.0e-8) 1409 possible = true; 1410 } else { 1411 double value = rowUpper[i]; 1412 if (rowLower[i] == rowUpper[i] && 1413 fabs(value - floor(value + 0.5)) < 1.0e-8) 1414 possible = true; 1415 } 1416 if (possible) { 1417 for (CoinBigIndex j = rowStart[i]; 1418 j < rowStart[i] + rowLength[i]; j++) { 1419 int iColumn = column[j]; 1420 if (columnLength[iColumn] != 1 || fabs(element[j]) != 1.0) { 1421 possible = false; 1422 break; 1423 } 1424 } 1425 if (possible) { 1426 for (CoinBigIndex j = rowStart[i]; 1427 j < rowStart[i] + rowLength[i]; j++) { 1428 int iColumn = column[j]; 1429 if (!copy2->isInteger(iColumn)) { 1430 copy2->setInteger(iColumn); 1431 int kOrig = original[iColumn]; 1432 setOptionalInteger(kOrig); 1433 } 1434 } 1435 del[nDel++] = i; 1436 } 1437 } 1438 } 1439 } 1440 } 1441 if (nDel) { 1442 copy2->deleteRows(nDel, del); 1443 // pack down possible 1444 int n=0; 1445 for (int i=0;i<nDel;i++) 1446 possibleRow[del[i]]=-1; 1447 for (int i=0;i<numberRows;i++) { 1448 if (possibleRow[i]>=0) 1449 possibleRow[n++]=possibleRow[i]; 1450 } 1451 } 1452 if (nDel != numberRows) { 1453 nDel = 0; 1454 for (int i = 0; i < numberColumns; i++) { 1455 if (copy2->isInteger(i)) { 1456 del[nDel++] = i; 1457 nExtra++; 1458 } 1459 } 1460 } else { 1461 nDel = 0; 1462 } 1463 delete copy1; 1464 copy1 = copy2->clone(); 1465 delete copy2; 1466 } 1467 // See if what's left is a network 1468 bool couldBeNetwork = false; 1469 if (copy1->getNumRows() && copy1->getNumCols()) { 1470 #ifdef COIN_HAS_CLP 1471 OsiClpSolverInterface * clpSolver 1472 = dynamic_cast<OsiClpSolverInterface *> (copy1); 1473 if (false && clpSolver) { 1474 numberRows = clpSolver->getNumRows(); 1475 char * rotate = new char[numberRows]; 1476 int n = clpSolver->getModelPtr()->findNetwork(rotate, 1.0); 1477 delete [] rotate; 1478 #if CBC_USEFUL_PRINTING>1 1479 printf("INTA network %d rows out of %d\n", n, numberRows); 1480 #endif 1481 if (CoinAbs(n) == numberRows) { 1482 couldBeNetwork = true; 1483 for (int i = 0; i < numberRows; i++) { 1484 if (!possibleRow[i]) { 1485 couldBeNetwork = false; 1486 #if CBC_USEFUL_PRINTING>1 1487 printf("but row %d is bad\n", i); 1488 #endif 1489 break; 1490 } 1491 } 1492 } 1493 } else 1494 #endif 1495 { 1496 numberColumns = copy1->getNumCols(); 1497 numberRows = copy1->getNumRows(); 1498 const double * rowLower = copy1->getRowLower(); 1499 const double * rowUpper = copy1->getRowUpper(); 1500 couldBeNetwork = true; 1501 for (int i = 0; i < numberRows; i++) { 1502 if (rowLower[i] > -1.0e20 && fabs(rowLower[i] - floor(rowLower[i] + 0.5)) > 1.0e-12) { 1503 couldBeNetwork = false; 1504 break; 1505 } 1506 if (rowUpper[i] < 1.0e20 && fabs(rowUpper[i] - floor(rowUpper[i] + 0.5)) > 1.0e-12) { 1507 couldBeNetwork = false; 1508 break; 1509 } 1510 if (possibleRow[i]==0) { 1511 couldBeNetwork = false; 1512 break; 1513 } 1514 } 1515 if (couldBeNetwork) { 1516 const CoinPackedMatrix * matrixByCol = copy1->getMatrixByCol(); 1517 const double * element = matrixByCol->getElements(); 1518 //const int * row = matrixByCol->getIndices(); 1519 const CoinBigIndex * columnStart = matrixByCol->getVectorStarts(); 1520 const int * columnLength = matrixByCol->getVectorLengths(); 1521 for (int iColumn = 0; iColumn < numberColumns; iColumn++) { 1522 CoinBigIndex start = columnStart[iColumn]; 1523 CoinBigIndex end = start + columnLength[iColumn]; 1524 if (end > start + 2) { 1525 couldBeNetwork = false; 1526 break; 1527 } 1528 int type = 0; 1529 for (CoinBigIndex j = start; j < end; j++) { 1530 double value = element[j]; 1531 if (fabs(value) != 1.0) { 1532 couldBeNetwork = false; 1533 break; 1534 } else if (value == 1.0) { 1535 if ((type&1) == 0) 1536 type |= 1; 1537 else 1538 type = 7; 1539 } else if (value == -1.0) { 1540 if ((type&2) == 0) 1541 type |= 2; 1542 else 1543 type = 7; 1544 } 1545 } 1546 if (type > 3) { 1547 couldBeNetwork = false; 1548 break; 1549 } 1550 } 1551 } 1552 } 1553 } 1554 if (couldBeNetwork) { 1555 for (int i = 0; i < numberColumns; i++) 1556 setOptionalInteger(original[i]); 1557 } 1558 if (nExtra || couldBeNetwork) { 1559 numberColumns = copy1->getNumCols(); 1560 numberRows = copy1->getNumRows(); 1561 if (!numberColumns || !numberRows) { 1562 int numberColumns = solver_->getNumCols(); 1563 for (int i = 0; i < numberColumns; i++) 1564 assert(solver_->isInteger(i)); 1565 } 1566 #if CBC_USEFUL_PRINTING>1 1567 if (couldBeNetwork || nExtra) 1568 printf("INTA %d extra integers, %d left%s\n", nExtra, 1569 numberColumns, 1570 couldBeNetwork ? ", all network" : ""); 1571 #endif 1572 findIntegers(true, 2); 1573 convertToDynamic(); 1574 } 1575 #if CBC_USEFUL_PRINTING>1 1576 if (!couldBeNetwork && copy1->getNumCols() && 1577 copy1->getNumRows()) { 1578 printf("INTA %d rows and %d columns remain\n", 1579 copy1->getNumRows(), copy1->getNumCols()); 1580 if (copy1->getNumCols() < 200) { 1581 copy1->writeMps("moreint"); 1582 printf("INTA Written remainder to moreint.mps.gz %d rows %d cols\n", 1583 copy1->getNumRows(), copy1->getNumCols()); 1584 } 1585 } 1586 #endif 1587 delete copy1; 1588 delete [] del; 1589 delete [] original; 1590 delete [] possibleRow; 1591 // double check increment 1592 analyzeObjective(); 1593 // If any changes - tell code 1594 if(numberOriginalIntegers<numberIntegers_) 1595 synchronizeModel(); 1518 } 1519 if (type > 3) { 1520 couldBeNetwork = false; 1521 break; 1522 } 1523 } 1524 } 1525 } 1526 } 1527 if (couldBeNetwork) { 1528 for (int i = 0; i < numberColumns; i++) 1529 setOptionalInteger(original[i]); 1530 } 1531 if (nExtra || couldBeNetwork) { 1532 numberColumns = copy1->getNumCols(); 1533 numberRows = copy1->getNumRows(); 1534 if (!numberColumns || !numberRows) { 1535 int numberColumns = solver_->getNumCols(); 1536 for (int i = 0; i < numberColumns; i++) 1537 assert(solver_->isInteger(i)); 1538 } 1539 #if CBC_USEFUL_PRINTING > 1 1540 if (couldBeNetwork || nExtra) 1541 printf("INTA %d extra integers, %d left%s\n", nExtra, 1542 numberColumns, 1543 couldBeNetwork ? ", all network" : ""); 1544 #endif 1545 findIntegers(true, 2); 1546 convertToDynamic(); 1547 } 1548 #if CBC_USEFUL_PRINTING > 1 1549 if (!couldBeNetwork && copy1->getNumCols() && copy1->getNumRows()) { 1550 printf("INTA %d rows and %d columns remain\n", 1551 copy1->getNumRows(), copy1->getNumCols()); 1552 if (copy1->getNumCols() < 200) { 1553 copy1->writeMps("moreint"); 1554 printf("INTA Written remainder to moreint.mps.gz %d rows %d cols\n", 1555 copy1->getNumRows(), copy1->getNumCols()); 1556 } 1557 } 1558 #endif 1559 delete copy1; 1560 delete[] del; 1561 delete[] original; 1562 delete[] possibleRow; 1563 // double check increment 1564 analyzeObjective(); 1565 // If any changes - tell code 1566 if (numberOriginalIntegers < numberIntegers_) 1567 synchronizeModel(); 1596 1568 } 1597 1569 /** … … 1608 1580 1609 1581 #ifdef CONFLICT_CUTS 1610 #if PRINT_CONFLICT ==11611 static int numberConflictCuts =0;1612 static int lastNumberConflictCuts =0;1613 static double lengthConflictCuts =0.0;1582 #if PRINT_CONFLICT == 1 1583 static int numberConflictCuts = 0; 1584 static int lastNumberConflictCuts = 0; 1585 static double lengthConflictCuts = 0.0; 1614 1586 #endif 1615 1587 #endif … … 1634 1606 1635 1607 { 1636 1637 1608 if (!parentModel_) { 1609 /* 1638 1610 Capture a time stamp before we start (unless set). 1639 1611 */ 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 double lastBestPossibleObjective=-COIN_DBL_MAX;1652 // when to check for restart1653 int nextCheckRestart=50;1654 1655 bool flipObjective = (solver_->getObjSense()<0.0);1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 if (dynamic_cast<CbcTreeLocal *>(tree_))1676 1612 if (!dblParam_[CbcStartSeconds]) { 1613 if (!useElapsedTime()) 1614 dblParam_[CbcStartSeconds] = CoinCpuTime(); 1615 else 1616 dblParam_[CbcStartSeconds] = CoinGetTimeOfDay(); 1617 } 1618 } 1619 dblParam_[CbcSmallestChange] = COIN_DBL_MAX; 1620 dblParam_[CbcSumChange] = 0.0; 1621 dblParam_[CbcLargestChange] = 0.0; 1622 intParam_[CbcNumberBranches] = 0; 1623 double lastBestPossibleObjective = -COIN_DBL_MAX; 1624 // when to check for restart 1625 int nextCheckRestart = 50; 1626 // Force minimization !!!! 1627 bool flipObjective = (solver_->getObjSense() < 0.0); 1628 if (flipObjective) 1629 flipModel(); 1630 dblParam_[CbcOptimizationDirection] = 1.0; // was solver_->getObjSense(); 1631 strongInfo_[0] = 0; 1632 strongInfo_[1] = 0; 1633 strongInfo_[2] = 0; 1634 strongInfo_[3] = 0; 1635 strongInfo_[4] = 0; 1636 strongInfo_[5] = 0; 1637 strongInfo_[6] = 0; 1638 numberStrongIterations_ = 0; 1639 currentNode_ = NULL; 1640 // See if should do cuts old way 1641 if (parallelMode() < 0) { 1642 specialOptions_ |= 4096 + 8192; 1643 } else if (parallelMode() > 0) { 1644 specialOptions_ |= 4096; 1645 } 1646 int saveMoreSpecialOptions = moreSpecialOptions_; 1647 if (dynamic_cast<CbcTreeLocal *>(tree_)) 1648 specialOptions_ |= 4096 + 8192; 1677 1649 #ifdef COIN_HAS_CLP 1678 1679 OsiClpSolverInterface *clpSolver1680 = dynamic_cast<OsiClpSolverInterface *>(solver_);1681 1682 1683 1684 1685 1686 if ((specialOptions_&4194304)==0)1687 1650 { 1651 OsiClpSolverInterface *clpSolver 1652 = dynamic_cast<OsiClpSolverInterface *>(solver_); 1653 if (clpSolver) { 1654 // pass in disaster handler 1655 CbcDisasterHandler handler(this); 1656 clpSolver->passInDisasterHandler(&handler); 1657 // Initialise solvers seed (unless users says not) 1658 if ((specialOptions_ & 4194304) == 0) 1659 clpSolver->getModelPtr()->setRandomSeed(1234567); 1688 1660 #ifdef JJF_ZERO 1689 1690 1691 1692 #endif 1693 1694 1695 #endif 1696 1697 OsiSolverInterface *originalSolver = NULL;1698 1699 OsiObject **originalObject = NULL;1700 1701 1702 1703 1661 // reduce factorization frequency 1662 int frequency = clpSolver->getModelPtr()->factorizationFrequency(); 1663 clpSolver->getModelPtr()->setFactorizationFrequency(CoinMin(frequency, 120)); 1664 #endif 1665 } 1666 } 1667 #endif 1668 // original solver (only set if pre-processing) 1669 OsiSolverInterface *originalSolver = NULL; 1670 int numberOriginalObjects = numberObjects_; 1671 OsiObject **originalObject = NULL; 1672 // Save whether there were any objects 1673 bool noObjects = (numberObjects_ == 0); 1674 // Set up strategies 1675 /* 1704 1676 See if the user has supplied a strategy object and deal with it if present. 1705 1677 The call to setupOther will set numberStrong_ and numberBeforeTrust_, and … … 1710 1682 existing one. 1711 1683 */ 1712 1713 1714 1715 1716 1717 1718 1719 1720 status_ = 0;1721 1722 handler_->message(CBC_INFEAS, messages_) << CoinMessageEol;1723 1724 1725 handler_->message(CBC_UNBOUNDED, 1726 messages_) << CoinMessageEol ; 1727 secondaryStatus_ = 7;1728 } 1729 originalContinuousObjective_ = COIN_DBL_MAX;1730 if (flipObjective) 1731 flipModel(); 1732 return;1733 } else if (numberObjects_ && object_) {1734 numberOriginalObjects = numberObjects_;1735 // redo sequence1736 numberIntegers_ = 0;1737 int numberColumns = getNumCols();1738 int nOrig = originalSolver->getNumCols();1739 CglPreProcess * process = strategy_->process();1740 assert (process);1741 const int * originalColumns = process->originalColumns();1742 // allow for cliques etc1743 nOrig = CoinMax(nOrig, originalColumns[numberColumns-1] + 1);1744 // try and redo debugger1745 OsiRowCutDebugger * debugger = const_cast<OsiRowCutDebugger *> (solver_->getRowCutDebuggerAlways());1746 if (debugger) {1747 if (numberColumns<=debugger->numberColumns()) 1748 debugger->redoSolution(numberColumns, originalColumns);1749 else 1750 debugger=NULL; // no idea how to handle (SOS?) 1751 } 1752 // User-provided solution might have been best. Synchronise.1753 if (bestSolution_) {1754 // need to redo - in case no better found in BAB1755 // just get integer part right1756 for (int i = 0; i < numberColumns; i++) {1757 int jColumn = originalColumns[i];1758 bestSolution_[i] = bestSolution_[jColumn];1759 }1760 1761 originalObject = object_;1762 // object number or -11763 int * temp = new int[nOrig];1764 int iColumn;1765 for (iColumn = 0; iColumn < nOrig; iColumn++)1766 temp[iColumn] = -1;1767 int iObject;1768 int nNonInt = 0;1769 for (iObject = 0; iObject < numberOriginalObjects; iObject++) {1770 iColumn = originalObject[iObject]->columnNumber();1771 if (iColumn < 0) {1772 nNonInt++;1773 } else {1774 temp[iColumn] = iObject;1775 }1776 1777 int numberNewIntegers = 0;1778 int numberOldIntegers = 0;1779 int numberOldOther= 0;1780 for (iColumn = 0; iColumn < numberColumns; iColumn++) {1781 int jColumn = originalColumns[iColumn];1782 if (temp[jColumn] >= 0) {1783 int iObject = temp[jColumn];1784 CbcSimpleInteger * obj =1785 dynamic_cast <CbcSimpleInteger *>(originalObject[iObject]);1786 1787 1788 1789 1790 1791 1792 1793 1794 1684 if (strategy_) { 1685 // May do preprocessing 1686 originalSolver = solver_; 1687 strategy_->setupOther(*this); 1688 if (strategy_->preProcessState()) { 1689 // pre-processing done 1690 if (strategy_->preProcessState() < 0) { 1691 // infeasible (or unbounded) 1692 status_ = 0; 1693 if (!solver_->isProvenDualInfeasible()) { 1694 handler_->message(CBC_INFEAS, messages_) << CoinMessageEol; 1695 secondaryStatus_ = 1; 1696 } else { 1697 handler_->message(CBC_UNBOUNDED, 1698 messages_) 1699 << CoinMessageEol; 1700 secondaryStatus_ = 7; 1701 } 1702 originalContinuousObjective_ = COIN_DBL_MAX; 1703 if (flipObjective) 1704 flipModel(); 1705 return; 1706 } else if (numberObjects_ && object_) { 1707 numberOriginalObjects = numberObjects_; 1708 // redo sequence 1709 numberIntegers_ = 0; 1710 int numberColumns = getNumCols(); 1711 int nOrig = originalSolver->getNumCols(); 1712 CglPreProcess *process = strategy_->process(); 1713 assert(process); 1714 const int *originalColumns = process->originalColumns(); 1715 // allow for cliques etc 1716 nOrig = CoinMax(nOrig, originalColumns[numberColumns - 1] + 1); 1717 // try and redo debugger 1718 OsiRowCutDebugger *debugger = const_cast<OsiRowCutDebugger *>(solver_->getRowCutDebuggerAlways()); 1719 if (debugger) { 1720 if (numberColumns <= debugger->numberColumns()) 1721 debugger->redoSolution(numberColumns, originalColumns); 1722 else 1723 debugger = NULL; // no idea how to handle (SOS?) 1724 } 1725 // User-provided solution might have been best. Synchronise. 1726 if (bestSolution_) { 1727 // need to redo - in case no better found in BAB 1728 // just get integer part right 1729 for (int i = 0; i < numberColumns; i++) { 1730 int jColumn = originalColumns[i]; 1731 bestSolution_[i] = bestSolution_[jColumn]; 1732 } 1733 } 1734 originalObject = object_; 1735 // object number or -1 1736 int *temp = new int[nOrig]; 1737 int iColumn; 1738 for (iColumn = 0; iColumn < nOrig; iColumn++) 1739 temp[iColumn] = -1; 1740 int iObject; 1741 int nNonInt = 0; 1742 for (iObject = 0; iObject < numberOriginalObjects; iObject++) { 1743 iColumn = originalObject[iObject]->columnNumber(); 1744 if (iColumn < 0) { 1745 nNonInt++; 1746 } else { 1747 temp[iColumn] = iObject; 1748 } 1749 } 1750 int numberNewIntegers = 0; 1751 int numberOldIntegers = 0; 1752 int numberOldOther = 0; 1753 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 1754 int jColumn = originalColumns[iColumn]; 1755 if (temp[jColumn] >= 0) { 1756 int iObject = temp[jColumn]; 1757 CbcSimpleInteger *obj = dynamic_cast<CbcSimpleInteger *>(originalObject[iObject]); 1758 if (obj) 1759 numberOldIntegers++; 1760 else 1761 numberOldOther++; 1762 } else if (isInteger(iColumn)) { 1763 numberNewIntegers++; 1764 } 1765 } 1766 /* 1795 1767 Allocate an array to hold the indices of the integer variables. 1796 1768 Make a large enough array for all objects 1797 1769 */ 1798 1799 object_ = new OsiObject *[numberObjects_];1800 delete[] integerVariable_;1801 integerVariable_ = new int [numberNewIntegers+numberOldIntegers];1802 1770 numberObjects_ = numberNewIntegers + numberOldIntegers + numberOldOther + nNonInt; 1771 object_ = new OsiObject *[numberObjects_]; 1772 delete[] integerVariable_; 1773 integerVariable_ = new int[numberNewIntegers + numberOldIntegers]; 1774 /* 1803 1775 Walk the variables again, filling in the indices and creating objects for 1804 1776 the integer variables. Initially, the objects hold the index and upper & 1805 1777 lower bounds. 1806 1778 */ 1807 numberIntegers_ = 0; 1808 int n = originalColumns[numberColumns-1] + 1; 1809 int * backward = new int[n]; 1810 int i; 1811 for ( i = 0; i < n; i++) 1812 backward[i] = -1; 1813 for (i = 0; i < numberColumns; i++) 1814 backward[originalColumns[i]] = i; 1815 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 1816 int jColumn = originalColumns[iColumn]; 1817 if (temp[jColumn] >= 0) { 1818 int iObject = temp[jColumn]; 1819 CbcSimpleInteger * obj = 1820 dynamic_cast <CbcSimpleInteger *>(originalObject[iObject]) ; 1821 if (obj) { 1822 object_[numberIntegers_] = originalObject[iObject]->clone(); 1823 // redo ids etc 1824 //object_[numberIntegers_]->resetSequenceEtc(numberColumns,originalColumns); 1825 object_[numberIntegers_]->resetSequenceEtc(numberColumns, backward); 1826 integerVariable_[numberIntegers_++] = iColumn; 1827 } 1828 } else if (isInteger(iColumn)) { 1829 object_[numberIntegers_] = 1830 new CbcSimpleInteger(this, iColumn); 1831 integerVariable_[numberIntegers_++] = iColumn; 1832 } 1833 } 1834 delete [] backward; 1835 numberObjects_ = numberIntegers_; 1836 // Now append other column stuff 1837 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 1838 int jColumn = originalColumns[iColumn]; 1839 if (temp[jColumn] >= 0) { 1840 int iObject = temp[jColumn]; 1841 CbcSimpleInteger * obj = 1842 dynamic_cast <CbcSimpleInteger *>(originalObject[iObject]) ; 1843 if (!obj) { 1844 object_[numberObjects_] = originalObject[iObject]->clone(); 1845 // redo ids etc 1846 CbcObject * obj = 1847 dynamic_cast <CbcObject *>(object_[numberObjects_]) ; 1848 assert (obj); 1849 obj->redoSequenceEtc(this, numberColumns, originalColumns); 1850 numberObjects_++; 1851 } 1852 } 1853 } 1854 // now append non column stuff 1855 for (iObject = 0; iObject < numberOriginalObjects; iObject++) { 1856 iColumn = originalObject[iObject]->columnNumber(); 1857 if (iColumn < 0) { 1858 // already has column numbers changed 1859 object_[numberObjects_] = originalObject[iObject]->clone(); 1779 numberIntegers_ = 0; 1780 int n = originalColumns[numberColumns - 1] + 1; 1781 int *backward = new int[n]; 1782 int i; 1783 for (i = 0; i < n; i++) 1784 backward[i] = -1; 1785 for (i = 0; i < numberColumns; i++) 1786 backward[originalColumns[i]] = i; 1787 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 1788 int jColumn = originalColumns[iColumn]; 1789 if (temp[jColumn] >= 0) { 1790 int iObject = temp[jColumn]; 1791 CbcSimpleInteger *obj = dynamic_cast<CbcSimpleInteger *>(originalObject[iObject]); 1792 if (obj) { 1793 object_[numberIntegers_] = originalObject[iObject]->clone(); 1794 // redo ids etc 1795 //object_[numberIntegers_]->resetSequenceEtc(numberColumns,originalColumns); 1796 object_[numberIntegers_]->resetSequenceEtc(numberColumns, backward); 1797 integerVariable_[numberIntegers_++] = iColumn; 1798 } 1799 } else if (isInteger(iColumn)) { 1800 object_[numberIntegers_] = new CbcSimpleInteger(this, iColumn); 1801 integerVariable_[numberIntegers_++] = iColumn; 1802 } 1803 } 1804 delete[] backward; 1805 numberObjects_ = numberIntegers_; 1806 // Now append other column stuff 1807 for (iColumn = 0; iColumn < numberColumns; iColumn++) { 1808 int jColumn = originalColumns[iColumn]; 1809 if (temp[jColumn] >= 0) { 1810 int iObject = temp[jColumn]; 1811 CbcSimpleInteger *obj = dynamic_cast<CbcSimpleInteger *>(originalObject[iObject]); 1812 if (!obj) { 1813 object_[numberObjects_] = originalObject[iObject]->clone(); 1814 // redo ids etc 1815 CbcObject *obj = dynamic_cast<CbcObject *>(object_[numberObjects_]); 1816 assert(obj); 1817 obj->redoSequenceEtc(this, numberColumns, originalColumns); 1818 numberObjects_++; 1819 } 1820 } 1821 } 1822 // now append non column stuff 1823 for (iObject = 0; iObject < numberOriginalObjects; iObject++) { 1824 iColumn = originalObject[iObject]->columnNumber(); 1825 if (iColumn < 0) { 1826 // already has column numbers changed 1827 object_[numberObjects_] = originalObject[iObject]->clone(); 1860 1828 #ifdef JJF_ZERO 1861 // redo ids etc 1862 CbcObject * obj = 1863 dynamic_cast <CbcObject *>(object_[numberObjects_]) ; 1864 assert (obj); 1865 obj->redoSequenceEtc(this, numberColumns, originalColumns); 1866 #endif 1867 numberObjects_++; 1868 } 1869 } 1870 delete [] temp; 1871 if (!numberObjects_) 1872 handler_->message(CBC_NOINT, messages_) << CoinMessageEol ; 1873 } else { 1874 int numberColumns = getNumCols(); 1875 CglPreProcess * process = strategy_->process(); 1876 assert (process); 1877 const int * originalColumns = process->originalColumns(); 1878 // try and redo debugger 1879 OsiRowCutDebugger * debugger = const_cast<OsiRowCutDebugger *> (solver_->getRowCutDebuggerAlways()); 1880 if (debugger) 1881 debugger->redoSolution(numberColumns, originalColumns); 1882 } 1883 } else { 1884 //no preprocessing 1885 originalSolver = NULL; 1886 } 1887 strategy_->setupCutGenerators(*this); 1888 strategy_->setupHeuristics(*this); 1889 // Set strategy print level to models 1890 strategy_->setupPrinting(*this, handler_->logLevel()); 1891 } 1892 eventHappened_ = false; 1893 CbcEventHandler *eventHandler = getEventHandler() ; 1894 if (eventHandler) 1895 eventHandler->setModel(this); 1829 // redo ids etc 1830 CbcObject *obj = dynamic_cast<CbcObject *>(object_[numberObjects_]); 1831 assert(obj); 1832 obj->redoSequenceEtc(this, numberColumns, originalColumns); 1833 #endif 1834 numberObjects_++; 1835 } 1836 } 1837 delete[] temp; 1838 if (!numberObjects_) 1839 handler_->message(CBC_NOINT, messages_) << CoinMessageEol; 1840 } else { 1841 int numberColumns = getNumCols(); 1842 CglPreProcess *process = strategy_->process(); 1843 assert(process); 1844 const int *originalColumns = process->originalColumns(); 1845 // try and redo debugger 1846 OsiRowCutDebugger *debugger = const_cast<OsiRowCutDebugger *>(solver_->getRowCutDebuggerAlways()); 1847 if (debugger) 1848 debugger->redoSolution(numberColumns, originalColumns); 1849 } 1850 } else { 1851 //no preprocessing 1852 originalSolver = NULL; 1853 } 1854 strategy_->setupCutGenerators(*this); 1855 strategy_->setupHeuristics(*this); 1856 // Set strategy print level to models 1857 strategy_->setupPrinting(*this, handler_->logLevel()); 1858 } 1859 eventHappened_ = false; 1860 CbcEventHandler *eventHandler = getEventHandler(); 1861 if (eventHandler) 1862 eventHandler->setModel(this); 1896 1863 #define CLIQUE_ANALYSIS 1897 1864 #ifdef CLIQUE_ANALYSIS 1898 1899 1900 1901 1902 1903 1865 // set up for probing 1866 // If we're doing clever stuff with cliques, additional info here. 1867 if (!parentModel_) 1868 probingInfo_ = new CglTreeProbingInfo(solver_); 1869 else 1870 probingInfo_ = NULL; 1904 1871 #else 1905 probingInfo_ = NULL; 1906 #endif 1907 1908 // Try for dominated columns 1909 if ((specialOptions_&64) != 0) { 1910 CglDuplicateRow dupcuts(solver_); 1911 dupcuts.setMode(2); 1912 CglStored * storedCuts = dupcuts.outDuplicates(solver_); 1913 if (storedCuts) { 1914 COIN_DETAIL_PRINT(printf("adding dup cuts\n")); 1915 addCutGenerator(storedCuts, 1, "StoredCuts from dominated", 1916 true, false, false, -200); 1917 } 1918 } 1919 if (!nodeCompare_) 1920 nodeCompare_ = new CbcCompareDefault();; 1921 // See if hot start wanted 1922 CbcCompareBase * saveCompare = NULL; 1923 // User supplied hotstart. Adapt for preprocessing. 1924 if (hotstartSolution_) { 1925 if (strategy_ && strategy_->preProcessState() > 0) { 1926 CglPreProcess * process = strategy_->process(); 1927 assert (process); 1928 int n = solver_->getNumCols(); 1929 const int * originalColumns = process->originalColumns(); 1930 // columns should be in order ... but 1931 double * tempS = new double[n]; 1932 for (int i = 0; i < n; i++) { 1933 int iColumn = originalColumns[i]; 1934 tempS[i] = hotstartSolution_[iColumn]; 1935 } 1936 delete [] hotstartSolution_; 1937 hotstartSolution_ = tempS; 1938 if (hotstartPriorities_) { 1939 int * tempP = new int [n]; 1940 for (int i = 0; i < n; i++) { 1941 int iColumn = originalColumns[i]; 1942 tempP[i] = hotstartPriorities_[iColumn]; 1943 } 1944 delete [] hotstartPriorities_; 1945 hotstartPriorities_ = tempP; 1946 } 1947 } 1948 saveCompare = nodeCompare_; 1949 // depth first 1950 nodeCompare_ = new CbcCompareDepth(); 1951 } 1952 if (!problemFeasibility_) 1953 problemFeasibility_ = new CbcFeasibilityBase(); 1954 # ifdef CBC_DEBUG 1955 std::string problemName ; 1956 solver_->getStrParam(OsiProbName, problemName) ; 1957 printf("Problem name - %s\n", problemName.c_str()) ; 1958 solver_->setHintParam(OsiDoReducePrint, false, OsiHintDo, 0) ; 1959 # endif 1960 /* 1872 probingInfo_ = NULL; 1873 #endif 1874 1875 // Try for dominated columns 1876 if ((specialOptions_ & 64) != 0) { 1877 CglDuplicateRow dupcuts(solver_); 1878 dupcuts.setMode(2); 1879 CglStored *storedCuts = dupcuts.outDuplicates(solver_); 1880 if (storedCuts) { 1881 COIN_DETAIL_PRINT(printf("adding dup cuts\n")); 1882 addCutGenerator(storedCuts, 1, "StoredCuts from dominated", 1883 true, false, false, -200); 1884 } 1885 } 1886 if (!nodeCompare_) 1887 nodeCompare_ = new CbcCompareDefault(); 1888 ; 1889 // See if hot start wanted 1890 CbcCompareBase *saveCompare = NULL; 1891 // User supplied hotstart. Adapt for preprocessing. 1892 if (hotstartSolution_) { 1893 if (strategy_ && strategy_->preProcessState() > 0) { 1894 CglPreProcess *process = strategy_->process(); 1895 assert(process); 1896 int n = solver_->getNumCols(); 1897 const int *originalColumns = process->originalColumns(); 1898 // columns should be in order ... but 1899 double *tempS = new double[n]; 1900 for (int i = 0; i < n; i++) { 1901 int iColumn = originalColumns[i]; 1902 tempS[i] = hotstartSolution_[iColumn]; 1903 } 1904 delete[] hotstartSolution_; 1905 hotstartSolution_ = tempS; 1906 if (hotstartPriorities_) { 1907 int *tempP = new int[n]; 1908 for (int i = 0; i < n; i++) { 1909 int iColumn = originalColumns[i]; 1910 tempP[i] = hotstartPriorities_[iColumn]; 1911 } 1912 delete[] hotstartPriorities_; 1913 hotstartPriorities_ = tempP; 1914 } 1915 } 1916 saveCompare = nodeCompare_; 1917 // depth first 1918 nodeCompare_ = new CbcCompareDepth(); 1919 } 1920 if (!problemFeasibility_) 1921 problemFeasibility_ = new CbcFeasibilityBase(); 1922 #ifdef CBC_DEBUG 1923 std::string problemName; 1924 solver_->getStrParam(OsiProbName, problemName); 1925 printf("Problem name - %s\n", problemName.c_str()); 1926 solver_->setHintParam(OsiDoReducePrint, false, OsiHintDo, 0); 1927 #endif 1928 /* 1961 1929 Assume we're done, and see if we're proven wrong. 1962 1930 */ 1963 status_ = 0;1964 1965 1966 1931 status_ = 0; 1932 secondaryStatus_ = 0; 1933 phase_ = 0; 1934 /* 1967 1935 Scan the variables, noting the integer variables. Create an 1968 1936 CbcSimpleInteger object for each integer variable. 1969 1937 */ 1970 findIntegers(false) ; 1971 // Say not dynamic pseudo costs 1972 ownership_ &= ~0x40000000; 1973 // If dynamic pseudo costs then do 1974 if (numberBeforeTrust_) 1975 convertToDynamic(); 1976 // Set up char array to say if integer (speed) 1977 delete [] integerInfo_; 1978 { 1979 int n = solver_->getNumCols(); 1980 integerInfo_ = new char [n]; 1981 for (int i = 0; i < n; i++) { 1982 if (solver_->isInteger(i)) 1983 integerInfo_[i] = 1; 1984 else 1985 integerInfo_[i] = 0; 1986 } 1987 } 1988 if (preferredWay_) { 1989 // set all unset ones 1990 for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) { 1991 CbcObject * obj = 1992 dynamic_cast <CbcObject *>(object_[iObject]) ; 1993 if (obj && !obj->preferredWay()) 1994 obj->setPreferredWay(preferredWay_); 1995 } 1996 } 1997 /* 1938 findIntegers(false); 1939 // Say not dynamic pseudo costs 1940 ownership_ &= ~0x40000000; 1941 // If dynamic pseudo costs then do 1942 if (numberBeforeTrust_) 1943 convertToDynamic(); 1944 // Set up char array to say if integer (speed) 1945 delete[] integerInfo_; 1946 { 1947 int n = solver_->getNumCols(); 1948 integerInfo_ = new char[n]; 1949 for (int i = 0; i < n; i++) { 1950 if (solver_->isInteger(i)) 1951 integerInfo_[i] = 1; 1952 else 1953 integerInfo_[i] = 0; 1954 } 1955 } 1956 if (preferredWay_) { 1957 // set all unset ones 1958 for (int iObject = 0; iObject < numberObjects_; iObject++) { 1959 CbcObject *obj = dynamic_cast<CbcObject *>(object_[iObject]); 1960 if (obj && !obj->preferredWay()) 1961 obj->setPreferredWay(preferredWay_); 1962 } 1963 } 1964 /* 1998 1965 Ensure that objects on the lists of OsiObjects, heuristics, and cut 1999 1966 generators attached to this model all refer to this model. 2000 1967 */ 2001 synchronizeModel();2002 2003 OsiBabSolver * solverCharacteristics = dynamic_cast<OsiBabSolver *>(solver_->getAuxiliaryInfo());2004 2005 2006 2007 2008 2009 2010 solverCharacteristics_ = dynamic_cast<OsiBabSolver *>(solver_->getAuxiliaryInfo());2011 2012 2013 2014 2015 2016 continuousObjective_ = -COIN_DBL_MAX;2017 1968 synchronizeModel(); 1969 if (!solverCharacteristics_) { 1970 OsiBabSolver *solverCharacteristics = dynamic_cast<OsiBabSolver *>(solver_->getAuxiliaryInfo()); 1971 if (solverCharacteristics) { 1972 solverCharacteristics_ = solverCharacteristics; 1973 } else { 1974 // replace in solver 1975 OsiBabSolver defaultC; 1976 solver_->setAuxiliaryInfo(&defaultC); 1977 solverCharacteristics_ = dynamic_cast<OsiBabSolver *>(solver_->getAuxiliaryInfo()); 1978 } 1979 } 1980 1981 solverCharacteristics_->setSolver(solver_); 1982 // Set so we can tell we are in initial phase in resolve 1983 continuousObjective_ = -COIN_DBL_MAX; 1984 /* 2018 1985 Solve the relaxation. 2019 1986 … … 2022 1989 continuous relaxation. 2023 1990 */ 2024 1991 /* Tell solver we are in Branch and Cut 2025 1992 Could use last parameter for subtle differences */ 2026 solver_->setHintParam(OsiDoInBranchAndCut, true, OsiHintDo, NULL);1993 solver_->setHintParam(OsiDoInBranchAndCut, true, OsiHintDo, NULL); 2027 1994 #ifdef COIN_HAS_CLP 2028 2029 OsiClpSolverInterface *clpSolver2030 = dynamic_cast<OsiClpSolverInterface *>(solver_);2031 2032 ClpSimplex *clpSimplex = clpSolver->getModelPtr();2033 if ((specialOptions_&32) == 0) {2034 2035 if (numberAnalyzeIterations_>=0||(-numberAnalyzeIterations_&64)==0)2036 2037 2038 2039 if ((clpSolver->specialOptions()&(1 + 8)) != (1 + 8)) {2040 2041 if (numberColumns > 1000 && numberIntegers_*4 < numberColumns)2042 clpSolver->setSpecialOptions(clpSolver->specialOptions()&(~1));2043 2044 1995 { 1996 OsiClpSolverInterface *clpSolver 1997 = dynamic_cast<OsiClpSolverInterface *>(solver_); 1998 if (clpSolver) { 1999 ClpSimplex *clpSimplex = clpSolver->getModelPtr(); 2000 if ((specialOptions_ & 32) == 0) { 2001 // take off names (unless going to be saving) 2002 if (numberAnalyzeIterations_ >= 0 || (-numberAnalyzeIterations_ & 64) == 0) 2003 clpSimplex->dropNames(); 2004 } 2005 // no crunch if mostly continuous 2006 if ((clpSolver->specialOptions() & (1 + 8)) != (1 + 8)) { 2007 int numberColumns = solver_->getNumCols(); 2008 if (numberColumns > 1000 && numberIntegers_ * 4 < numberColumns) 2009 clpSolver->setSpecialOptions(clpSolver->specialOptions() & (~1)); 2010 } 2011 //#define NO_CRUNCH 2045 2012 #ifdef NO_CRUNCH 2046 printf("TEMP switching off crunch\n"); 2047 int iOpt = clpSolver->specialOptions(); 2048 iOpt &= ~1; 2049 iOpt |= 65536; 2050 clpSolver->setSpecialOptions(iOpt); 2051 #endif 2052 } 2053 } 2054 #endif 2055 bool feasible; 2056 numberSolves_ = 0 ; 2057 { 2058 // check 2059 int numberOdd = 0; 2060 for (int i = 0; i < numberObjects_; i++) { 2061 CbcSimpleInteger * obj = 2062 dynamic_cast <CbcSimpleInteger *>(object_[i]) ; 2063 if (!obj) 2064 numberOdd++; 2065 } 2066 if (numberOdd) 2067 moreSpecialOptions_ |= 1073741824; 2068 } 2069 // If NLP then we assume already solved outside branchAndbound 2070 if (!solverCharacteristics_->solverType() || solverCharacteristics_->solverType() == 4) { 2071 feasible = resolve(NULL, 0) != 0 ; 2072 } else { 2073 // pick up given status 2074 feasible = (solver_->isProvenOptimal() && 2075 !solver_->isDualObjectiveLimitReached()) ; 2076 } 2077 if (problemFeasibility_->feasible(this, 0) < 0) { 2078 feasible = false; // pretend infeasible 2079 } 2080 numberSavedSolutions_ = 0; 2081 int saveNumberStrong = numberStrong_; 2082 int saveNumberBeforeTrust = numberBeforeTrust_; 2083 /* 2013 printf("TEMP switching off crunch\n"); 2014 int iOpt = clpSolver->specialOptions(); 2015 iOpt &= ~1; 2016 iOpt |= 65536; 2017 clpSolver->setSpecialOptions(iOpt); 2018 #endif 2019 } 2020 } 2021 #endif 2022 bool feasible; 2023 numberSolves_ = 0; 2024 { 2025 // check 2026 int numberOdd = 0; 2027 for (int i = 0; i < numberObjects_; i++) { 2028 CbcSimpleInteger *obj = dynamic_cast<CbcSimpleInteger *>(object_[i]); 2029 if (!obj) 2030 numberOdd++; 2031 } 2032 if (numberOdd) 2033 moreSpecialOptions_ |= 1073741824; 2034 } 2035 // If NLP then we assume already solved outside branchAndbound 2036 if (!solverCharacteristics_->solverType() || solverCharacteristics_->solverType() == 4) { 2037 feasible = resolve(NULL, 0) != 0; 2038 } else { 2039 // pick up given status 2040 feasible = (solver_->isProvenOptimal() && !solver_->isDualObjectiveLimitReached()); 2041 } 2042 if (problemFeasibility_->feasible(this, 0) < 0) { 2043 feasible = false; // pretend infeasible 2044 } 2045 numberSavedSolutions_ = 0; 2046 int saveNumberStrong = numberStrong_; 2047 int saveNumberBeforeTrust = numberBeforeTrust_; 2048 /* 2084 2049 If the linear relaxation of the root is infeasible, bail out now. Otherwise, 2085 2050 continue with processing the root node. 2086 2051 */ 2087 if (!feasible) { 2088 status_ = 0 ; 2089 if (!solver_->isProvenDualInfeasible()) { 2090 handler_->message(CBC_INFEAS, messages_) << CoinMessageEol ; 2091 secondaryStatus_ = 1; 2092 } else { 2093 handler_->message(CBC_UNBOUNDED, messages_) << CoinMessageEol ; 2094 secondaryStatus_ = 7; 2095 } 2096 originalContinuousObjective_ = COIN_DBL_MAX; 2097 if (bestSolution_ && 2098 ((specialOptions_&8388608)==0||(specialOptions_&2048)!=0)) { 2099 // best solution found by various heuristics - set solution 2100 char general[200]; 2101 sprintf(general,"Solution of %g already found by heuristic", 2102 bestObjective_); 2103 messageHandler()->message(CBC_GENERAL, 2104 messages()) 2105 << general << CoinMessageEol ; 2106 setCutoff(1.0e50) ; // As best solution should be worse than cutoff 2107 // change cutoff as constraint if wanted 2108 if (cutoffRowNumber_>=0) { 2109 if (solver_->getNumRows()>cutoffRowNumber_) 2110 solver_->setRowUpper(cutoffRowNumber_,1.0e50); 2111 } 2112 // also in continuousSolver_ 2113 if (continuousSolver_) { 2114 // Solvers know about direction 2115 double direction = solver_->getObjSense(); 2116 continuousSolver_->setDblParam(OsiDualObjectiveLimit, 1.0e50*direction); 2117 } else { 2118 continuousSolver_ = solver_->clone(); 2119 } 2120 phase_ = 5; 2121 double increment = getDblParam(CbcModel::CbcCutoffIncrement) ; 2122 if ((specialOptions_&4) == 0) 2123 bestObjective_ += 100.0 * increment + 1.0e-3; // only set if we are going to solve 2124 setBestSolution(CBC_END_SOLUTION, bestObjective_, bestSolution_, 1) ; 2125 continuousSolver_->resolve() ; 2126 if (!continuousSolver_->isProvenOptimal()) { 2127 continuousSolver_->messageHandler()->setLogLevel(2) ; 2128 continuousSolver_->initialSolve() ; 2129 } 2130 delete solver_ ; 2131 solverCharacteristics_=NULL; 2132 solver_ = continuousSolver_ ; 2133 setPointers(solver_); 2134 continuousSolver_ = NULL ; 2135 } 2136 solverCharacteristics_ = NULL; 2137 if (flipObjective) 2138 flipModel(); 2139 return ; 2140 } else if (!numberObjects_) { 2141 // nothing to do 2142 // Undo preprocessing performed during BaB. 2143 if (strategy_ && strategy_->preProcessState() > 0) { 2144 // undo preprocessing 2145 CglPreProcess * process = strategy_->process(); 2146 assert (process); 2147 int n = originalSolver->getNumCols(); 2148 if (bestSolution_) { 2149 delete [] bestSolution_; 2150 bestSolution_ = new double [n]; 2151 process->postProcess(*solver_); 2152 } 2153 strategy_->deletePreProcess(); 2154 // Solution now back in originalSolver 2155 delete solver_; 2156 solver_ = originalSolver; 2157 if (bestSolution_) { 2158 bestObjective_ = solver_->getObjValue() * solver_->getObjSense(); 2159 memcpy(bestSolution_, solver_->getColSolution(), n*sizeof(double)); 2160 } 2161 // put back original objects if there were any 2162 if (originalObject) { 2163 int iColumn; 2164 assert (ownObjects_); 2165 for (iColumn = 0; iColumn < numberObjects_; iColumn++) 2166 delete object_[iColumn]; 2167 delete [] object_; 2168 numberObjects_ = numberOriginalObjects; 2169 object_ = originalObject; 2170 delete [] integerVariable_; 2171 numberIntegers_ = 0; 2172 for (iColumn = 0; iColumn < n; iColumn++) { 2173 if (solver_->isInteger(iColumn)) 2174 numberIntegers_++; 2175 } 2176 integerVariable_ = new int[numberIntegers_]; 2177 numberIntegers_ = 0; 2178 for (iColumn = 0; iColumn < n; iColumn++) { 2179 if (solver_->isInteger(iColumn)) 2180 integerVariable_[numberIntegers_++] = iColumn; 2181 } 2182 } 2183 } 2184 if (flipObjective) 2185 flipModel(); 2186 solverCharacteristics_ = NULL; 2052 if (!feasible) { 2053 status_ = 0; 2054 if (!solver_->isProvenDualInfeasible()) { 2055 handler_->message(CBC_INFEAS, messages_) << CoinMessageEol; 2056 secondaryStatus_ = 1; 2057 } else { 2058 handler_->message(CBC_UNBOUNDED, messages_) << CoinMessageEol; 2059 secondaryStatus_ = 7; 2060 } 2061 originalContinuousObjective_ = COIN_DBL_MAX; 2062 if (bestSolution_ && ((specialOptions_ & 8388608) == 0 || (specialOptions_ & 2048) != 0)) { 2063 // best solution found by various heuristics - set solution 2064 char general[200]; 2065 sprintf(general, "Solution of %g already found by heuristic", 2066 bestObjective_); 2067 messageHandler()->message(CBC_GENERAL, 2068 messages()) 2069 << general << CoinMessageEol; 2070 setCutoff(1.0e50); // As best solution should be worse than cutoff 2071 // change cutoff as constraint if wanted 2072 if (cutoffRowNumber_ >= 0) { 2073 if (solver_->getNumRows() > cutoffRowNumber_) 2074 solver_->setRowUpper(cutoffRowNumber_, 1.0e50); 2075 } 2076 // also in continuousSolver_ 2077 if (continuousSolver_) { 2078 // Solvers know about direction 2079 double direction = solver_->getObjSense(); 2080 continuousSolver_->setDblParam(OsiDualObjectiveLimit, 1.0e50 * direction); 2081 } else { 2082 continuousSolver_ = solver_->clone(); 2083 } 2084 phase_ = 5; 2085 double increment = getDblParam(CbcModel::CbcCutoffIncrement); 2086 if ((specialOptions_ & 4) == 0) 2087 bestObjective_ += 100.0 * increment + 1.0e-3; // only set if we are going to solve 2088 setBestSolution(CBC_END_SOLUTION, bestObjective_, bestSolution_, 1); 2089 continuousSolver_->resolve(); 2090 if (!continuousSolver_->isProvenOptimal()) { 2091 continuousSolver_->messageHandler()->setLogLevel(2); 2092 continuousSolver_->initialSolve(); 2093 } 2094 delete solver_; 2095 solverCharacteristics_ = NULL; 2096 solver_ = continuousSolver_; 2097 setPointers(solver_); 2098 continuousSolver_ = NULL; 2099 } 2100 solverCharacteristics_ = NULL; 2101 if (flipObjective) 2102 flipModel(); 2103 return; 2104 } else if (!numberObjects_) { 2105 // nothing to do 2106 // Undo preprocessing performed during BaB. 2107 if (strategy_ && strategy_->preProcessState() > 0) { 2108 // undo preprocessing 2109 CglPreProcess *process = strategy_->process(); 2110 assert(process); 2111 int n = originalSolver->getNumCols(); 2112 if (bestSolution_) { 2113 delete[] bestSolution_; 2114 bestSolution_ = new double[n]; 2115 process->postProcess(*solver_); 2116 } 2117 strategy_->deletePreProcess(); 2118 // Solution now back in originalSolver 2119 delete solver_; 2120 solver_ = originalSolver; 2121 if (bestSolution_) { 2187 2122 bestObjective_ = solver_->getObjValue() * solver_->getObjSense(); 2188 int numberColumns = solver_->getNumCols(); 2189 delete [] bestSolution_; 2190 bestSolution_ = new double[numberColumns]; 2191 CoinCopyN(solver_->getColSolution(), numberColumns, bestSolution_); 2192 return ; 2193 } 2194 /* 2123 memcpy(bestSolution_, solver_->getColSolution(), n * sizeof(double)); 2124 } 2125 // put back original objects if there were any 2126 if (originalObject) { 2127 int iColumn; 2128 assert(ownObjects_); 2129 for (iColumn = 0; iColumn < numberObjects_; iColumn++) 2130 delete object_[iColumn]; 2131 delete[] object_; 2132 numberObjects_ = numberOriginalObjects; 2133 object_ = originalObject; 2134 delete[] integerVariable_; 2135 numberIntegers_ = 0; 2136 for (iColumn = 0; iColumn < n; iColumn++) { 2137 if (solver_->isInteger(iColumn)) 2138 numberIntegers_++; 2139 } 2140 integerVariable_ = new int[numberIntegers_]; 2141 numberIntegers_ = 0; 2142 for (iColumn = 0; iColumn < n; iColumn++) { 2143 if (solver_->isInteger(iColumn)) 2144 integerVariable_[numberIntegers_++] = iColumn; 2145 } 2146 } 2147 } 2148 if (flipObjective) 2149 flipModel(); 2150 solverCharacteristics_ = NULL; 2151 bestObjective_ = solver_->getObjValue() * solver_->getObjSense(); 2152 int numberColumns = solver_->getNumCols(); 2153 delete[] bestSolution_; 2154 bestSolution_ = new double[numberColumns]; 2155 CoinCopyN(solver_->getColSolution(), numberColumns, bestSolution_); 2156 return; 2157 } 2158 /* 2195 2159 See if we're using the Osi side of the branching hierarchy. If so, either 2196 2160 convert existing CbcObjects to OsiObjects, or generate them fresh. In the … … 2206 2170 really dead code, and object detection is now handled from the Osi side. 2207 2171 */ 2208 // Convert to Osi if wanted 2209 //OsiBranchingInformation * persistentInfo = NULL; 2210 if (branchingMethod_ && branchingMethod_->chooseMethod()) { 2211 //persistentInfo = new OsiBranchingInformation(solver_); 2212 if (numberOriginalObjects) { 2213 for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) { 2214 CbcObject * obj = 2215 dynamic_cast <CbcObject *>(object_[iObject]) ; 2216 if (obj) { 2217 CbcSimpleInteger * obj2 = 2218 dynamic_cast <CbcSimpleInteger *>(obj) ; 2219 if (obj2) { 2220 // back to Osi land 2221 object_[iObject] = obj2->osiObject(); 2222 delete obj; 2223 } else { 2224 OsiSimpleInteger * obj3 = 2225 dynamic_cast <OsiSimpleInteger *>(obj) ; 2226 if (!obj3) { 2227 OsiSOS * obj4 = 2228 dynamic_cast <OsiSOS *>(obj) ; 2229 if (!obj4) { 2230 CbcSOS * obj5 = 2231 dynamic_cast <CbcSOS *>(obj) ; 2232 if (obj5) { 2233 // back to Osi land 2234 object_[iObject] = obj5->osiObject(solver_); 2235 } else { 2236 printf("Code up CbcObject type in Osi land\n"); 2237 abort(); 2238 } 2239 } 2240 } 2241 } 2172 // Convert to Osi if wanted 2173 //OsiBranchingInformation * persistentInfo = NULL; 2174 if (branchingMethod_ && branchingMethod_->chooseMethod()) { 2175 //persistentInfo = new OsiBranchingInformation(solver_); 2176 if (numberOriginalObjects) { 2177 for (int iObject = 0; iObject < numberObjects_; iObject++) { 2178 CbcObject *obj = dynamic_cast<CbcObject *>(object_[iObject]); 2179 if (obj) { 2180 CbcSimpleInteger *obj2 = dynamic_cast<CbcSimpleInteger *>(obj); 2181 if (obj2) { 2182 // back to Osi land 2183 object_[iObject] = obj2->osiObject(); 2184 delete obj; 2185 } else { 2186 OsiSimpleInteger *obj3 = dynamic_cast<OsiSimpleInteger *>(obj); 2187 if (!obj3) { 2188 OsiSOS *obj4 = dynamic_cast<OsiSOS *>(obj); 2189 if (!obj4) { 2190 CbcSOS *obj5 = dynamic_cast<CbcSOS *>(obj); 2191 if (obj5) { 2192 // back to Osi land 2193 object_[iObject] = obj5->osiObject(solver_); 2194 } else { 2195 printf("Code up CbcObject type in Osi land\n"); 2196 abort(); 2242 2197 } 2198 } 2243 2199 } 2244 // and add to solver 2245 //if (!solver_->numberObjects()) { 2246 solver_->addObjects(numberObjects_, object_); 2247 //} else { 2248 //if (solver_->numberObjects()!=numberOriginalObjects) { 2249 //printf("should have trapped that solver has objects before\n"); 2250 //abort(); 2251 //} 2252 //} 2253 } else { 2254 /* 2200 } 2201 } 2202 } 2203 // and add to solver 2204 //if (!solver_->numberObjects()) { 2205 solver_->addObjects(numberObjects_, object_); 2206 //} else { 2207 //if (solver_->numberObjects()!=numberOriginalObjects) { 2208 //printf("should have trapped that solver has objects before\n"); 2209 //abort(); 2210 //} 2211 //} 2212 } else { 2213 /* 2255 2214 As of 080104, findIntegersAndSOS is misleading --- the default OSI 2256 2215 implementation finds only integers. 2257 2216 */ 2258 // do from solver 2259 deleteObjects(false); 2260 solver_->findIntegersAndSOS(false); 2261 numberObjects_ = solver_->numberObjects(); 2262 object_ = solver_->objects(); 2263 ownObjects_ = false; 2264 } 2265 branchingMethod_->chooseMethod()->setSolver(solver_); 2266 } 2267 // take off heuristics if have to (some do not work with SOS, for example) 2268 // object should know what's safe. 2269 { 2270 int numberOdd = 0; 2271 int numberSOS = 0; 2272 for (int i = 0; i < numberObjects_; i++) { 2273 if (!object_[i]->canDoHeuristics()) 2274 numberOdd++; 2275 CbcSOS * obj = 2276 dynamic_cast <CbcSOS *>(object_[i]) ; 2277 if (obj) 2278 numberSOS++; 2279 } 2280 if (numberOdd) { 2281 if (numberHeuristics_ && (specialOptions_&1024)==0 ) { 2282 int k = 0; 2283 for (int i = 0; i < numberHeuristics_; i++) { 2284 if (!heuristic_[i]->canDealWithOdd()) 2285 delete heuristic_[i]; 2286 else 2287 heuristic_[k++] = heuristic_[i]; 2288 } 2289 if (!k) { 2290 delete [] heuristic_; 2291 heuristic_ = NULL; 2292 } 2293 numberHeuristics_ = k; 2294 handler_->message(CBC_HEURISTICS_OFF, messages_) << numberOdd << CoinMessageEol ; 2295 } 2296 // If odd switch off AddIntegers 2297 specialOptions_ &= ~65536; 2298 // switch off fast nodes for now 2299 fastNodeDepth_ = -1; 2300 moreSpecialOptions_ &= ~33554432; // no diving 2301 } else if (numberSOS) { 2302 specialOptions_ |= 128; // say can do SOS in dynamic mode 2303 // switch off fast nodes for now 2304 fastNodeDepth_ = -1; 2305 moreSpecialOptions_ &= ~33554432; // no diving 2306 } 2307 if (numberThreads_ > 0) { 2308 /* switch off fast nodes for now 2217 // do from solver 2218 deleteObjects(false); 2219 solver_->findIntegersAndSOS(false); 2220 numberObjects_ = solver_->numberObjects(); 2221 object_ = solver_->objects(); 2222 ownObjects_ = false; 2223 } 2224 branchingMethod_->chooseMethod()->setSolver(solver_); 2225 } 2226 // take off heuristics if have to (some do not work with SOS, for example) 2227 // object should know what's safe. 2228 { 2229 int numberOdd = 0; 2230 int numberSOS = 0; 2231 for (int i = 0; i < numberObjects_; i++) { 2232 if (!object_[i]->canDoHeuristics()) 2233 numberOdd++; 2234 CbcSOS *obj = dynamic_cast<CbcSOS *>(object_[i]); 2235 if (obj) 2236 numberSOS++; 2237 } 2238 if (numberOdd) { 2239 if (numberHeuristics_ && (specialOptions_ & 1024) == 0) { 2240 int k = 0; 2241 for (int i = 0; i < numberHeuristics_; i++) { 2242 if (!heuristic_[i]->canDealWithOdd()) 2243 delete heuristic_[i]; 2244 else 2245 heuristic_[k++] = heuristic_[i]; 2246 } 2247 if (!k) { 2248 delete[] heuristic_; 2249 heuristic_ = NULL; 2250 } 2251 numberHeuristics_ = k; 2252 handler_->message(CBC_HEURISTICS_OFF, messages_) << numberOdd << CoinMessageEol; 2253 } 2254 // If odd switch off AddIntegers 2255 specialOptions_ &= ~65536; 2256 // switch off fast nodes for now 2257 fastNodeDepth_ = -1; 2258 moreSpecialOptions_ &= ~33554432; // no diving 2259 } else if (numberSOS) { 2260 specialOptions_ |= 128; // say can do SOS in dynamic mode 2261 // switch off fast nodes for now 2262 fastNodeDepth_ = -1; 2263 moreSpecialOptions_ &= ~33554432; // no diving 2264 } 2265 if (numberThreads_ > 0) { 2266 /* switch off fast nodes for now 2309 2267 Trouble is that by time mini bab finishes code is 2310 2268 looking at a different node 2311 2269 */ 2312 2313 2314 2315 2316 originalContinuousObjective_ = solver_->getObjValue()* solver_->getObjSense();2317 2318 2319 2320 2270 fastNodeDepth_ = -1; 2271 } 2272 } 2273 // Save objective (just so user can access it) 2274 originalContinuousObjective_ = solver_->getObjValue() * solver_->getObjSense(); 2275 bestPossibleObjective_ = originalContinuousObjective_; 2276 sumChangeObjective1_ = 0.0; 2277 sumChangeObjective2_ = 0.0; 2278 /* 2321 2279 OsiRowCutDebugger knows an optimal answer for a subset of MIP problems. 2322 2280 Assuming it recognises the problem, when called upon it will check a cut to 2323 2281 see if it cuts off the optimal answer. 2324 2282 */ 2325 2326 2327 2328 2329 2330 # 2331 if ((specialOptions_&1) == 0)2332 solver_->activateRowCutDebugger(problemName.c_str());2333 2334 2335 # 2336 2337 2283 // If debugger exists set specialOptions_ bit 2284 if (solver_->getRowCutDebuggerAlways()) { 2285 specialOptions_ |= 1; 2286 } 2287 2288 #ifdef CBC_DEBUG 2289 if ((specialOptions_ & 1) == 0) 2290 solver_->activateRowCutDebugger(problemName.c_str()); 2291 if (solver_->getRowCutDebuggerAlways()) 2292 specialOptions_ |= 1; 2293 #endif 2294 2295 /* 2338 2296 Begin setup to process a feasible root node. 2339 2297 */ 2340 bestObjective_ = CoinMin(bestObjective_, 1.0e50);2341 2342 numberSolutions_ = 0;2343 numberHeuristicSolutions_ = 0;2344 2345 2346 2347 2348 2349 double value;2350 solver_->getDblParam(OsiDualObjectiveLimit, value);2351 2352 2353 double cutoff = getCutoff();2354 double direction = solver_->getObjSense();2355 2356 2357 2358 2359 << cutoff << -cutoff << CoinMessageEol;2360 2361 cutoff = bestObjective_;2362 setCutoff(cutoff);2363 2298 bestObjective_ = CoinMin(bestObjective_, 1.0e50); 2299 if (!bestSolution_) { 2300 numberSolutions_ = 0; 2301 numberHeuristicSolutions_ = 0; 2302 } 2303 stateOfSearch_ = 0; 2304 // Everything is minimization 2305 { 2306 // needed to sync cutoffs 2307 double value; 2308 solver_->getDblParam(OsiDualObjectiveLimit, value); 2309 dblParam_[CbcCurrentCutoff] = value * solver_->getObjSense(); 2310 } 2311 double cutoff = getCutoff(); 2312 double direction = solver_->getObjSense(); 2313 dblParam_[CbcOptimizationDirection] = direction; 2314 if (cutoff < 1.0e20 && direction < 0.0) 2315 messageHandler()->message(CBC_CUTOFF_WARNING1, 2316 messages()) 2317 << cutoff << -cutoff << CoinMessageEol; 2318 if (cutoff > bestObjective_) 2319 cutoff = bestObjective_; 2320 setCutoff(cutoff); 2321 /* 2364 2322 We probably already have a current solution, but just in case ... 2365 2323 */ 2366 int numberColumns = getNumCols();2367 2368 currentSolution_ = new double[numberColumns];2369 2370 2324 int numberColumns = getNumCols(); 2325 if (!currentSolution_) 2326 currentSolution_ = new double[numberColumns]; 2327 testSolution_ = currentSolution_; 2328 /* 2371 2329 Create a copy of the solver, thus capturing the original (root node) 2372 2330 constraint system (aka the continuous system). 2373 2331 */ 2374 2375 continuousSolver_ = solver_->clone();2332 delete continuousSolver_; 2333 continuousSolver_ = solver_->clone(); 2376 2334 #ifdef CONFLICT_CUTS 2377 if ((moreSpecialOptions_&4194304)!=0) {2335 if ((moreSpecialOptions_ & 4194304) != 0) { 2378 2336 #ifdef COIN_HAS_CLP 2379 OsiClpSolverInterface *clpSolver2380 = dynamic_cast<OsiClpSolverInterface *>(solver_);2381 2382 int specialOptions=clpSolver->getModelPtr()->specialOptions();2383 2384 2385 clpSolver->getModelPtr()->setSpecialOptions(specialOptions|32|2097152);2386 2387 clpSolver->getModelPtr()->setSpecialOptions(specialOptions&~(32|2097152));2388 2389 2337 OsiClpSolverInterface *clpSolver 2338 = dynamic_cast<OsiClpSolverInterface *>(solver_); 2339 if (clpSolver) { 2340 int specialOptions = clpSolver->getModelPtr()->specialOptions(); 2341 // 2097152 switches on rays in crunch 2342 if (!parentModel_) 2343 clpSolver->getModelPtr()->setSpecialOptions(specialOptions | 32 | 2097152); 2344 else 2345 clpSolver->getModelPtr()->setSpecialOptions(specialOptions & ~(32 | 2097152)); 2346 } 2347 } 2390 2348 #endif 2391 2349 #endif 2392 2350 #ifdef COIN_HAS_NTY 2393 // maybe allow on fix and restart later 2394 if ((moreSpecialOptions2_&(128|256))!=0&&!parentModel_) { 2395 symmetryInfo_ = new CbcSymmetry(); 2396 symmetryInfo_->setupSymmetry(*continuousSolver_); 2397 int numberGenerators = symmetryInfo_->statsOrbits(this,0); 2398 if (!symmetryInfo_->numberUsefulOrbits()&&(moreSpecialOptions2_&(128|256))!=(128|256)) { 2399 delete symmetryInfo_; 2400 symmetryInfo_=NULL; 2401 moreSpecialOptions2_ &= ~(128|256); 2402 } 2403 if ((moreSpecialOptions2_&(128|256))==(128|256)) { 2404 //moreSpecialOptions2_ &= ~256; 2405 } 2406 } 2407 #endif 2408 2409 // add cutoff as constraint if wanted 2410 if (cutoffRowNumber_==-2) { 2411 if (!parentModel_) { 2412 int numberColumns=solver_->getNumCols(); 2413 double * obj = CoinCopyOfArray(solver_->getObjCoefficients(),numberColumns); 2414 int * indices = new int [numberColumns]; 2415 int n=0; 2416 for (int i=0;i<numberColumns;i++) { 2417 if (obj[i]) { 2418 indices[n]=i; 2419 obj[n++]=obj[i]; 2420 } 2421 } 2422 if (n) { 2423 double cutoff=getCutoff(); 2424 // relax a little bit 2425 cutoff += 1.0e-4; 2426 double offset; 2427 solver_->getDblParam(OsiObjOffset, offset); 2428 cutoffRowNumber_ = solver_->getNumRows(); 2429 solver_->addRow(n,indices,obj,-COIN_DBL_MAX,CoinMin(cutoff,1.0e25)+offset); 2430 } else { 2431 // no objective! 2432 cutoffRowNumber_ = -1; 2433 } 2434 delete [] indices; 2435 delete [] obj; 2351 // maybe allow on fix and restart later 2352 if ((moreSpecialOptions2_ & (128 | 256)) != 0 && !parentModel_) { 2353 symmetryInfo_ = new CbcSymmetry(); 2354 symmetryInfo_->setupSymmetry(*continuousSolver_); 2355 int numberGenerators = symmetryInfo_->statsOrbits(this, 0); 2356 if (!symmetryInfo_->numberUsefulOrbits() && (moreSpecialOptions2_ & (128 | 256)) != (128 | 256)) { 2357 delete symmetryInfo_; 2358 symmetryInfo_ = NULL; 2359 moreSpecialOptions2_ &= ~(128 | 256); 2360 } 2361 if ((moreSpecialOptions2_ & (128 | 256)) == (128 | 256)) { 2362 //moreSpecialOptions2_ &= ~256; 2363 } 2364 } 2365 #endif 2366 2367 // add cutoff as constraint if wanted 2368 if (cutoffRowNumber_ == -2) { 2369 if (!parentModel_) { 2370 int numberColumns = solver_->getNumCols(); 2371 double *obj = CoinCopyOfArray(solver_->getObjCoefficients(), numberColumns); 2372 int *indices = new int[numberColumns]; 2373 int n = 0; 2374 for (int i = 0; i < numberColumns; i++) { 2375 if (obj[i]) { 2376 indices[n] = i; 2377 obj[n++] = obj[i]; 2378 } 2379 } 2380 if (n) { 2381 double cutoff = getCutoff(); 2382 // relax a little bit 2383 cutoff += 1.0e-4; 2384 double offset; 2385 solver_->getDblParam(OsiObjOffset, offset); 2386 cutoffRowNumber_ = solver_->getNumRows(); 2387 solver_->addRow(n, indices, obj, -COIN_DBL_MAX, CoinMin(cutoff, 1.0e25) + offset); 2436 2388 } else { 2437 // switch off 2438 cutoffRowNumber_ = -1; 2439 } 2440 } 2441 numberRowsAtContinuous_ = getNumRows() ; 2442 solver_->saveBaseModel(); 2443 /* 2389 // no objective! 2390 cutoffRowNumber_ = -1; 2391 } 2392 delete[] indices; 2393 delete[] obj; 2394 } else { 2395 // switch off 2396 cutoffRowNumber_ = -1; 2397 } 2398 } 2399 numberRowsAtContinuous_ = getNumRows(); 2400 solver_->saveBaseModel(); 2401 /* 2444 2402 Check the objective to see if we can deduce a nontrivial increment. If 2445 2403 it's better than the current value for CbcCutoffIncrement, it'll be 2446 2404 installed. 2447 2405 */ 2448 2449 analyzeObjective();2450 2451 2452 2453 double increment = getDblParam(CbcModel::CbcCutoffIncrement);2454 2455 cutoff = bestObjective_ - increment;2456 setCutoff(cutoff);2457 2458 2406 if (solverCharacteristics_->reducedCostsAccurate()) 2407 analyzeObjective(); 2408 { 2409 // may be able to change cutoff now 2410 double cutoff = getCutoff(); 2411 double increment = getDblParam(CbcModel::CbcCutoffIncrement); 2412 if (cutoff > bestObjective_ - increment) { 2413 cutoff = bestObjective_ - increment; 2414 setCutoff(cutoff); 2415 } 2416 } 2459 2417 #ifdef COIN_HAS_CLP 2460 2461 ClpDualRowPivot *savePivotMethod = NULL;2462 2463 2464 OsiClpSolverInterface *clpSolver2465 = dynamic_cast<OsiClpSolverInterface *>(solver_);2466 2467 2418 // Possible save of pivot method 2419 ClpDualRowPivot *savePivotMethod = NULL; 2420 { 2421 // pass tolerance and increment to solver 2422 OsiClpSolverInterface *clpSolver 2423 = dynamic_cast<OsiClpSolverInterface *>(solver_); 2424 if (clpSolver) 2425 clpSolver->setStuff(getIntegerTolerance(), getCutoffIncrement()); 2468 2426 #ifdef CLP_RESOLVE 2469 if ((moreSpecialOptions_&1048576)!=0&&!parentModel_&&clpSolver) {2470 resolveClp(clpSolver,0);2471 2472 #endif 2473 2474 #endif 2475 2427 if ((moreSpecialOptions_ & 1048576) != 0 && !parentModel_ && clpSolver) { 2428 resolveClp(clpSolver, 0); 2429 } 2430 #endif 2431 } 2432 #endif 2433 /* 2476 2434 Set up for cut generation. addedCuts_ holds the cuts which are relevant for 2477 2435 the active subproblem. whichGenerator will be used to record the generator … … 2479 2437 */ 2480 2438 #define INITIAL_MAXIMUM_WHICH 1000 2481 maximumWhich_ = INITIAL_MAXIMUM_WHICH;2482 delete[] whichGenerator_;2483 whichGenerator_ = new int[maximumWhich_];2484 memset(whichGenerator_, 0, maximumWhich_*sizeof(int));2485 maximumNumberCuts_ = 0;2486 currentNumberCuts_ = 0;2487 delete [] addedCuts_;2488 addedCuts_ = NULL;2489 OsiObject **saveObjects = NULL;2490 2491 2492 2493 2439 maximumWhich_ = INITIAL_MAXIMUM_WHICH; 2440 delete[] whichGenerator_; 2441 whichGenerator_ = new int[maximumWhich_]; 2442 memset(whichGenerator_, 0, maximumWhich_ * sizeof(int)); 2443 maximumNumberCuts_ = 0; 2444 currentNumberCuts_ = 0; 2445 delete[] addedCuts_; 2446 addedCuts_ = NULL; 2447 OsiObject **saveObjects = NULL; 2448 maximumRows_ = numberRowsAtContinuous_; 2449 currentDepth_ = 0; 2450 workingBasis_.resize(maximumRows_, numberColumns); 2451 /* 2494 2452 Set up an empty heap and associated data structures to hold the live set 2495 2453 (problems which require further exploration). 2496 2454 */ 2497 CbcCompareDefault *compareActual2498 = dynamic_cast<CbcCompareDefault *> 2499 2500 compareActual->setBestPossible(direction*solver_->getObjValue());2501 2455 CbcCompareDefault *compareActual 2456 = dynamic_cast<CbcCompareDefault *>(nodeCompare_); 2457 if (compareActual) { 2458 compareActual->setBestPossible(direction * solver_->getObjValue()); 2459 compareActual->setCutoff(getCutoff()); 2502 2460 #ifdef JJF_ZERO 2503 2504 2505 2506 2507 2508 2509 #endif 2510 2511 tree_->setComparison(*nodeCompare_);2512 2461 if (false && !numberThreads_ && !parentModel_) { 2462 printf("CbcTreeArray ? threads ? parentArray\n"); 2463 // Setup new style tree 2464 delete tree_; 2465 tree_ = new CbcTreeArray(); 2466 } 2467 #endif 2468 } 2469 tree_->setComparison(*nodeCompare_); 2470 /* 2513 2471 Used to record the path from a node to the root of the search tree, so that 2514 2472 we can then traverse from the root to the node when restoring a subproblem. 2515 2473 */ 2516 maximumDepth_ = 10;2517 delete [] walkback_;2518 walkback_ = new CbcNodeInfo * [maximumDepth_];2519 2520 delete [] lastNodeInfo_;2521 lastNodeInfo_ = new CbcNodeInfo * [maximumDepth_];2522 delete [] lastNumberCuts_;2523 lastNumberCuts_ = new int [maximumDepth_];2524 2525 2526 delete[] lastCut_;2527 lastCut_ = new const OsiRowCut *[maximumCuts_];2528 2474 maximumDepth_ = 10; 2475 delete[] walkback_; 2476 walkback_ = new CbcNodeInfo *[maximumDepth_]; 2477 lastDepth_ = 0; 2478 delete[] lastNodeInfo_; 2479 lastNodeInfo_ = new CbcNodeInfo *[maximumDepth_]; 2480 delete[] lastNumberCuts_; 2481 lastNumberCuts_ = new int[maximumDepth_]; 2482 maximumCuts_ = 100; 2483 lastNumberCuts2_ = 0; 2484 delete[] lastCut_; 2485 lastCut_ = new const OsiRowCut *[maximumCuts_]; 2486 /* 2529 2487 Used to generate bound edits for CbcPartialNodeInfo. 2530 2488 */ 2531 double * lowerBefore = new double [numberColumns];2532 double * upperBefore = new double [numberColumns];2533 2489 double *lowerBefore = new double[numberColumns]; 2490 double *upperBefore = new double[numberColumns]; 2491 /* 2534 2492 Set up to run heuristics and generate cuts at the root node. The heavy 2535 2493 lifting is hidden inside the calls to doHeuristicsAtRoot and solveWithCuts. … … 2558 2516 TODO: If numberUnsatisfied == 0, don't we have a solution? 2559 2517 */ 2560 2561 2562 2563 2564 2565 2566 2567 2568 CglCutGenerator *generator = generator_[iCutGenerator]->generator();2569 2570 2571 2572 2573 OsiCuts cuts;2574 int anyAction = -1;2575 numberOldActiveCuts_ = 0;2576 numberNewCuts_ = 0;2577 2578 delete[] usedInSolution_;2579 2580 2581 2518 phase_ = 1; 2519 int iCutGenerator; 2520 for (iCutGenerator = 0; iCutGenerator < numberCutGenerators_; iCutGenerator++) { 2521 // If parallel switch off global cuts 2522 if (numberThreads_) { 2523 generator_[iCutGenerator]->setGlobalCuts(false); 2524 generator_[iCutGenerator]->setGlobalCutsAtRoot(false); 2525 } 2526 CglCutGenerator *generator = generator_[iCutGenerator]->generator(); 2527 generator->setAggressiveness(generator->getAggressiveness() + 100); 2528 if (!generator->canDoGlobalCuts()) 2529 generator->setGlobalCuts(false); 2530 } 2531 OsiCuts cuts; 2532 int anyAction = -1; 2533 numberOldActiveCuts_ = 0; 2534 numberNewCuts_ = 0; 2535 // Array to mark solution 2536 delete[] usedInSolution_; 2537 usedInSolution_ = new int[numberColumns]; 2538 CoinZeroN(usedInSolution_, numberColumns); 2539 /* 2582 2540 For printing totals and for CbcNode (numberNodes_) 2583 2541 */ 2584 numberIterations_ = 0;2585 numberNodes_ = 0;2586 numberNodes2_ = 0;2587 2588 2589 2590 2591 if ((specialOptions_&262144) != 0) {2592 2593 2594 } else if ((specialOptions_&524288) != 0 && storedRowCuts_) {2595 2596 2597 2542 numberIterations_ = 0; 2543 numberNodes_ = 0; 2544 numberNodes2_ = 0; 2545 maximumStatistics_ = 0; 2546 maximumDepthActual_ = 0; 2547 numberDJFixed_ = 0.0; 2548 if (!parentModel_) { 2549 if ((specialOptions_ & 262144) != 0) { 2550 // create empty stored cuts 2551 //storedRowCuts_ = new CglStored(solver_->getNumCols()); 2552 } else if ((specialOptions_ & 524288) != 0 && storedRowCuts_) { 2553 // tighten and set best solution 2554 // A) tight bounds on integer variables 2555 /* 2598 2556 storedRowCuts_ are coming in from outside, probably for nonlinear. 2599 2557 John was unsure about origin. 2600 2558 */ 2601 const double *lower = solver_->getColLower();2602 const double *upper = solver_->getColUpper();2603 const double *tightLower = storedRowCuts_->tightLower();2604 const double *tightUpper = storedRowCuts_->tightUpper();2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 storedRowCuts_->bestSolution());2624 2625 2626 2627 CbcHeuristicRINS *rins2628 = dynamic_cast<CbcHeuristicRINS *>(heuristic_[i]);2629 2630 2631 2632 2633 2634 2635 2559 const double *lower = solver_->getColLower(); 2560 const double *upper = solver_->getColUpper(); 2561 const double *tightLower = storedRowCuts_->tightLower(); 2562 const double *tightUpper = storedRowCuts_->tightUpper(); 2563 int nTightened = 0; 2564 for (int i = 0; i < numberIntegers_; i++) { 2565 int iColumn = integerVariable_[i]; 2566 if (tightLower[iColumn] > lower[iColumn]) { 2567 nTightened++; 2568 solver_->setColLower(iColumn, tightLower[iColumn]); 2569 } 2570 if (tightUpper[iColumn] < upper[iColumn]) { 2571 nTightened++; 2572 solver_->setColUpper(iColumn, tightUpper[iColumn]); 2573 } 2574 } 2575 if (nTightened) 2576 COIN_DETAIL_PRINT(printf("%d tightened by alternate cuts\n", nTightened)); 2577 if (storedRowCuts_->bestObjective() < bestObjective_) { 2578 // B) best solution 2579 double objValue = storedRowCuts_->bestObjective(); 2580 setBestSolution(CBC_SOLUTION, objValue, 2581 storedRowCuts_->bestSolution()); 2582 // Do heuristics 2583 // Allow RINS 2584 for (int i = 0; i < numberHeuristics_; i++) { 2585 CbcHeuristicRINS *rins 2586 = dynamic_cast<CbcHeuristicRINS *>(heuristic_[i]); 2587 if (rins) { 2588 rins->setLastNode(-100); 2589 } 2590 } 2591 } 2592 } 2593 } 2636 2594 #ifdef SWITCH_VARIABLES 2637 2638 if (numberIntegers_<solver_->getNumCols())2639 2640 #endif 2641 2595 // see if any switching variables 2596 if (numberIntegers_ < solver_->getNumCols()) 2597 findSwitching(); 2598 #endif 2599 /* 2642 2600 Run heuristics at the root. This is the only opportunity to run FPump; it 2643 2601 will be removed from the heuristics list by doHeuristicsAtRoot. 2644 2602 */ 2645 2646 CbcModel ** rootModels=NULL;2647 if (!parentModel_&&multipleRootTries_%100) {2648 double rootTimeCpu=CoinCpuTime();2649 double startTimeRoot=CoinGetTimeOfDay();2650 int numberRootThreads=1;2651 2603 // See if multiple runs wanted 2604 CbcModel **rootModels = NULL; 2605 if (!parentModel_ && multipleRootTries_ % 100) { 2606 double rootTimeCpu = CoinCpuTime(); 2607 double startTimeRoot = CoinGetTimeOfDay(); 2608 int numberRootThreads = 1; 2609 /* undocumented fine tuning 2652 2610 aabbcc where cc is number of tries 2653 2611 bb if nonzero is number of threads 2654 2612 aa if nonzero just do heuristics 2655 2613 */ 2656 int numberModels = multipleRootTries_%100;2614 int numberModels = multipleRootTries_ % 100; 2657 2615 #ifdef CBC_THREAD 2658 numberRootThreads = (multipleRootTries_/100)%100;2659 2660 if (numberThreads_<2)2661 numberRootThreads=numberModels;2662 2663 numberRootThreads=CoinMin(numberThreads_,numberModels);2664 2665 #endif 2666 int otherOptions = (multipleRootTries_/10000)%100;2667 rootModels = new CbcModel *[numberModels];2668 2669 if (newSeed==0) {2670 2671 while (time>=COIN_INT_MAX)2672 2673 2674 } else if (newSeed<0) {2675 2616 numberRootThreads = (multipleRootTries_ / 100) % 100; 2617 if (!numberRootThreads) { 2618 if (numberThreads_ < 2) 2619 numberRootThreads = numberModels; 2620 else 2621 numberRootThreads = CoinMin(numberThreads_, numberModels); 2622 } 2623 #endif 2624 int otherOptions = (multipleRootTries_ / 10000) % 100; 2625 rootModels = new CbcModel *[numberModels]; 2626 unsigned int newSeed = randomSeed_; 2627 if (newSeed == 0) { 2628 double time = fabs(CoinGetTimeOfDay()); 2629 while (time >= COIN_INT_MAX) 2630 time *= 0.5; 2631 newSeed = static_cast<unsigned int>(time); 2632 } else if (newSeed < 0) { 2633 newSeed = 123456789; 2676 2634 #ifdef COIN_HAS_CLP 2677 OsiClpSolverInterface *clpSolver2678 = dynamic_cast<OsiClpSolverInterface *>(solver_);2679 2680 2681 2682 #endif 2683 2684 CoinWarmStartBasis * basis = dynamic_cast<CoinWarmStartBasis *>(solver_->getEmptyWarmStart());2685 for (int i=0;i<numberModels;i++) {2686 rootModels[i]=new CbcModel(*this);2687 2688 2689 rootModels[i]->setRandomSeed(newSeed+10000000*i);2690 rootModels[i]->randomNumberGenerator()->setSeed(newSeed+50000000*i);2691 2635 OsiClpSolverInterface *clpSolver 2636 = dynamic_cast<OsiClpSolverInterface *>(solver_); 2637 if (clpSolver) { 2638 newSeed += clpSolver->getModelPtr()->randomNumberGenerator()->getSeed(); 2639 } 2640 #endif 2641 } 2642 CoinWarmStartBasis *basis = dynamic_cast<CoinWarmStartBasis *>(solver_->getEmptyWarmStart()); 2643 for (int i = 0; i < numberModels; i++) { 2644 rootModels[i] = new CbcModel(*this); 2645 rootModels[i]->setNumberThreads(0); 2646 rootModels[i]->setMaximumNodes(otherOptions ? -1 : 0); 2647 rootModels[i]->setRandomSeed(newSeed + 10000000 * i); 2648 rootModels[i]->randomNumberGenerator()->setSeed(newSeed + 50000000 * i); 2649 rootModels[i]->setMultipleRootTries(0); 2692 2650 #ifdef COIN_HAS_NTY 2693 rootModels[i]->zapSymmetry(); 2694 rootModels[i]->moreSpecialOptions2_ &= ~(128|256); // off nauty 2695 #endif 2696 // use seed 2697 rootModels[i]->setSpecialOptions(specialOptions_ |(4194304|8388608)); 2698 rootModels[i]->setMoreSpecialOptions(moreSpecialOptions_ & 2699 (~(134217728|4194304))); 2700 rootModels[i]->setMoreSpecialOptions2(moreSpecialOptions2_ & 2701 (~(128|256))); 2702 rootModels[i]->solver_->setWarmStart(basis); 2651 rootModels[i]->zapSymmetry(); 2652 rootModels[i]->moreSpecialOptions2_ &= ~(128 | 256); // off nauty 2653 #endif 2654 // use seed 2655 rootModels[i]->setSpecialOptions(specialOptions_ | (4194304 | 8388608)); 2656 rootModels[i]->setMoreSpecialOptions(moreSpecialOptions_ & (~(134217728 | 4194304))); 2657 rootModels[i]->setMoreSpecialOptions2(moreSpecialOptions2_ & (~(128 | 256))); 2658 rootModels[i]->solver_->setWarmStart(basis); 2703 2659 #ifdef COIN_HAS_CLP 2704 OsiClpSolverInterface *clpSolver2705 = dynamic_cast<OsiClpSolverInterface *>(rootModels[i]->solver_);2660 OsiClpSolverInterface *clpSolver 2661 = dynamic_cast<OsiClpSolverInterface *>(rootModels[i]->solver_); 2706 2662 #define NEW_RANDOM_BASIS 2707 2663 #ifdef NEW_RANDOM_BASIS 2708 if (i==0)2709 2710 #endif 2711 2712 ClpSimplex *simplex = clpSolver->getModelPtr();2713 2714 2715 simplex->setRandomSeed(newSeed+20000000*i);2716 2717 int logLevel=simplex->logLevel();2718 if (logLevel==1)2719 2720 if (i!=0) {2664 if (i == 0) 2665 continue; 2666 #endif 2667 if (clpSolver) { 2668 ClpSimplex *simplex = clpSolver->getModelPtr(); 2669 if (defaultHandler_) 2670 simplex->setDefaultMessageHandler(); 2671 simplex->setRandomSeed(newSeed + 20000000 * i); 2672 simplex->allSlackBasis(); 2673 int logLevel = simplex->logLevel(); 2674 if (logLevel == 1) 2675 simplex->setLogLevel(0); 2676 if (i != 0) { 2721 2677 #ifdef NEW_RANDOM_BASIS 2722 2723 int throwOut=20;//2+numberRows/100;2724 for (int iThrow=0;iThrow<throwOut;iThrow++) {2725 2726 int iStart=static_cast<int>(random*numberRows);2727 for (int j=iStart;j<numberRows;j++) {2728 if (simplex->getRowStatus(j)!=ClpSimplex::basic) {2729 simplex->setRowStatus(j,ClpSimplex::basic);2730 2731 2732 2733 2734 2678 int numberRows = simplex->numberRows(); 2679 int throwOut = 20; //2+numberRows/100; 2680 for (int iThrow = 0; iThrow < throwOut; iThrow++) { 2681 double random = simplex->randomNumberGenerator()->randomDouble(); 2682 int iStart = static_cast<int>(random * numberRows); 2683 for (int j = iStart; j < numberRows; j++) { 2684 if (simplex->getRowStatus(j) != ClpSimplex::basic) { 2685 simplex->setRowStatus(j, ClpSimplex::basic); 2686 break; 2687 } 2688 } 2689 } 2690 clpSolver->setWarmStart(NULL); 2735 2691 #else 2736 2737 int bias = static_cast<int>(random*(numberIterations/4));2738 simplex->setMaximumIterations(numberIterations/2+bias);2739 2740 2741 2742 #endif 2743 2692 double random = simplex->randomNumberGenerator()->randomDouble(); 2693 int bias = static_cast<int>(random * (numberIterations / 4)); 2694 simplex->setMaximumIterations(numberIterations / 2 + bias); 2695 simplex->primal(); 2696 simplex->setMaximumIterations(COIN_INT_MAX); 2697 simplex->dual(); 2698 #endif 2699 } else { 2744 2700 #ifndef NEW_RANDOM_BASIS 2745 2746 #endif 2747 #endif 2748 2701 simplex->primal(); 2702 #endif 2703 #endif 2704 } 2749 2705 #ifdef NEW_RANDOM_BASIS 2750 2751 2752 #endif 2753 2754 for (int j=0;j<numberHeuristics_;j++)2755 rootModels[i]->heuristic_[j]->setSeed(rootModels[i]->heuristic_[j]->getSeed()+100000000*i);2756 for (int j=0;j<numberCutGenerators_;j++)2757 2758 2759 2706 simplex->setLogLevel(logLevel); 2707 clpSolver->setWarmStart(NULL); 2708 #endif 2709 } 2710 for (int j = 0; j < numberHeuristics_; j++) 2711 rootModels[i]->heuristic_[j]->setSeed(rootModels[i]->heuristic_[j]->getSeed() + 100000000 * i); 2712 for (int j = 0; j < numberCutGenerators_; j++) 2713 rootModels[i]->generator_[j]->generator()->refreshSolver(rootModels[i]->solver_); 2714 } 2715 delete basis; 2760 2716 #ifdef CBC_THREAD 2761 if (numberRootThreads==1) {2762 #endif 2763 for (int iModel=0;iModel<numberModels;iModel++) {2764 2765 2766 2767 feasible=false;2768 2769 2770 2717 if (numberRootThreads == 1) { 2718 #endif 2719 for (int iModel = 0; iModel < numberModels; iModel++) { 2720 doRootCbcThread(rootModels[iModel]); 2721 // see if solved at root node 2722 if (rootModels[iModel]->getMaximumNodes()) { 2723 feasible = false; 2724 break; 2725 } 2726 } 2771 2727 #ifdef CBC_THREAD 2772 } else { 2773 Coin_pthread_t * threadId = new Coin_pthread_t [numberRootThreads]; 2774 for (int kModel=0;kModel<numberModels;kModel+=numberRootThreads) { 2775 bool finished=false; 2776 for (int iModel=kModel;iModel<CoinMin(numberModels,kModel+numberRootThreads);iModel++) { 2777 pthread_create(&(threadId[iModel-kModel].thr), NULL, 2778 doRootCbcThread, 2779 rootModels[iModel]); 2780 } 2781 // wait 2782 for (int iModel=kModel;iModel<CoinMin(numberModels,kModel+numberRootThreads);iModel++) { 2783 pthread_join(threadId[iModel-kModel].thr, NULL); 2784 } 2785 // see if solved at root node 2786 for (int iModel=kModel;iModel<CoinMin(numberModels,kModel+numberRootThreads);iModel++) { 2787 if (rootModels[iModel]->getMaximumNodes()) 2788 finished=true; 2789 } 2790 if (finished) { 2791 feasible=false; 2792 break; 2793 } 2794 } 2795 delete [] threadId; 2796 } 2797 #endif 2798 // sort solutions 2799 int * which = new int [numberModels]; 2800 double * value = new double [numberModels]; 2801 int numberSolutions=0; 2802 for (int iModel=0;iModel<numberModels;iModel++) { 2803 if (rootModels[iModel]->bestSolution()) { 2804 which[numberSolutions]=iModel; 2805 value[numberSolutions++]= 2806 -rootModels[iModel]->getMinimizationObjValue(); 2807 } 2808 } 2809 char general[100]; 2810 rootTimeCpu=CoinCpuTime()-rootTimeCpu; 2811 if (numberRootThreads==1) 2812 sprintf(general,"Multiple root solvers took a total of %.2f seconds\n", 2813 rootTimeCpu); 2814 else 2815 sprintf(general,"Multiple root solvers took a total of %.2f seconds (%.2f elapsed)\n", 2816 rootTimeCpu,CoinGetTimeOfDay()-startTimeRoot); 2817 messageHandler()->message(CBC_GENERAL, 2818 messages()) 2819 << general << CoinMessageEol ; 2820 CoinSort_2(value,value+numberSolutions,which); 2821 // to get name 2822 CbcHeuristicRINS dummyHeuristic; 2823 dummyHeuristic.setHeuristicName("Multiple root solvers"); 2824 lastHeuristic_=&dummyHeuristic; 2825 for (int i=0;i<numberSolutions;i++) { 2826 double objValue = - value[i]; 2827 if (objValue<getCutoff()) { 2828 int iModel=which[i]; 2829 setBestSolution(CBC_ROUNDING,objValue, 2830 rootModels[iModel]->bestSolution()); 2831 } 2832 } 2833 lastHeuristic_=NULL; 2834 delete [] which; 2835 delete [] value; 2836 } 2837 // Do heuristics 2838 if (numberObjects_&&!rootModels) 2839 doHeuristicsAtRoot(); 2840 if (solverCharacteristics_->solutionAddsCuts()) { 2841 // With some heuristics solver needs a resolve here 2842 solver_->resolve(); 2843 if(!isProvenOptimal()){ 2844 solver_->initialSolve(); 2845 } 2846 } 2847 /* 2728 } else { 2729 Coin_pthread_t *threadId = new Coin_pthread_t[numberRootThreads]; 2730 for (int kModel = 0; kModel < numberModels; kModel += numberRootThreads) { 2731 bool finished = false; 2732 for (int iModel = kModel; iModel < CoinMin(numberModels, kModel + numberRootThreads); iModel++) { 2733 pthread_create(&(threadId[iModel - kModel].thr), NULL, 2734 doRootCbcThread, 2735 rootModels[iModel]); 2736 } 2737 // wait 2738 for (int iModel = kModel; iModel < CoinMin(numberModels, kModel + numberRootThreads); iModel++) { 2739 pthread_join(threadId[iModel - kModel].thr, NULL); 2740 } 2741 // see if solved at root node 2742 for (int iModel = kModel; iModel < CoinMin(numberModels, kModel + numberRootThreads); iModel++) { 2743 if (rootModels[iModel]->getMaximumNodes()) 2744 finished = true; 2745 } 2746 if (finished) { 2747 feasible = false; 2748 break; 2749 } 2750 } 2751 delete[] threadId; 2752 } 2753 #endif 2754 // sort solutions 2755 int *which = new int[numberModels]; 2756 double *value = new double[numberModels]; 2757 int numberSolutions = 0; 2758 for (int iModel = 0; iModel < numberModels; iModel++) { 2759 if (rootModels[iModel]->bestSolution()) { 2760 which[numberSolutions] = iModel; 2761 value[numberSolutions++] = -rootModels[iModel]->getMinimizationObjValue(); 2762 } 2763 } 2764 char general[100]; 2765 rootTimeCpu = CoinCpuTime() - rootTimeCpu; 2766 if (numberRootThreads == 1) 2767 sprintf(general, "Multiple root solvers took a total of %.2f seconds\n", 2768 rootTimeCpu); 2769 else 2770 sprintf(general, "Multiple root solvers took a total of %.2f seconds (%.2f elapsed)\n", 2771 rootTimeCpu, CoinGetTimeOfDay() - startTimeRoot); 2772 messageHandler()->message(CBC_GENERAL, 2773 messages()) 2774 << general << CoinMessageEol; 2775 CoinSort_2(value, value + numberSolutions, which); 2776 // to get name 2777 CbcHeuristicRINS dummyHeuristic; 2778 dummyHeuristic.setHeuristicName("Multiple root solvers"); 2779 lastHeuristic_ = &dummyHeuristic; 2780 for (int i = 0; i < numberSolutions; i++) { 2781 double objValue = -value[i]; 2782 if (objValue < getCutoff()) { 2783 int iModel = which[i]; 2784 setBestSolution(CBC_ROUNDING, objValue, 2785 rootModels[iModel]->bestSolution()); 2786 } 2787 } 2788 lastHeuristic_ = NULL; 2789 delete[] which; 2790 delete[] value; 2791 } 2792 // Do heuristics 2793 if (numberObjects_ && !rootModels) 2794 doHeuristicsAtRoot(); 2795 if (solverCharacteristics_->solutionAddsCuts()) { 2796 // With some heuristics solver needs a resolve here 2797 solver_->resolve(); 2798 if (!isProvenOptimal()) { 2799 solver_->initialSolve(); 2800 } 2801 } 2802 /* 2848 2803 Grepping through the code, it would appear that this is a command line 2849 2804 debugging hook. There's no obvious place in the code where this is set to … … 2852 2807 User hook, says John. 2853 2808 */ 2854 if (intParam_[CbcMaxNumNode] < 02855 ||numberSolutions_>=getMaximumSolutions())2856 2857 stoppedOnGap_ = false;2858 2859 2860 if(canStopOnGap()) {2861 2862 stoppedOnGap_ = true;2863 2864 2865 2866 2809 if (intParam_[CbcMaxNumNode] < 0 2810 || numberSolutions_ >= getMaximumSolutions()) 2811 eventHappened_ = true; // stop as fast as possible 2812 stoppedOnGap_ = false; 2813 // See if can stop on gap 2814 bestPossibleObjective_ = solver_->getObjValue() * solver_->getObjSense(); 2815 if (canStopOnGap()) { 2816 if (bestPossibleObjective_ < getCutoff()) 2817 stoppedOnGap_ = true; 2818 feasible = false; 2819 //eventHappened_=true; // stop as fast as possible 2820 } 2821 /* 2867 2822 Set up for statistics collection, if requested. Standard values are 2868 2823 documented in CbcModel.hpp. The magic number 100 will trigger a dump of … … 2870 2825 command line debugging hook. 2871 2826 */ 2872 2873 2874 2875 2876 statistics_ = new CbcStatistics *[maximumStatistics_];2877 memset(statistics_, 0, maximumStatistics_*sizeof(CbcStatistics *));2878 2879 2880 if (noObjects && numberIntegers_ < solver_->getNumCols() && (specialOptions_&65536) != 0 && !parentModel_ && false) {2881 int numberIntegers1=0;2882 2883 for (int i=0;i<numberColumns;i++) {2884 2885 2886 2887 2888 2889 int numberIntegers2=0;2890 for (int i=0;i<numberColumns;i++) {2891 2892 2893 2894 if (numberIntegers1<numberIntegers2) {2895 findIntegers(true,2);2896 2897 2898 2899 2900 2827 statistics_ = NULL; 2828 // Do on switch 2829 if (doStatistics > 0 && doStatistics <= 100) { 2830 maximumStatistics_ = 10000; 2831 statistics_ = new CbcStatistics *[maximumStatistics_]; 2832 memset(statistics_, 0, maximumStatistics_ * sizeof(CbcStatistics *)); 2833 } 2834 // See if we can add integers 2835 if (noObjects && numberIntegers_ < solver_->getNumCols() && (specialOptions_ & 65536) != 0 && !parentModel_ && false) { 2836 int numberIntegers1 = 0; 2837 int numberColumns = solver_->getNumCols(); 2838 for (int i = 0; i < numberColumns; i++) { 2839 if (solver_->isInteger(i)) 2840 numberIntegers1++; 2841 } 2842 AddIntegers(); 2843 // make sure in sync 2844 int numberIntegers2 = 0; 2845 for (int i = 0; i < numberColumns; i++) { 2846 if (solver_->isInteger(i)) 2847 numberIntegers2++; 2848 } 2849 if (numberIntegers1 < numberIntegers2) { 2850 findIntegers(true, 2); 2851 convertToDynamic(); 2852 } 2853 } 2854 2855 /* 2901 2856 Do an initial round of cut generation for the root node. Depending on the 2902 2857 type of underlying solver, we may want to do this even if the initial query … … 2913 2868 adjusted accordingly). 2914 2869 */ 2915 int iObject ; 2916 int numberUnsatisfied = 0 ; 2917 delete [] currentSolution_; 2918 currentSolution_ = new double [numberColumns]; 2919 testSolution_ = currentSolution_; 2920 memcpy(currentSolution_, solver_->getColSolution(), 2921 numberColumns*sizeof(double)) ; 2922 // point to useful information 2923 OsiBranchingInformation usefulInfo = usefulInformation(); 2924 2925 for (iObject = 0 ; iObject < numberObjects_ ; iObject++) { 2926 double infeasibility = 2927 object_[iObject]->checkInfeasibility(&usefulInfo) ; 2928 if (infeasibility ) numberUnsatisfied++ ; 2929 } 2930 // replace solverType 2931 double * tightBounds = NULL; 2932 if (solverCharacteristics_->tryCuts()) { 2933 2934 if (numberUnsatisfied) { 2935 // User event 2936 if (!eventHappened_ && feasible) { 2937 if (rootModels) { 2938 // for fixings 2939 int numberColumns=solver_->getNumCols(); 2940 tightBounds = new double [2*numberColumns]; 2941 { 2942 const double * lower = solver_->getColLower(); 2943 const double * upper = solver_->getColUpper(); 2944 for (int i=0;i<numberColumns;i++) { 2945 tightBounds[2*i+0]=lower[i]; 2946 tightBounds[2*i+1]=upper[i]; 2947 } 2948 } 2949 int numberModels = multipleRootTries_%100; 2950 const OsiSolverInterface ** solvers = new 2951 const OsiSolverInterface * [numberModels]; 2952 int numberRows=continuousSolver_->getNumRows(); 2953 int maxCuts=0; 2954 for (int i=0;i<numberModels;i++) { 2955 solvers[i]=rootModels[i]->solver(); 2956 const double * lower = solvers[i]->getColLower(); 2957 const double * upper = solvers[i]->getColUpper(); 2958 for (int j=0;j<numberColumns;j++) { 2959 tightBounds[2*j+0]=CoinMax(lower[j],tightBounds[2*j+0]); 2960 tightBounds[2*j+1]=CoinMin(upper[j],tightBounds[2*j+1]); 2961 } 2962 int numberRows2=solvers[i]->getNumRows(); 2963 assert (numberRows2>=numberRows); 2964 maxCuts += numberRows2-numberRows; 2965 // accumulate statistics 2966 for (int j=0;j<numberCutGenerators_;j++) { 2967 generator_[j]->addStatistics(rootModels[i]->cutGenerator(j)); 2968 } 2969 } 2970 for (int j=0;j<numberCutGenerators_;j++) { 2971 generator_[j]->scaleBackStatistics(numberModels); 2972 } 2973 //CbcRowCuts rowCut(maxCuts); 2974 const OsiRowCutDebugger *debugger = NULL; 2975 if ((specialOptions_&1) != 0) 2976 debugger = solver_->getRowCutDebugger() ; 2977 for (int iModel=0;iModel<numberModels;iModel++) { 2978 int numberRows2=solvers[iModel]->getNumRows(); 2979 const CoinPackedMatrix * rowCopy = solvers[iModel]->getMatrixByRow(); 2980 const int * rowLength = rowCopy->getVectorLengths(); 2981 const double * elements = rowCopy->getElements(); 2982 const int * column = rowCopy->getIndices(); 2983 const CoinBigIndex * rowStart = rowCopy->getVectorStarts(); 2984 const double * rowLower = solvers[iModel]->getRowLower(); 2985 const double * rowUpper = solvers[iModel]->getRowUpper(); 2986 for (int iRow=numberRows;iRow<numberRows2;iRow++) { 2987 OsiRowCut rc; 2988 rc.setLb(rowLower[iRow]); 2989 rc.setUb(rowUpper[iRow]); 2990 CoinBigIndex start = rowStart[iRow]; 2991 rc.setRow(rowLength[iRow],column+start,elements+start,false); 2992 if (debugger) 2993 CoinAssert (!debugger->invalidCut(rc)); 2994 globalCuts_.addCutIfNotDuplicate(rc); 2995 } 2996 //int cutsAdded=globalCuts_.numberCuts()-numberCuts; 2997 //numberCuts += cutsAdded; 2998 //printf("Model %d gave %d cuts (out of %d possible)\n", 2999 // iModel,cutsAdded,numberRows2-numberRows); 3000 } 3001 // normally replace global cuts 3002 //if (!globalCuts_.()) 3003 //globalCuts_=rowCutrowCut.addCuts(globalCuts_); 3004 //rowCut.addCuts(globalCuts_); 3005 int nTightened=0; 3006 assert(feasible); 3007 { 3008 double tolerance=1.0e-5; 3009 const double * lower = solver_->getColLower(); 3010 const double * upper = solver_->getColUpper(); 3011 for (int i=0;i<numberColumns;i++) { 3012 if (tightBounds[2*i+0]>tightBounds[2*i+1]+1.0e-9) { 3013 feasible=false; 3014 char general[200]; 3015 sprintf(general,"Solvers give infeasible bounds on %d %g,%g was %g,%g - search finished\n", 3016 i,tightBounds[2*i+0],tightBounds[2*i+1],lower[i],upper[i]); 3017 messageHandler()->message(CBC_GENERAL,messages()) 3018 << general << CoinMessageEol ; 3019 break; 3020 } 3021 double oldLower=lower[i]; 3022 double oldUpper=upper[i]; 3023 if (tightBounds[2*i+0]>oldLower+tolerance) { 3024 nTightened++; 3025 solver_->setColLower(i,tightBounds[2*i+0]); 3026 } 3027 if (tightBounds[2*i+1]<oldUpper-tolerance) { 3028 nTightened++; 3029 solver_->setColUpper(i,tightBounds[2*i+1]); 3030 } 3031 } 3032 } 3033 delete [] tightBounds; 3034 tightBounds=NULL; 3035 char printBuffer[200]; 3036 sprintf(printBuffer,"%d solvers added %d different cuts out of pool of %d", 3037 numberModels,globalCuts_.sizeRowCuts(),maxCuts); 3038 messageHandler()->message(CBC_GENERAL, messages()) 3039 << printBuffer << CoinMessageEol ; 3040 if (nTightened) { 3041 sprintf(printBuffer,"%d bounds were tightened", 3042 nTightened); 3043 messageHandler()->message(CBC_GENERAL, messages()) 3044 << printBuffer << CoinMessageEol ; 3045 } 3046 delete [] solvers; 3047 } 3048 if (!parentModel_&&(moreSpecialOptions_&67108864) != 0) { 3049 // load cuts from file 3050 FILE * fp = fopen("global.cuts","rb"); 3051 if (fp) { 3052 size_t nRead; 3053 int numberColumns=solver_->getNumCols(); 3054 int numCols; 3055 nRead = fread(&numCols, sizeof(int), 1, fp); 3056 if (nRead != 1) 3057 throw("Error in fread"); 3058 if (numberColumns!=numCols) { 3059 printf("Mismatch on columns %d %d\n",numberColumns,numCols); 3060 fclose(fp); 3061 } else { 3062 // If rootModel just do some 3063 double threshold=-1.0; 3064 if (!multipleRootTries_) 3065 threshold=0.5; 3066 int initialCuts=0; 3067 int initialGlobal = globalCuts_.sizeRowCuts(); 3068 double * elements = new double [numberColumns+2]; 3069 int * indices = new int [numberColumns]; 3070 int numberEntries=1; 3071 while (numberEntries>0) { 3072 nRead = fread(&numberEntries, sizeof(int), 1, fp); 3073 if (nRead != 1) 3074 throw("Error in fread"); 3075 double randomNumber=randomNumberGenerator_.randomDouble(); 3076 if (numberEntries>0) { 3077 initialCuts++; 3078 nRead = fread(elements, sizeof(double), numberEntries+2, fp); 3079 if (nRead != static_cast<size_t>(numberEntries+2)) 3080 throw("Error in fread"); 3081 nRead = fread(indices, sizeof(int), numberEntries, fp); 3082 if (nRead != static_cast<size_t>(numberEntries)) 3083 throw("Error in fread"); 3084 if (randomNumber>threshold) { 3085 OsiRowCut rc; 3086 rc.setLb(elements[numberEntries]); 3087 rc.setUb(elements[numberEntries+1]); 3088 rc.setRow(numberEntries,indices,elements, 3089 false); 3090 rc.setGloballyValidAsInteger(2); 3091 globalCuts_.addCutIfNotDuplicate(rc) ; 3092 } 3093 } 3094 } 3095 fclose(fp); 3096 // fixes 3097 int nTightened=0; 3098 fp = fopen("global.fix","rb"); 3099 if (fp) { 3100 nRead = fread(indices, sizeof(int), 2, fp); 3101 if (nRead != 2) 3102 throw("Error in fread"); 3103 if (numberColumns!=indices[0]) { 3104 printf("Mismatch on columns %d %d\n",numberColumns, 3105 indices[0]); 3106 } else { 3107 indices[0]=1; 3108 while (indices[0]>=0) { 3109 nRead = fread(indices, sizeof(int), 2, fp); 3110 if (nRead != 2) 3111 throw("Error in fread"); 3112 int iColumn=indices[0]; 3113 if (iColumn>=0) { 3114 nTightened++; 3115 nRead = fread(elements, sizeof(double), 4, fp); 3116 if (nRead != 4) 3117 throw("Error in fread"); 3118 solver_->setColLower(iColumn,elements[0]); 3119 solver_->setColUpper(iColumn,elements[1]); 3120 } 3121 } 3122 } 3123 } 3124 if (fp) 3125 fclose(fp); 3126 char printBuffer[200]; 3127 sprintf(printBuffer,"%d cuts read in of which %d were unique, %d bounds tightened", 3128 initialCuts, 3129 globalCuts_.sizeRowCuts()-initialGlobal,nTightened); 3130 messageHandler()->message(CBC_GENERAL, messages()) 3131 << printBuffer << CoinMessageEol ; 3132 delete [] elements; 3133 delete [] indices; 3134 } 3135 } 3136 } 3137 if (feasible) 3138 feasible = solveWithCuts(cuts, maximumCutPassesAtRoot_, 3139 NULL); 3140 if (multipleRootTries_&& 3141 (moreSpecialOptions_&134217728)!=0) { 3142 FILE * fp=NULL; 3143 size_t nRead; 3144 int numberColumns=solver_->getNumCols(); 3145 int initialCuts=0; 3146 if ((moreSpecialOptions_&134217728)!=0) { 3147 // append so go down to end 3148 fp = fopen("global.cuts","r+b"); 3149 if (fp) { 3150 int numCols; 3151 nRead = fread(&numCols, sizeof(int), 1, fp); 3152 if (nRead != 1) 3153 throw("Error in fread"); 3154 if (numberColumns!=numCols) { 3155 printf("Mismatch on columns %d %d\n",numberColumns,numCols); 3156 fclose(fp); 3157 fp=NULL; 3158 } 3159 } 3160 } 3161 double * elements = new double [numberColumns+2]; 3162 int * indices = new int [numberColumns]; 3163 if (fp) { 3164 int numberEntries=1; 3165 while (numberEntries>0) { 3166 fpos_t position; 3167 fgetpos(fp, &position); 3168 nRead = fread(&numberEntries, sizeof(int), 1, fp); 3169 if (nRead != 1) 3170 throw("Error in fread"); 3171 if (numberEntries>0) { 3172 initialCuts++; 3173 nRead = fread(elements, sizeof(double), numberEntries+2, fp); 3174 if (nRead != static_cast<size_t>(numberEntries+2)) 3175 throw("Error in fread"); 3176 nRead = fread(indices, sizeof(int), numberEntries, fp); 3177 if (nRead != static_cast<size_t>(numberEntries)) 3178 throw("Error in fread"); 3179 } else { 3180 // end 3181 fsetpos(fp, &position); 3182 } 3183 } 3184 } else { 3185 fp = fopen("global.cuts","wb"); 3186 size_t nWrite; 3187 nWrite=fwrite(&numberColumns,sizeof(int),1,fp); 3188 if (nWrite != 1) 3189 throw("Error in fwrite"); 3190 } 3191 size_t nWrite; 3192 // now append binding cuts 3193 int numberC=continuousSolver_->getNumRows(); 3194 int numberRows=solver_->getNumRows(); 3195 printf("Saving %d cuts (up from %d)\n", 3196 initialCuts+numberRows-numberC,initialCuts); 3197 const double * rowLower = solver_->getRowLower(); 3198 const double * rowUpper = solver_->getRowUpper(); 3199 // Row copy 3200 CoinPackedMatrix matrixByRow(*solver_->getMatrixByRow()); 3201 const double * elementByRow = matrixByRow.getElements(); 3202 const int * column = matrixByRow.getIndices(); 3203 const CoinBigIndex * rowStart = matrixByRow.getVectorStarts(); 3204 const int * rowLength = matrixByRow.getVectorLengths(); 3205 for (int iRow=numberC;iRow<numberRows;iRow++) { 3206 int n=rowLength[iRow]; 3207 assert (n); 3208 CoinBigIndex start=rowStart[iRow]; 3209 memcpy(elements,elementByRow+start,n*sizeof(double)); 3210 memcpy(indices,column+start,n*sizeof(int)); 3211 elements[n]=rowLower[iRow]; 3212 elements[n+1]=rowUpper[iRow]; 3213 nWrite=fwrite(&n,sizeof(int),1,fp); 3214 if (nWrite != 1) 3215 throw("Error in fwrite"); 3216 nWrite=fwrite(elements,sizeof(double),n+2,fp); 3217 if (nWrite != static_cast<size_t>(n+2)) 3218 throw("Error in fwrite"); 3219 nWrite=fwrite(indices,sizeof(int),n,fp); 3220 if (nWrite != static_cast<size_t>(n)) 3221 throw("Error in fwrite"); 3222 } 3223 // eof marker 3224 int eofMarker=-1; 3225 nWrite=fwrite(&eofMarker,sizeof(int),1,fp); 3226 if (nWrite != 1) 3227 throw("Error in fwrite"); 3228 fclose(fp); 3229 // do tighter bounds (? later extra to original columns) 3230 int nTightened=0; 3231 const double * lower = solver_->getColLower(); 3232 const double * upper = solver_->getColUpper(); 3233 const double * originalLower = continuousSolver_->getColLower(); 3234 const double * originalUpper = continuousSolver_->getColUpper(); 3235 double tolerance=1.0e-5; 3236 for (int i=0;i<numberColumns;i++) { 3237 if (lower[i]>originalLower[i]+tolerance) { 3238 nTightened++; 3239 } 3240 if (upper[i]<originalUpper[i]-tolerance) { 3241 nTightened++; 3242 } 3243 } 3244 if (nTightened) { 3245 fp = fopen("global.fix","wb"); 3246 size_t nWrite; 3247 indices[0]=numberColumns; 3248 if (originalColumns_) 3249 indices[1]=COIN_INT_MAX; 3250 else 3251 indices[1]=-1; 3252 nWrite=fwrite(indices,sizeof(int),2,fp); 3253 if (nWrite != 2) 3254 throw("Error in fwrite"); 3255 for (int i=0;i<numberColumns;i++) { 3256 int nTightened=0; 3257 if (lower[i]>originalLower[i]+tolerance) { 3258 nTightened++; 3259 } 3260 if (upper[i]<originalUpper[i]-tolerance) { 3261 nTightened++; 3262 } 3263 if (nTightened) { 3264 indices[0]=i; 3265 if (originalColumns_) 3266 indices[1]=originalColumns_[i]; 3267 elements[0]=lower[i]; 3268 elements[1]=upper[i]; 3269 elements[2]=originalLower[i]; 3270 elements[3]=originalUpper[i]; 3271 nWrite=fwrite(indices,sizeof(int),2,fp); 3272 if (nWrite != 2) 3273 throw("Error in fwrite"); 3274 nWrite=fwrite(elements,sizeof(double),4,fp); 3275 if (nWrite != 4) 3276 throw("Error in fwrite"); 3277 } 3278 } 3279 // eof marker 3280 indices[0]=-1; 3281 nWrite=fwrite(indices,sizeof(int),2,fp); 3282 if (nWrite != 2) 3283 throw("Error in fwrite"); 3284 fclose(fp); 3285 } 3286 delete [] elements; 3287 delete [] indices; 3288 } 3289 if ((specialOptions_&524288) != 0 && !parentModel_ 3290 && storedRowCuts_) { 3291 if (feasible) { 3292 /* pick up stuff and try again 2870 int iObject; 2871 int numberUnsatisfied = 0; 2872 delete[] currentSolution_; 2873 currentSolution_ = new double[numberColumns]; 2874 testSolution_ = currentSolution_; 2875 memcpy(currentSolution_, solver_->getColSolution(), 2876 numberColumns * sizeof(double)); 2877 // point to useful information 2878 OsiBranchingInformation usefulInfo = usefulInformation(); 2879 2880 for (iObject = 0; iObject < numberObjects_; iObject++) { 2881 double infeasibility = object_[iObject]->checkInfeasibility(&usefulInfo); 2882 if (infeasibility) 2883 numberUnsatisfied++; 2884 } 2885 // replace solverType 2886 double *tightBounds = NULL; 2887 if (solverCharacteristics_->tryCuts()) { 2888 2889 if (numberUnsatisfied) { 2890 // User event 2891 if (!eventHappened_ && feasible) { 2892 if (rootModels) { 2893 // for fixings 2894 int numberColumns = solver_->getNumCols(); 2895 tightBounds = new double[2 * numberColumns]; 2896 { 2897 const double *lower = solver_->getColLower(); 2898 const double *upper = solver_->getColUpper(); 2899 for (int i = 0; i < numberColumns; i++) { 2900 tightBounds[2 * i + 0] = lower[i]; 2901 tightBounds[2 * i + 1] = upper[i]; 2902 } 2903 } 2904 int numberModels = multipleRootTries_ % 100; 2905 const OsiSolverInterface **solvers = new const OsiSolverInterface *[numberModels]; 2906 int numberRows = continuousSolver_->getNumRows(); 2907 int maxCuts = 0; 2908 for (int i = 0; i < numberModels; i++) { 2909 solvers[i] = rootModels[i]->solver(); 2910 const double *lower = solvers[i]->getColLower(); 2911 const double *upper = solvers[i]->getColUpper(); 2912 for (int j = 0; j < numberColumns; j++) { 2913 tightBounds[2 * j + 0] = CoinMax(lower[j], tightBounds[2 * j + 0]); 2914 tightBounds[2 * j + 1] = CoinMin(upper[j], tightBounds[2 * j + 1]); 2915 } 2916 int numberRows2 = solvers[i]->getNumRows(); 2917 assert(numberRows2 >= numberRows); 2918 maxCuts += numberRows2 - numberRows; 2919 // accumulate statistics 2920 for (int j = 0; j < numberCutGenerators_; j++) { 2921 generator_[j]->addStatistics(rootModels[i]->cutGenerator(j)); 2922 } 2923 } 2924 for (int j = 0; j < numberCutGenerators_; j++) { 2925 generator_[j]->scaleBackStatistics(numberModels); 2926 } 2927 //CbcRowCuts rowCut(maxCuts); 2928 const OsiRowCutDebugger *debugger = NULL; 2929 if ((specialOptions_ & 1) != 0) 2930 debugger = solver_->getRowCutDebugger(); 2931 for (int iModel = 0; iModel < numberModels; iModel++) { 2932 int numberRows2 = solvers[iModel]->getNumRows(); 2933 const CoinPackedMatrix *rowCopy = solvers[iModel]->getMatrixByRow(); 2934 const int *rowLength = rowCopy->getVectorLengths(); 2935 const double *elements = rowCopy->getElements(); 2936 const int *column = rowCopy->getIndices(); 2937 const CoinBigIndex *rowStart = rowCopy->getVectorStarts(); 2938 const double *rowLower = solvers[iModel]->getRowLower(); 2939 const double *rowUpper = solvers[iModel]->getRowUpper(); 2940 for (int iRow = numberRows; iRow < numberRows2; iRow++) { 2941 OsiRowCut rc; 2942 rc.setLb(rowLower[iRow]); 2943 rc.setUb(rowUpper[iRow]); 2944 CoinBigIndex start = rowStart[iRow]; 2945 rc.setRow(rowLength[iRow], column + start, elements + start, false); 2946 if (debugger) 2947 CoinAssert(!debugger->invalidCut(rc)); 2948 globalCuts_.addCutIfNotDuplicate(rc); 2949 } 2950 //int cutsAdded=globalCuts_.numberCuts()-numberCuts;