- Timestamp:
- Dec 21, 2009 11:59:56 AM (11 years ago)
- Location:
- branches/sandbox/Cbc/src
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/sandbox/Cbc/src/CbcCutGenerator.hpp
r1314 r1409 340 340 model_ = model; 341 341 } 342 //@}343 344 private:345 /**@name Private gets and sets */346 //@{347 342 /// Whether global cuts at root 348 343 inline bool globalCutsAtRoot() const { … … 363 358 switches_ |= yesNo ? 256 : 0; 364 359 } 360 //@} 361 362 private: 363 /**@name Private gets and sets */ 364 //@{ 365 365 //@} 366 366 /// Saved cuts -
branches/sandbox/Cbc/src/CbcModel.cpp
r1393 r1409 74 74 #include "CbcCompareActual.hpp" 75 75 #include "CbcTree.hpp" 76 #ifdef CBC_THREAD 77 #include <pthread.h> 78 #ifdef HAVE_CLOCK_GETTIME 79 inline int my_gettime(struct timespec* tp) 80 { 81 return clock_gettime(CLOCK_REALTIME, tp); 82 } 83 #else 84 #ifndef _MSC_VER 85 inline int my_gettime(struct timespec* tp) 86 { 87 struct timeval tv; 88 int ret = gettimeofday(&tv, NULL); 89 tp->tv_sec = tv.tv_sec; 90 tp->tv_nsec = tv.tv_usec * 1000; 91 return ret; 92 } 93 #else 94 inline int my_gettime(struct timespec* tp) 95 { 96 double t = CoinGetTimeOfDay(); 97 tp->tv_sec = (int)floor(t); 98 tp->tv_nsec = (int)((tp->tv_sec - floor(t)) / 1000000.0); 99 return 0; 100 } 101 #endif 102 #endif 103 104 struct Coin_pthread_t { 105 pthread_t thr; 106 long status; 107 }; 108 109 // To Pass across to doOneNode 110 typedef struct { 111 CbcModel * baseModel; 112 CbcModel * thisModel; 113 CbcNode * node; // filled in every time 114 CbcNode * createdNode; // filled in every time on return 115 Coin_pthread_t threadIdOfBase; 116 pthread_mutex_t * mutex; // for locking data 117 pthread_mutex_t * mutex2; // for waking up threads 118 pthread_cond_t * condition2; // for waking up thread 119 int returnCode; // -1 available, 0 busy, 1 finished , 2?? 120 double timeLocked; 121 double timeWaitingToLock; 122 double timeWaitingToStart; 123 double timeInThread; 124 int numberTimesLocked; 125 int numberTimesUnlocked; 126 int numberTimesWaitingToStart; 127 int saveStuff[2]; 128 int dantzigState; // 0 unset, -1 waiting to be set, 1 set 129 struct timespec absTime; 130 bool locked; 131 int nDeleteNode; 132 CbcNode ** delNode; 133 int maxDeleteNode; 134 int nodesThisTime; 135 int iterationsThisTime; 136 } threadStruct; 137 static void * doNodesThread(void * voidInfo); 138 static void * doCutsThread(void * voidInfo); 139 static void * doHeurThread(void * voidInfo); 140 #endif 76 // This may be dummy 77 #include "CbcThread.hpp" 141 78 /* Various functions local to CbcModel.cpp */ 142 79 … … 610 547 } 611 548 #endif 612 /*613 Generate a random objective function for problems where the given objective614 function is not terribly useful. (Nearly feasible, single integer variable,615 that sort of thing.616 */549 /* 550 Generate a random objective function for problems where the given objective 551 function is not terribly useful. (Nearly feasible, single integer variable, 552 that sort of thing. 553 */ 617 554 CoinDrand48(true, 1234567); 618 555 for (int i = 0; i < numberColumns; i++) { … … 1022 959 int numberColumns = getNumCols() ; 1023 960 double scaleFactor = 1.0; // due to rhs etc 1024 /*1025 Original model did not have integer bounds.1026 */961 /* 962 Original model did not have integer bounds. 963 */ 1027 964 if ((specialOptions_&65536) == 0) { 1028 965 /* be on safe side (later look carefully as may be able to … … 1187 1124 } 1188 1125 #ifdef COIN_DEVELOP 1189 /*1190 We're debugging. (specialOptions 1)1191 */1126 /* 1127 We're debugging. (specialOptions 1) 1128 */ 1192 1129 if ((specialOptions_&1) != 0) { 1193 1130 const OsiRowCutDebugger *debugger = saveSolver->getRowCutDebugger() ; … … 1667 1604 bool noObjects = (numberObjects_ == 0); 1668 1605 // Set up strategies 1669 /*1670 See if the user has supplied a strategy object and deal with it if present.1671 The call to setupOther will set numberStrong_ and numberBeforeTrust_, and1672 perform integer preprocessing, if requested.1673 1674 We need to hang on to a pointer to solver_. setupOther will assign a1675 preprocessed solver to model, but will instruct assignSolver not to trash the1676 existing one.1677 */1606 /* 1607 See if the user has supplied a strategy object and deal with it if present. 1608 The call to setupOther will set numberStrong_ and numberBeforeTrust_, and 1609 perform integer preprocessing, if requested. 1610 1611 We need to hang on to a pointer to solver_. setupOther will assign a 1612 preprocessed solver to model, but will instruct assignSolver not to trash the 1613 existing one. 1614 */ 1678 1615 if (strategy_) { 1679 1616 // May do preprocessing … … 1704 1641 if (debugger) 1705 1642 debugger->redoSolution(numberColumns, originalColumns); 1706 1643 // User-provided solution might have been best. Synchronise. 1707 1644 if (bestSolution_) { 1708 1645 // need to redo - in case no better found in BAB … … 2047 1984 return ; 2048 1985 } 2049 /*2050 See if we're using the Osi side of the branching hierarchy. If so, either2051 convert existing CbcObjects to OsiObjects, or generate them fresh. In the2052 first case, CbcModel owns the objects on the object_ list. In the second2053 case, the solver holds the objects and object_ simply points to the2054 solver's list.2055 2056 080417 The conversion code here (the block protected by `if (obj)') cannot2057 possibly be correct. On the Osi side, descent is OsiObject -> OsiObject2 ->2058 all other Osi object classes. On the Cbc side, it's OsiObject -> CbcObject2059 -> all other Cbc object classes. It's structurally impossible for any Osi2060 object to descend from CbcObject. The only thing I can see is that this is2061 really dead code, and object detection is now handled from the Osi side.2062 */1986 /* 1987 See if we're using the Osi side of the branching hierarchy. If so, either 1988 convert existing CbcObjects to OsiObjects, or generate them fresh. In the 1989 first case, CbcModel owns the objects on the object_ list. In the second 1990 case, the solver holds the objects and object_ simply points to the 1991 solver's list. 1992 1993 080417 The conversion code here (the block protected by `if (obj)') cannot 1994 possibly be correct. On the Osi side, descent is OsiObject -> OsiObject2 -> 1995 all other Osi object classes. On the Cbc side, it's OsiObject -> CbcObject 1996 -> all other Cbc object classes. It's structurally impossible for any Osi 1997 object to descend from CbcObject. The only thing I can see is that this is 1998 really dead code, and object detection is now handled from the Osi side. 1999 */ 2063 2000 // Convert to Osi if wanted 2064 2001 bool useOsiBranching = false; … … 2109 2046 //} 2110 2047 } else { 2111 /*2112 As of 080104, findIntegersAndSOS is misleading --- the default OSI2113 implementation finds only integers.2114 */2048 /* 2049 As of 080104, findIntegersAndSOS is misleading --- the default OSI 2050 implementation finds only integers. 2051 */ 2115 2052 // do from solver 2116 2053 deleteObjects(false); … … 2309 2246 double * upperBefore = new double [numberColumns] ; 2310 2247 /* 2311 Set up to run heuristics and generate cuts at the root node. The heavy2312 lifting is hidden inside the calls to doHeuristicsAtRoot and solveWithCuts.2313 2314 To start, tell cut generators they can be a bit more aggressive at the2315 root node.2316 2317 QUESTION: phase_ = 0 is documented as `initial solve', phase = 1 as `solve2318 2319 2320 2248 Set up to run heuristics and generate cuts at the root node. The heavy 2249 lifting is hidden inside the calls to doHeuristicsAtRoot and solveWithCuts. 2250 2251 To start, tell cut generators they can be a bit more aggressive at the 2252 root node. 2253 2254 QUESTION: phase_ = 0 is documented as `initial solve', phase = 1 as `solve 2255 with cuts at root'. Is phase_ = 1 the correct indication when 2256 doHeurisiticsAtRoot is called to run heuristics outside of the main 2257 cut / heurisitc / reoptimise loop in solveWithCuts? 2321 2258 2322 2259 Generate cuts at the root node and reoptimise. solveWithCuts does the heavy … … 2338 2275 int iCutGenerator; 2339 2276 for (iCutGenerator = 0; iCutGenerator < numberCutGenerators_; iCutGenerator++) { 2277 // If parallel switch off global cuts 2278 if (numberThreads_) { 2279 generator_[iCutGenerator]->setGlobalCuts(false); 2280 generator_[iCutGenerator]->setGlobalCutsAtRoot(false); 2281 } 2340 2282 CglCutGenerator * generator = generator_[iCutGenerator]->generator(); 2341 2283 generator->setAggressiveness(generator->getAggressiveness() + 100); … … 2366 2308 // tighten and set best solution 2367 2309 // A) tight bounds on integer variables 2368 2369 2370 2371 2310 /* 2311 storedRowCuts_ are coming in from outside, probably for nonlinear. 2312 John was unsure about origin. 2313 */ 2372 2314 const double * lower = solver_->getColLower(); 2373 2315 const double * upper = solver_->getColUpper(); … … 2405 2347 } 2406 2348 } 2407 /*2408 Run heuristics at the root. This is the only opportunity to run FPump; it2409 will be removed from the heuristics list by doHeuristicsAtRoot.2410 */2349 /* 2350 Run heuristics at the root. This is the only opportunity to run FPump; it 2351 will be removed from the heuristics list by doHeuristicsAtRoot. 2352 */ 2411 2353 // Do heuristics 2412 2354 doHeuristicsAtRoot(); 2413 /*2414 Grepping through the code, it would appear that this is a command line2415 debugging hook. There's no obvious place in the code where this is set to2416 a negative value.2417 2418 User hook, says John.2419 */2355 /* 2356 Grepping through the code, it would appear that this is a command line 2357 debugging hook. There's no obvious place in the code where this is set to 2358 a negative value. 2359 2360 User hook, says John. 2361 */ 2420 2362 if ( intParam_[CbcMaxNumNode] < 0) 2421 2363 eventHappened_ = true; // stop as fast as possible … … 2432 2374 //eventHappened_=true; // stop as fast as possible 2433 2375 } 2434 /*2435 Set up for statistics collection, if requested. Standard values are2436 documented in CbcModel.hpp. The magic number 100 will trigger a dump of2437 CbcSimpleIntegerDynamicPseudoCost objects (no others). Looks like another2438 command line debugging hook.2439 */2376 /* 2377 Set up for statistics collection, if requested. Standard values are 2378 documented in CbcModel.hpp. The magic number 100 will trigger a dump of 2379 CbcSimpleIntegerDynamicPseudoCost objects (no others). Looks like another 2380 command line debugging hook. 2381 */ 2440 2382 statistics_ = NULL; 2441 2383 // Do on switch … … 2448 2390 if (noObjects && numberIntegers_ < solver_->getNumCols() && (specialOptions_&65536) != 0 && !parentModel_) 2449 2391 AddIntegers(); 2450 /*2451 Do an initial round of cut generation for the root node. Depending on the2452 type of underlying solver, we may want to do this even if the initial query2453 to the objects indicates they're satisfied.2454 2455 solveWithCuts does the heavy lifting. It will iterate a generate/reoptimise2456 loop (including reduced cost fixing) until no cuts are generated, the2457 change in objective falls off, or the limit on the number of rounds of cut2458 generation is exceeded.2459 2460 At the end of all this, any cuts will be recorded in cuts and also2461 installed in the solver's constraint system. We'll have reoptimised, and2462 removed any slack cuts (numberOldActiveCuts_ and numberNewCuts_ have been2463 adjusted accordingly).2464 */2392 /* 2393 Do an initial round of cut generation for the root node. Depending on the 2394 type of underlying solver, we may want to do this even if the initial query 2395 to the objects indicates they're satisfied. 2396 2397 solveWithCuts does the heavy lifting. It will iterate a generate/reoptimise 2398 loop (including reduced cost fixing) until no cuts are generated, the 2399 change in objective falls off, or the limit on the number of rounds of cut 2400 generation is exceeded. 2401 2402 At the end of all this, any cuts will be recorded in cuts and also 2403 installed in the solver's constraint system. We'll have reoptimised, and 2404 removed any slack cuts (numberOldActiveCuts_ and numberNewCuts_ have been 2405 adjusted accordingly). 2406 */ 2465 2407 int iObject ; 2466 2408 int preferredWay ; … … 2601 2543 feasible = false; 2602 2544 #if defined(COIN_HAS_CLP)&&defined(COIN_HAS_CPX) 2603 /*2604 This is the notion of using Cbc stuff to get going, then calling cplex to2605 finish off.2606 */2545 /* 2546 This is the notion of using Cbc stuff to get going, then calling cplex to 2547 finish off. 2548 */ 2607 2549 if (feasible && (specialOptions_&16384) != 0 && fastNodeDepth_ == -2 && !parentModel_) { 2608 2550 // Use Cplex to do search! … … 2718 2660 } 2719 2661 #endif 2720 /*2721 A hook to use clp to quickly explore some part of the tree.2722 */2662 /* 2663 A hook to use clp to quickly explore some part of the tree. 2664 */ 2723 2665 if (fastNodeDepth_ == 1000 &&/*!parentModel_*/(specialOptions_&2048) == 0) { 2724 2666 fastNodeDepth_ = -1; … … 3163 3105 CglTreeProbingInfo info(*probingInfo_); 3164 3106 #ifdef JJF_ZERO 3165 /*3166 Marginal idea. Further exploration probably good. Build some extra3167 cliques from probing info. Not quite worth the effort?3168 */3107 /* 3108 Marginal idea. Further exploration probably good. Build some extra 3109 cliques from probing info. Not quite worth the effort? 3110 */ 3169 3111 OsiSolverInterface * fake = info.analyze(*solver_, 1); 3170 3112 if (fake) { … … 3182 3124 printf("%d implications on %d 0-1\n", toZero[number01], number01); 3183 3125 #endif 3184 3126 // Create a cut generator that remembers implications discovered at root. 3185 3127 CglImplication implication(probingInfo_); 3186 3128 addCutGenerator(&implication, 1, "ImplicationCuts", true, false, false, -200); … … 3310 3252 CbcNode * createdNode = NULL; 3311 3253 #ifdef CBC_THREAD 3312 CbcModel ** threadModel = NULL; 3313 Coin_pthread_t * threadId = NULL; 3314 int * threadCount = NULL; 3315 pthread_mutex_t mutex; 3316 pthread_cond_t condition_main; 3317 pthread_mutex_t condition_mutex; 3318 pthread_mutex_t * mutex2 = NULL; 3319 pthread_cond_t * condition2 = NULL; 3320 threadStruct * threadInfo = NULL; 3321 bool locked = false; 3322 int threadStats[6]; 3323 int defaultParallelIterations = 400; 3324 int defaultParallelNodes = 2; 3325 memset(threadStats, 0, sizeof(threadStats)); 3326 double timeWaiting = 0.0; 3327 // For now just one model 3328 if (numberThreads_) { 3254 if ((specialOptions_&2048) != 0) 3255 numberThreads_ = 0; 3256 if (numberThreads_ ) { 3329 3257 nodeCompare_->sayThreaded(); // need to use addresses 3330 threadId = new Coin_pthread_t [numberThreads_]; 3331 threadCount = new int [numberThreads_]; 3332 CoinZeroN(threadCount, numberThreads_); 3333 pthread_mutex_init(&mutex, NULL); 3334 pthread_cond_init(&condition_main, NULL); 3335 pthread_mutex_init(&condition_mutex, NULL); 3336 threadModel = new CbcModel * [numberThreads_+1]; 3337 threadInfo = new threadStruct [numberThreads_+1]; 3338 mutex2 = new pthread_mutex_t [numberThreads_]; 3339 condition2 = new pthread_cond_t [numberThreads_]; 3340 if (parallelMode() < -1) { 3341 // May need for deterministic 3342 saveObjects = new OsiObject * [numberObjects_]; 3343 for (int i = 0; i < numberObjects_; i++) { 3344 saveObjects[i] = object_[i]->clone(); 3345 } 3346 } 3347 // we don't want a strategy object 3348 CbcStrategy * saveStrategy = strategy_; 3349 strategy_ = NULL; 3350 for (int i = 0; i < numberThreads_; i++) { 3351 pthread_mutex_init(mutex2 + i, NULL); 3352 pthread_cond_init(condition2 + i, NULL); 3353 threadId[i].status = 0; 3354 threadInfo[i].baseModel = this; 3355 threadModel[i] = new CbcModel(*this, true); 3356 threadModel[i]->synchronizeHandlers(1); 3357 #ifdef COIN_HAS_CLP 3358 // Solver may need to know about model 3359 CbcModel * thisModel = threadModel[i]; 3360 CbcOsiSolver * solver = 3361 dynamic_cast<CbcOsiSolver *>(thisModel->solver()) ; 3362 if (solver) 3363 solver->setCbcModel(thisModel); 3364 #endif 3365 mutex_ = reinterpret_cast<void *> (threadInfo + i); 3366 threadModel[i]->moveToModel(this, -1); 3367 threadInfo[i].thisModel = threadModel[i]; 3368 threadInfo[i].node = NULL; 3369 threadInfo[i].createdNode = NULL; 3370 threadInfo[i].threadIdOfBase.thr = pthread_self(); 3371 threadInfo[i].mutex = &mutex; 3372 threadInfo[i].mutex2 = mutex2 + i; 3373 threadInfo[i].condition2 = condition2 + i; 3374 threadInfo[i].returnCode = -1; 3375 threadInfo[i].timeLocked = 0.0; 3376 threadInfo[i].timeWaitingToLock = 0.0; 3377 threadInfo[i].timeWaitingToStart = 0.0; 3378 threadInfo[i].timeInThread = 0.0; 3379 threadInfo[i].numberTimesLocked = 0; 3380 threadInfo[i].numberTimesUnlocked = 0; 3381 threadInfo[i].numberTimesWaitingToStart = 0; 3382 threadInfo[i].dantzigState = 0; // 0 unset, -1 waiting to be set, 1 set 3383 threadInfo[i].locked = false; 3384 threadInfo[i].delNode = NULL; 3385 threadInfo[i].maxDeleteNode = 0; 3386 threadInfo[i].nDeleteNode = 0; 3387 threadInfo[i].nodesThisTime = 0; 3388 threadInfo[i].iterationsThisTime = 0; 3389 pthread_create(&(threadId[i].thr), NULL, doNodesThread, threadInfo + i); 3390 threadId[i].status = 1; 3391 } 3392 strategy_ = saveStrategy; 3393 // Do a partial one for base model 3394 threadInfo[numberThreads_].baseModel = this; 3395 threadModel[numberThreads_] = this; 3396 mutex_ = reinterpret_cast<void *> (threadInfo + numberThreads_); 3397 threadInfo[numberThreads_].node = NULL; 3398 threadInfo[numberThreads_].mutex = &mutex; 3399 threadInfo[numberThreads_].condition2 = &condition_main; 3400 threadInfo[numberThreads_].mutex2 = &condition_mutex; 3401 threadInfo[numberThreads_].timeLocked = 0.0; 3402 threadInfo[numberThreads_].timeWaitingToLock = 0.0; 3403 threadInfo[numberThreads_].numberTimesLocked = 0; 3404 threadInfo[numberThreads_].numberTimesUnlocked = 0; 3405 threadInfo[numberThreads_].locked = false; 3258 master_ = new CbcBaseModel(*this, 3259 (parallelMode() < -1) ? 1 : 0); 3260 masterThread_ = master_->masterThread(); 3406 3261 } 3407 3262 #endif … … 3466 3321 int numberConsecutiveInfeasible = 0; 3467 3322 while (true) { 3468 #ifdef CBC_THREAD 3469 if (parallelMode() > 0 && !locked) { 3470 lockThread(); 3471 locked = true; 3472 } 3473 #endif 3323 lockThread(); 3474 3324 #ifdef COIN_HAS_CLP 3475 // Possible change of pivot method 3476 if (!savePivotMethod && !parentModel_) { 3477 OsiClpSolverInterface * clpSolver 3478 = dynamic_cast<OsiClpSolverInterface *> (solver_); 3479 if (clpSolver && numberNodes_ >= 100 && numberNodes_ < 200) { 3480 if (numberIterations_ < (numberSolves_ + numberNodes_)*10) { 3481 //if (numberIterations_<numberNodes_*20) { 3482 ClpSimplex * simplex = clpSolver->getModelPtr(); 3483 ClpDualRowPivot * pivotMethod = simplex->dualRowPivot(); 3484 ClpDualRowDantzig * pivot = 3485 dynamic_cast< ClpDualRowDantzig*>(pivotMethod); 3486 if (!pivot) { 3487 savePivotMethod = pivotMethod->clone(true); 3488 ClpDualRowDantzig dantzig; 3489 simplex->setDualRowPivotAlgorithm(dantzig); 3490 #ifdef COIN_DEVELOP 3491 printf("%d node, %d iterations ->Dantzig\n", numberNodes_, 3492 numberIterations_); 3493 #endif 3494 #ifdef CBC_THREAD 3495 for (int i = 0; i < numberThreads_; i++) { 3496 threadInfo[i].dantzigState = -1; 3497 } 3498 #endif 3499 } 3500 } 3501 } 3502 } 3325 // See if we want dantzig row choice 3326 goToDantzig(100, savePivotMethod); 3503 3327 #endif 3504 3328 if (tree_->empty()) { 3505 3329 #ifdef CBC_THREAD 3506 3330 if (parallelMode() > 0) { 3507 #ifdef COIN_DEVELOP 3508 printf("empty\n"); 3509 #endif 3510 // may still be outstanding nodes 3511 int iThread; 3512 for (iThread = 0; iThread < numberThreads_; iThread++) { 3513 if (threadId[iThread].status) { 3514 if (threadInfo[iThread].returnCode == 0) 3515 break; 3516 } 3517 } 3518 if (iThread < numberThreads_) { 3519 #ifdef COIN_DEVELOP 3520 printf("waiting for thread %d code 0\n", iThread); 3521 #endif 3522 if (parallelMode() > 0) { 3523 unlockThread(); 3524 locked = false; 3525 } 3526 pthread_cond_signal(threadInfo[iThread].condition2); // unlock in case 3527 while (true) { 3528 pthread_mutex_lock(&condition_mutex); 3529 struct timespec absTime; 3530 my_gettime(&absTime); 3531 double time = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 3532 absTime.tv_nsec += 1000000; // millisecond 3533 if (absTime.tv_nsec >= 1000000000) { 3534 absTime.tv_nsec -= 1000000000; 3535 absTime.tv_sec++; 3536 } 3537 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime); 3538 my_gettime(&absTime); 3539 double time2 = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 3540 timeWaiting += time2 - time; 3541 pthread_mutex_unlock(&condition_mutex); 3542 if (threadInfo[iThread].returnCode != 0) 3543 break; 3544 pthread_cond_signal(threadInfo[iThread].condition2); // unlock 3545 } 3546 threadModel[iThread]->moveToModel(this, 1); 3547 assert (threadInfo[iThread].returnCode == 1); 3548 if (threadInfo[iThread].dantzigState == -1) { 3549 // 0 unset, -1 waiting to be set, 1 set 3550 threadInfo[iThread].dantzigState = 1; 3551 CbcModel * model = threadInfo[iThread].thisModel; 3552 OsiClpSolverInterface * clpSolver2 3553 = dynamic_cast<OsiClpSolverInterface *> (model->solver()); 3554 assert (clpSolver2); 3555 ClpSimplex * simplex2 = clpSolver2->getModelPtr(); 3556 ClpDualRowDantzig dantzig; 3557 simplex2->setDualRowPivotAlgorithm(dantzig); 3558 } 3559 // say available 3560 threadInfo[iThread].returnCode = -1; 3561 threadStats[4]++; 3562 #ifdef COIN_DEVELOP 3563 printf("thread %d code now -1\n", iThread); 3564 #endif 3565 continue; 3566 } else { 3567 #ifdef COIN_DEVELOP 3568 printf("no threads at code 0 \n"); 3569 #endif 3570 // now check if any have just finished 3571 for (iThread = 0; iThread < numberThreads_; iThread++) { 3572 if (threadId[iThread].status) { 3573 if (threadInfo[iThread].returnCode == 1) 3574 break; 3575 } 3576 } 3577 if (iThread < numberThreads_) { 3578 if (parallelMode() > 0) { 3579 unlockThread(); 3580 locked = false; 3581 } 3582 threadModel[iThread]->moveToModel(this, 1); 3583 assert (threadInfo[iThread].returnCode == 1); 3584 // say available 3585 threadInfo[iThread].returnCode = -1; 3586 threadStats[4]++; 3587 #ifdef COIN_DEVELOP 3588 printf("thread %d code now -1\n", iThread); 3589 #endif 3590 continue; 3591 } 3592 } 3593 if (!tree_->empty()) { 3594 #ifdef COIN_DEVELOP 3595 printf("tree not empty!!!!!!\n"); 3596 #endif 3597 continue; 3598 } 3599 for (iThread = 0; iThread < numberThreads_; iThread++) { 3600 if (threadId[iThread].status) { 3601 if (threadInfo[iThread].returnCode != -1) { 3602 printf("bad end of tree\n"); 3603 abort(); 3604 } 3605 } 3606 } 3607 #ifdef COIN_DEVELOP 3608 printf("finished ************\n"); 3609 #endif 3610 unlockThread(); 3611 locked = false; // not needed as break 3612 } 3613 #endif 3331 int anyLeft = master_->waitForThreadsInTree(0); 3332 if (!anyLeft) 3333 break; 3334 } else { 3335 break; 3336 } 3337 #else 3614 3338 break; 3615 } 3616 #ifdef CBC_THREAD 3617 if (parallelMode() > 0) { 3339 #endif 3340 } else { 3618 3341 unlockThread(); 3619 locked = false; 3620 } 3621 #endif 3342 } 3622 3343 // If done 100 nodes see if worth trying reduction 3623 3344 if (numberNodes_ == 50 || numberNodes_ == 100) { … … 3647 3368 } 3648 3369 #endif 3649 /*3650 Decide if we want to do a restart.3651 */3370 /* 3371 Decide if we want to do a restart. 3372 */ 3652 3373 if (saveSolver) { 3653 3374 bool tryNewSearch = solverCharacteristics_->reducedCostsAccurate() && … … 3748 3469 double * newSolution = new double[numberColumns]; 3749 3470 double objectiveValue = checkCutoffForRestart; 3750 3471 // Save the best solution so far. 3751 3472 CbcSerendipity heuristic(*this); 3752 3473 if (bestSolution_) 3753 3474 heuristic.setInputSolution(bestSolution_, bestObjective_); 3754 3475 // Magic number 3755 3476 heuristic.setFractionSmall(0.8); 3756 3477 // `pumpTune' to stand-alone solver for explanations. 3757 3478 heuristic.setFeasibilityPumpOptions(1008013); 3758 3479 // Use numberNodes to say how many are original rows … … 3774 3495 delete [] newSolution; 3775 3496 } else { 3776 3497 // 1 for sol'n, 2 for finished, 3 for both 3777 3498 if ((returnCode&1) != 0) { 3778 3499 // increment number of solutions so other heuristics can test … … 3819 3540 CbcCompareDefault * compare = dynamic_cast<CbcCompareDefault *> 3820 3541 (nodeCompare_); 3821 3542 // Don't interfere if user has replaced the compare function. 3822 3543 if (compare) { 3823 3544 //printf("Redoing tree\n"); … … 3828 3549 } 3829 3550 } 3830 3551 // replace current cutoff? 3831 3552 if (cutoff > getCutoff()) { 3832 3553 double newCutoff = getCutoff(); … … 3862 3583 newCutoff = getCutoff(); 3863 3584 } 3864 if (parallelMode() > 0) 3865 lockThread(); 3585 lockThread(); 3866 3586 // Do from deepest (clean tree w.r.t. new solution) 3867 3587 tree_->cleanTree(this, newCutoff, bestPossibleObjective_) ; … … 3869 3589 nodeCompare_->newSolution(this, continuousObjective_, 3870 3590 continuousInfeasibilities_) ; 3871 3591 // side effect: redo heap 3872 3592 tree_->setComparison(*nodeCompare_) ; 3873 3593 if (tree_->empty()) { 3874 if (parallelMode() > 0)3875 unlockThread();3876 // For threads we need to check further3877 //break; // finished3878 3594 continue; 3879 3595 } 3880 if (parallelMode() > 0) 3881 unlockThread(); 3596 unlockThread(); 3882 3597 } 3883 3598 cutoff = getCutoff() ; … … 3889 3604 */ 3890 3605 if (numberNodes_ >= lastEvery1000) { 3891 if (parallelMode() > 0) 3892 lockThread(); 3606 lockThread(); 3893 3607 #ifdef COIN_HAS_CLP 3894 // Possible change of pivot method 3895 if (!savePivotMethod && !parentModel_) { 3896 OsiClpSolverInterface * clpSolver 3897 = dynamic_cast<OsiClpSolverInterface *> (solver_); 3898 if (clpSolver && numberNodes_ >= 1000 && numberNodes_ < 2000) { 3899 if (numberIterations_ < (numberSolves_ + numberNodes_)*10) { 3900 //if (numberIterations_<numberNodes_*20) { 3901 ClpSimplex * simplex = clpSolver->getModelPtr(); 3902 ClpDualRowPivot * pivotMethod = simplex->dualRowPivot(); 3903 ClpDualRowDantzig * pivot = 3904 dynamic_cast< ClpDualRowDantzig*>(pivotMethod); 3905 if (!pivot) { 3906 savePivotMethod = pivotMethod->clone(true); 3907 ClpDualRowDantzig dantzig; 3908 simplex->setDualRowPivotAlgorithm(dantzig); 3909 #ifdef COIN_DEVELOP 3910 printf("%d node, %d iterations ->Dantzig\n", numberNodes_, 3911 numberIterations_); 3912 #endif 3913 #ifdef CBC_THREAD 3914 for (int i = 0; i < numberThreads_; i++) { 3915 threadInfo[i].dantzigState = -1; 3916 } 3917 #endif 3918 } 3919 } 3920 } 3921 } 3608 // See if we want dantzig row choice 3609 goToDantzig(1000, savePivotMethod); 3922 3610 #endif 3923 3611 lastEvery1000 = numberNodes_ + 1000; … … 3929 3617 if (redoTree) 3930 3618 tree_->setComparison(*nodeCompare_) ; 3931 if (parallelMode() > 0) 3932 unlockThread(); 3933 } 3934 // Had hotstart before, now switched off 3619 unlockThread(); 3620 } 3621 // Had hotstart before, now switched off 3935 3622 if (saveCompare && !hotstartSolution_) { 3936 3623 // hotstart switched off … … 3939 3626 saveCompare = NULL; 3940 3627 // redo tree 3941 if (parallelMode() > 0) 3942 lockThread(); 3628 lockThread(); 3943 3629 tree_->setComparison(*nodeCompare_) ; 3944 if (parallelMode() > 0) 3945 unlockThread(); 3630 unlockThread(); 3946 3631 } 3947 3632 if (numberNodes_ >= lastPrintEvery) { 3948 3633 lastPrintEvery = numberNodes_ + printFrequency_; 3949 if (parallelMode() > 0) 3950 lockThread(); 3634 lockThread(); 3951 3635 int nNodes = tree_->size() ; 3952 3636 3953 3637 //MODIF PIERRE 3954 3638 bestPossibleObjective_ = tree_->getBestPossibleObjective(); 3955 if (parallelMode() > 0) 3956 unlockThread(); 3639 unlockThread(); 3957 3640 #ifdef CLP_INVESTIGATE 3958 3641 if (getCutoff() < 1.0e20) { … … 4019 3702 node = tree_->bestNode(cutoff) ; 4020 3703 // Possible one on tree worse than cutoff 4021 3704 // Wierd comparison function can leave ineligible nodes on tree 4022 3705 if (!node || node->objectiveValue() > cutoff) 4023 3706 continue; … … 4048 3731 #ifdef CBC_THREAD 4049 3732 } else if (parallelMode() > 0) { 4050 node = tree_->bestNode(cutoff);4051 // Possible one on tree worse than cutoff4052 if ( !node || node->objectiveValue() > cutoff)3733 int anyLeft = master_->waitForThreadsInTree(1); 3734 // may need to go round again 3735 if (anyLeft) 4053 3736 continue; 4054 threadStats[0]++;4055 //need to think4056 int iThread;4057 // Start one off if any available4058 for (iThread = 0; iThread < numberThreads_; iThread++) {4059 if (threadInfo[iThread].returnCode == -1)4060 break;4061 }4062 if (iThread < numberThreads_) {4063 threadInfo[iThread].node = node;4064 assert (threadInfo[iThread].returnCode == -1);4065 // say in use4066 threadModel[iThread]->moveToModel(this, 0);4067 // This has to be AFTER moveToModel4068 threadInfo[iThread].returnCode = 0;4069 pthread_cond_signal(threadInfo[iThread].condition2); // unlock4070 threadCount[iThread]++;4071 }4072 lockThread();4073 locked = true;4074 // see if any finished4075 for (iThread = 0; iThread < numberThreads_; iThread++) {4076 if (threadInfo[iThread].returnCode > 0)4077 break;4078 }4079 unlockThread();4080 locked = false;4081 if (iThread < numberThreads_) {4082 threadModel[iThread]->moveToModel(this, 1);4083 assert (threadInfo[iThread].returnCode == 1);4084 // say available4085 threadInfo[iThread].returnCode = -1;4086 // carry on4087 threadStats[3]++;4088 } else {4089 // Start one off if any available4090 for (iThread = 0; iThread < numberThreads_; iThread++) {4091 if (threadInfo[iThread].returnCode == -1)4092 break;4093 }4094 if (iThread < numberThreads_) {4095 lockThread();4096 locked = true;4097 // If any on tree get4098 if (!tree_->empty()) {4099 //node = tree_->bestNode(cutoff) ;4100 //assert (node);4101 threadStats[1]++;4102 continue; // ** get another node4103 }4104 unlockThread();4105 locked = false;4106 }4107 // wait (for debug could sleep and use test)4108 bool finished = false;4109 while (!finished) {4110 pthread_mutex_lock(&condition_mutex);4111 struct timespec absTime;4112 my_gettime(&absTime);4113 double time = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec;4114 absTime.tv_nsec += 1000000; // millisecond4115 if (absTime.tv_nsec >= 1000000000) {4116 absTime.tv_nsec -= 1000000000;4117 absTime.tv_sec++;4118 }4119 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime);4120 my_gettime(&absTime);4121 double time2 = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec;4122 timeWaiting += time2 - time;4123 pthread_mutex_unlock(&condition_mutex);4124 for (iThread = 0; iThread < numberThreads_; iThread++) {4125 if (threadInfo[iThread].returnCode > 0) {4126 finished = true;4127 break;4128 } else if (threadInfo[iThread].returnCode == 0) {4129 pthread_cond_signal(threadInfo[iThread].condition2); // unlock4130 }4131 }4132 }4133 assert (iThread < numberThreads_);4134 // move information to model4135 threadModel[iThread]->moveToModel(this, 1);4136 node = threadInfo[iThread].node;4137 threadInfo[iThread].node = NULL;4138 assert (threadInfo[iThread].returnCode == 1);4139 // say available4140 threadInfo[iThread].returnCode = -1;4141 // carry on4142 threadStats[2]++;4143 }4144 3737 } else { 4145 3738 // Deterministic parallel 4146 if (tree_->size() < CoinM in(numberThreads_, 8) && !goneParallel) {3739 if (tree_->size() < CoinMax(numberThreads_, 8) && !goneParallel) { 4147 3740 node = tree_->bestNode(cutoff) ; 4148 3741 // Possible one on tree worse than cutoff … … 4186 3779 } 4187 3780 } else { 4188 // Split 4189 int saveTreeSize = tree_->size();3781 // Split and solve 3782 master_->deterministicParallel(); 4190 3783 goneParallel = true; 4191 int nAffected = splitModel(numberThreads_, threadModel, defaultParallelNodes);4192 int iThread;4193 // do all until finished4194 for (iThread = 0; iThread < numberThreads_; iThread++) {4195 // obviously tune4196 threadInfo[iThread].nDeleteNode = defaultParallelIterations;4197 }4198 // Save current state4199 int iObject;4200 for (iObject = 0; iObject < numberObjects_; iObject++) {4201 saveObjects[iObject]->updateBefore(object_[iObject]);4202 }4203 for (iThread = 0; iThread < numberThreads_; iThread++) {4204 threadInfo[iThread].returnCode = 0;4205 pthread_cond_signal(threadInfo[iThread].condition2); // unlock4206 }4207 // wait4208 bool finished = false;4209 while (!finished) {4210 pthread_mutex_lock(&condition_mutex);4211 struct timespec absTime;4212 my_gettime(&absTime);4213 double time = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec;4214 absTime.tv_nsec += 1000000; // millisecond4215 if (absTime.tv_nsec >= 1000000000) {4216 absTime.tv_nsec -= 1000000000;4217 absTime.tv_sec++;4218 }4219 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime);4220 my_gettime(&absTime);4221 double time2 = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec;4222 timeWaiting += time2 - time;4223 pthread_mutex_unlock(&condition_mutex);4224 finished = true;4225 for (iThread = 0; iThread < numberThreads_; iThread++) {4226 if (threadInfo[iThread].returnCode <= 0) {4227 finished = false;4228 }4229 }4230 }4231 // Unmark marked4232 for (int i = 0; i < nAffected; i++) {4233 walkback_[i]->unmark();4234 }4235 int iModel;4236 double scaleFactor = 1.0;4237 for (iModel = 0; iModel < numberThreads_; iModel++) {4238 //printf("model %d tree size %d\n",iModel,threadModel[iModel]->tree_->size());4239 if (saveTreeSize > 4*numberThreads_*defaultParallelNodes) {4240 if (!threadModel[iModel]->tree_->size()) {4241 scaleFactor *= 1.05;4242 }4243 }4244 threadModel[iModel]->moveToModel(this, 11);4245 // Update base model4246 OsiObject ** threadObject = threadModel[iModel]->object_;4247 for (iObject = 0; iObject < numberObjects_; iObject++) {4248 object_[iObject]->updateAfter(threadObject[iObject], saveObjects[iObject]);4249 }4250 }4251 if (scaleFactor != 1.0) {4252 int newNumber = static_cast<int> (defaultParallelNodes * scaleFactor + 0.5001);4253 if (newNumber*2 < defaultParallelIterations) {4254 if (defaultParallelNodes == 1)4255 newNumber = 2;4256 if (newNumber != defaultParallelNodes) {4257 char general[200];4258 sprintf(general, "Changing tree size from %d to %d",4259 defaultParallelNodes, newNumber);4260 messageHandler()->message(CBC_GENERAL,4261 messages())4262 << general << CoinMessageEol ;4263 defaultParallelNodes = newNumber;4264 }4265 }4266 }4267 //printf("Tree sizes %d %d %d - affected %d\n",saveTreeSize,saveTreeSize2,tree_->size(),nAffected);4268 3784 } 4269 3785 } … … 4278 3794 #ifdef CBC_THREAD 4279 3795 if (numberThreads_) { 4280 int i; 4281 // Seems to be bug in CoinCpu on Linux - does threads as well despite documentation 4282 double time = 0.0; 4283 for (i = 0; i < numberThreads_; i++) 4284 time += threadInfo[i].timeInThread; 4285 bool goodTimer = time < (getCurrentSeconds()); 4286 for (i = 0; i < numberThreads_; i++) { 4287 while (threadInfo[i].returnCode == 0) { 4288 pthread_cond_signal(threadInfo[i].condition2); // unlock 4289 pthread_mutex_lock(&condition_mutex); 4290 struct timespec absTime; 4291 my_gettime(&absTime); 4292 absTime.tv_nsec += 1000000; // millisecond 4293 if (absTime.tv_nsec >= 1000000000) { 4294 absTime.tv_nsec -= 1000000000; 4295 absTime.tv_sec++; 4296 } 4297 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime); 4298 my_gettime(&absTime); 4299 pthread_mutex_unlock(&condition_mutex); 4300 } 4301 pthread_cond_signal(threadInfo[i].condition2); // unlock 4302 pthread_mutex_lock(&condition_mutex); // not sure necessary but have had one hang on interrupt 4303 threadModel[i]->numberThreads_ = 0; // say exit 4304 if (parallelMode() < 0) 4305 delete [] threadInfo[i].delNode; 4306 threadInfo[i].returnCode = 0; 4307 pthread_mutex_unlock(&condition_mutex); 4308 pthread_cond_signal(threadInfo[i].condition2); // unlock 4309 //if (!stopped) 4310 //pthread_join(threadId[i],NULL); 4311 int returnCode; 4312 returnCode = pthread_join(threadId[i].thr, NULL); 4313 threadId[i].status = 0; 4314 assert (!returnCode); 4315 //else 4316 //pthread_kill(threadId[i]); // kill rather than try and synchronize 4317 threadModel[i]->moveToModel(this, 2); 4318 pthread_mutex_destroy (threadInfo[i].mutex2); 4319 pthread_cond_destroy (threadInfo[i].condition2); 4320 assert (threadInfo[i].numberTimesLocked == threadInfo[i].numberTimesUnlocked); 4321 handler_->message(CBC_THREAD_STATS, messages_) 4322 << "Thread"; 4323 handler_->printing(true) 4324 << i << threadCount[i] << threadInfo[i].timeWaitingToStart; 4325 handler_->printing(goodTimer) << threadInfo[i].timeInThread; 4326 handler_->printing(false) << 0.0; 4327 handler_->printing(true) << threadInfo[i].numberTimesLocked 4328 << threadInfo[i].timeLocked << threadInfo[i].timeWaitingToLock 4329 << CoinMessageEol; 4330 } 4331 assert (threadInfo[numberThreads_].numberTimesLocked == threadInfo[numberThreads_].numberTimesUnlocked); 4332 handler_->message(CBC_THREAD_STATS, messages_) 4333 << "Main thread"; 4334 handler_->printing(false) << 0 << 0 << 0.0; 4335 handler_->printing(false) << 0.0; 4336 handler_->printing(true) << timeWaiting; 4337 handler_->printing(true) << threadInfo[numberThreads_].numberTimesLocked 4338 << threadInfo[numberThreads_].timeLocked << threadInfo[numberThreads_].timeWaitingToLock 4339 << CoinMessageEol; 4340 pthread_mutex_destroy (&mutex); 4341 pthread_cond_destroy (&condition_main); 4342 pthread_mutex_destroy (&condition_mutex); 4343 // delete models (here in case some point to others) 4344 for (i = 0; i < numberThreads_; i++) { 4345 // make sure handler will be deleted 4346 threadModel[i]->defaultHandler_ = true; 4347 delete threadModel[i]; 4348 } 4349 delete [] mutex2; 4350 delete [] condition2; 4351 delete [] threadId; 4352 delete [] threadInfo; 4353 delete [] threadModel; 4354 delete [] threadCount; 4355 mutex_ = NULL; 3796 master_->waitForThreadsInTree(2); 3797 delete master_; 3798 master_ = NULL; 3799 masterThread_ = NULL; 4356 3800 // adjust time to allow for children on some systems 4357 3801 dblParam_[CbcStartSeconds] -= CoinCpuTimeJustChildren(); … … 4914 4358 subTreeModel_(NULL), 4915 4359 numberStoppedSubTrees_(0), 4916 mutex_(NULL),4917 4360 presolve_(0), 4918 4361 numberStrong_(5), … … 4977 4420 storedRowCuts_(NULL), 4978 4421 numberThreads_(0), 4979 threadMode_(0) 4422 threadMode_(0), 4423 master_(NULL), 4424 masterThread_(NULL) 4980 4425 { 4981 4426 memset(intParam_, 0, sizeof(intParam_)); … … 5072 4517 subTreeModel_(NULL), 5073 4518 numberStoppedSubTrees_(0), 5074 mutex_(NULL),5075 4519 presolve_(0), 5076 4520 numberStrong_(5), … … 5135 4579 storedRowCuts_(NULL), 5136 4580 numberThreads_(0), 5137 threadMode_(0) 4581 threadMode_(0), 4582 master_(NULL), 4583 masterThread_(NULL) 5138 4584 { 5139 4585 memset(intParam_, 0, sizeof(intParam_)); … … 5325 4771 subTreeModel_(rhs.subTreeModel_), 5326 4772 numberStoppedSubTrees_(rhs.numberStoppedSubTrees_), 5327 mutex_(NULL),5328 4773 presolve_(rhs.presolve_), 5329 4774 numberStrong_(rhs.numberStrong_), … … 5377 4822 storedRowCuts_(NULL), 5378 4823 numberThreads_(rhs.numberThreads_), 5379 threadMode_(rhs.threadMode_) 4824 threadMode_(rhs.threadMode_), 4825 master_(NULL), 4826 masterThread_(NULL) 5380 4827 { 5381 4828 memcpy(intParam_, rhs.intParam_, sizeof(intParam_)); … … 5493 4940 appData_ = rhs.appData_; 5494 4941 messages_ = rhs.messages_; 5495 ownership_ = 0x80000000;4942 ownership_ = rhs.ownership_ | 0x80000000; 5496 4943 messageHandler()->setLogLevel(rhs.messageHandler()->logLevel()); 5497 4944 numberIntegers_ = rhs.numberIntegers_; … … 5674 5121 subTreeModel_ = rhs.subTreeModel_; 5675 5122 numberStoppedSubTrees_ = rhs.numberStoppedSubTrees_; 5676 mutex_ = NULL;5677 5123 presolve_ = rhs.presolve_; 5678 5124 numberStrong_ = rhs.numberStrong_; … … 5747 5193 numberThreads_ = rhs.numberThreads_; 5748 5194 threadMode_ = rhs.threadMode_; 5195 delete master_; 5196 master_ = NULL; 5197 masterThread_ = NULL; 5749 5198 searchStrategy_ = rhs.searchStrategy_; 5750 5199 numberStrongIterations_ = rhs.numberStrongIterations_; … … 6113 5562 numberThreads_ = rhs.numberThreads_; 6114 5563 threadMode_ = rhs.threadMode_; 5564 delete master_; 5565 master_ = NULL; 5566 masterThread_ = NULL; 6115 5567 memcpy(intParam_, rhs.intParam_, sizeof(intParam_)); 6116 5568 memcpy(dblParam_, rhs.dblParam_, sizeof(dblParam_)); … … 6813 6265 int i; 6814 6266 if (currentNumberCuts) { 6815 if (parallelMode() > 0) 6816 lockThread(); 6267 lockThread(); 6817 6268 int numberLeft = nodeInfo->numberBranchesLeft(); 6818 6269 for (i = 0 ; i < currentNumberCuts ; i++) { … … 6824 6275 } 6825 6276 } 6826 if (parallelMode() > 0) 6827 unlockThread(); 6277 unlockThread(); 6828 6278 } 6829 6279 return 1 ; … … 7020 6470 //solver_->writeMps("saved"); 7021 6471 #ifdef CBC_THREAD 7022 /* 7023 Thread mode makes a difference here only when it specifies using separate 7024 threads to generate cuts at the root (bit 2^1 set in threadMode_). In which 7025 case we'll create an array of empty CbcModels (!). Solvers will be cloned 7026 later. 7027 7028 Don't start up threads here if we're already threaded. 7029 */ 7030 CbcModel ** threadModel = NULL; 7031 Coin_pthread_t * threadId = NULL; 7032 pthread_cond_t condition_main; 7033 pthread_mutex_t condition_mutex; 7034 pthread_mutex_t * mutex2 = NULL; 7035 pthread_cond_t * condition2 = NULL; 7036 threadStruct * threadInfo = NULL; 7037 void * saveMutex = NULL; 6472 /* 6473 Thread mode makes a difference here only when it specifies using separate 6474 threads to generate cuts at the root (bit 2^1 set in threadMode_). In which 6475 case we'll create an array of empty CbcModels (!). Solvers will be cloned 6476 later. 6477 6478 Don't start up threads here if we're already threaded. 6479 */ 6480 CbcBaseModel * master = NULL; 7038 6481 if (numberThreads_ && (threadMode_&2) != 0 && !numberNodes_) { 7039 threadId = new Coin_pthread_t [numberThreads_]; 7040 pthread_cond_init(&condition_main, NULL); 7041 pthread_mutex_init(&condition_mutex, NULL); 7042 threadModel = new CbcModel * [numberThreads_]; 7043 threadInfo = new threadStruct [numberThreads_+1]; 7044 mutex2 = new pthread_mutex_t [numberThreads_]; 7045 condition2 = new pthread_cond_t [numberThreads_]; 7046 saveMutex = mutex_; 7047 for (int i = 0; i < numberThreads_; i++) { 7048 pthread_mutex_init(mutex2 + i, NULL); 7049 pthread_cond_init(condition2 + i, NULL); 7050 threadId[i].status = 0; 7051 threadModel[i] = new CbcModel; 7052 threadModel[i]->generator_ = new CbcCutGenerator * [1]; 7053 delete threadModel[i]->solver_; 7054 threadModel[i]->solver_ = NULL; 7055 threadModel[i]->numberThreads_ = numberThreads_; 7056 mutex_ = reinterpret_cast<void *> (threadInfo + i); 7057 threadInfo[i].thisModel = threadModel[i]; 7058 threadInfo[i].baseModel = this; 7059 threadInfo[i].threadIdOfBase.thr = pthread_self(); 7060 threadInfo[i].mutex2 = mutex2 + i; 7061 threadInfo[i].condition2 = condition2 + i; 7062 threadInfo[i].returnCode = -1; 7063 pthread_create(&(threadId[i].thr), NULL, doCutsThread, threadInfo + i); 7064 threadId[i].status = 1; 7065 } 7066 // Do a partial one for base model 7067 threadInfo[numberThreads_].baseModel = this; 7068 mutex_ = reinterpret_cast<void *> (threadInfo + numberThreads_); 7069 threadInfo[numberThreads_].condition2 = &condition_main; 7070 threadInfo[numberThreads_].mutex2 = &condition_mutex; 6482 master = new CbcBaseModel(*this, -1); 7071 6483 } 7072 6484 #endif … … 7094 6506 onOptimalPath = (debugger->onOptimalPath(*solver_)) ; 7095 6507 } 7096 /*7097 As the final action in each round of cut generation (the numberTries loop),7098 we'll call takeOffCuts to remove slack cuts. These are saved into slackCuts7099 and rechecked immediately after the cut generation phase of the loop.7100 */6508 /* 6509 As the final action in each round of cut generation (the numberTries loop), 6510 we'll call takeOffCuts to remove slack cuts. These are saved into slackCuts 6511 and rechecked immediately after the cut generation phase of the loop. 6512 */ 7101 6513 OsiCuts slackCuts; 7102 6514 /* 7103 6515 lh: 7104 7105 7106 The resolve will also refresh cached copies of the solver solution7107 (cbcColLower_, ...) held by CbcModel.7108 This resolve looks like the best point to capture a warm start for use in7109 the case where cut generation proves ineffective and we need to back out7110 a few tight cuts.7111 I've always maintained that this resolve is unnecessary. Let's put in a hook7112 to report if it's every nontrivial. -lh7113 7114 6516 Resolve the problem 6517 6518 The resolve will also refresh cached copies of the solver solution 6519 (cbcColLower_, ...) held by CbcModel. 6520 This resolve looks like the best point to capture a warm start for use in 6521 the case where cut generation proves ineffective and we need to back out 6522 a few tight cuts. 6523 I've always maintained that this resolve is unnecessary. Let's put in a hook 6524 to report if it's every nontrivial. -lh 6525 6526 Resolve the problem. If we've lost feasibility, might as well bail out right 7115 6527 after the debug stuff. The resolve will also refresh cached copies of the 7116 6528 solver solution (cbcColLower_, ...) held by CbcModel. … … 7128 6540 cut_obj[CUT_HISTORY-1] = lastObjective; 7129 6541 //double firstObjective = lastObjective+1.0e-8+1.0e-12*fabs(lastObjective); 7130 /*7131 Contemplate the result of the resolve.7132 - CbcModel::resolve() has a hook that calls CbcStrategy::status to look7133 over the solution. The net result is that resolve can return7134 0 (infeasible), 1 (feasible), or -1 (feasible, but do no further work).7135 - CbcFeasbililityBase::feasible() can return 0 (no comment),7136 1 (pretend this is an integer solution), or -1 (pretend this is7137 infeasible). As of 080104, this seems to be a stub to allow overrides,7138 with a default implementation that always returns 0.7139 7140 Setting numberTries = 0 for `do no more work' is problematic. The main cut7141 generation loop will still execute once, so we do not observe the `no7142 further work' semantics.7143 7144 As best I can see, allBranchesGone is a null function as of 071220.7145 */6542 /* 6543 Contemplate the result of the resolve. 6544 - CbcModel::resolve() has a hook that calls CbcStrategy::status to look 6545 over the solution. The net result is that resolve can return 6546 0 (infeasible), 1 (feasible), or -1 (feasible, but do no further work). 6547 - CbcFeasbililityBase::feasible() can return 0 (no comment), 6548 1 (pretend this is an integer solution), or -1 (pretend this is 6549 infeasible). As of 080104, this seems to be a stub to allow overrides, 6550 with a default implementation that always returns 0. 6551 6552 Setting numberTries = 0 for `do no more work' is problematic. The main cut 6553 generation loop will still execute once, so we do not observe the `no 6554 further work' semantics. 6555 6556 As best I can see, allBranchesGone is a null function as of 071220. 6557 */ 7146 6558 if (node && node->nodeInfo() && !node->nodeInfo()->numberBranchesLeft()) 7147 6559 node->nodeInfo()->allBranchesGone(); // can clean up … … 7152 6564 feasible = false; // pretend infeasible 7153 6565 } 7154 /*7155 NEW_UPDATE_OBJECT is defined to 0 when unthreaded (CBC_THREAD undefined), 27156 when threaded. No sign of 1 as of 071220.7157 7158 At present, there are two sets of hierarchies for branching classes. Call7159 them CbcHier and OsiHier. For example, we have OsiBranchingObject, with7160 children CbcBranchingObject and OsiTwoWayBranchingObject. All7161 specialisations descend from one of these two children. Similarly, there is7162 OsiObject, with children CbcObject and OsiObject2.7163 7164 In the original setup, there's a single CbcBranchDecision object attached7165 to CbcModel (branchingMethod_). It has a field to hold the current CbcHier7166 branching object, and the updateInformation routine reaches through the7167 branching object to update the underlying CbcHier object.7168 7169 NEW_UPDATE_OBJECT = 0 would seem to assume the original setup. But,7170 if we're using the OSI hierarchy for objects and branching, a call to a7171 nontrivial branchingMethod_->updateInformation would have no effect (it7172 would expect a CbcObject to work on) or perhaps crash. For the7173 default CbcBranchDefaultDecision, updateInformation is a noop (actually7174 defined in the base CbcBranchDecision class).7175 7176 NEW_UPDATE_OBJECT = 2 looks like it's prepared to cope with either CbcHier or7177 OsiHier, but it'll be executed only when threads are activated. See the7178 comments below. The setup is scary.7179 7180 But ... if the OsiHier update actually reaches right through to the object7181 list in the solver, it should work just fine in unthreaded mode. It would7182 seem that the appropriate thing to do in unthreaded mode would be to choose7183 between the existing code for NEW_UPDATE_OBJECT = 0 and the OsiHier code for7184 NEW_UPDATE_OBJECT = 2. But I'm going to let John hash that out. The worst7185 that can happen is inefficiency because I'm not properly updating an object.7186 */6566 /* 6567 NEW_UPDATE_OBJECT is defined to 0 when unthreaded (CBC_THREAD undefined), 2 6568 when threaded. No sign of 1 as of 071220. 6569 6570 At present, there are two sets of hierarchies for branching classes. Call 6571 them CbcHier and OsiHier. For example, we have OsiBranchingObject, with 6572 children CbcBranchingObject and OsiTwoWayBranchingObject. All 6573 specialisations descend from one of these two children. Similarly, there is 6574 OsiObject, with children CbcObject and OsiObject2. 6575 6576 In the original setup, there's a single CbcBranchDecision object attached 6577 to CbcModel (branchingMethod_). It has a field to hold the current CbcHier 6578 branching object, and the updateInformation routine reaches through the 6579 branching object to update the underlying CbcHier object. 6580 6581 NEW_UPDATE_OBJECT = 0 would seem to assume the original setup. But, 6582 if we're using the OSI hierarchy for objects and branching, a call to a 6583 nontrivial branchingMethod_->updateInformation would have no effect (it 6584 would expect a CbcObject to work on) or perhaps crash. For the 6585 default CbcBranchDefaultDecision, updateInformation is a noop (actually 6586 defined in the base CbcBranchDecision class). 6587 6588 NEW_UPDATE_OBJECT = 2 looks like it's prepared to cope with either CbcHier or 6589 OsiHier, but it'll be executed only when threads are activated. See the 6590 comments below. The setup is scary. 6591 6592 But ... if the OsiHier update actually reaches right through to the object 6593 list in the solver, it should work just fine in unthreaded mode. It would 6594 seem that the appropriate thing to do in unthreaded mode would be to choose 6595 between the existing code for NEW_UPDATE_OBJECT = 0 and the OsiHier code for 6596 NEW_UPDATE_OBJECT = 2. But I'm going to let John hash that out. The worst 6597 that can happen is inefficiency because I'm not properly updating an object. 6598 */ 7187 6599 7188 6600 // Update branching information if wanted … … 7213 6625 #endif 7214 6626 update.objectNumber_ = iObject; 7215 6627 // Care! We must be careful not to update the same variable in parallel threads. 7216 6628 addUpdateInformation(update); 7217 6629 //#define TIGHTEN_BOUNDS … … 7381 6793 // minimumDrop *= 1.0e-5 ; 7382 6794 // if (numberTries >= -1000000) { 7383 7384 6795 //numberTries=100; 6796 minimumDrop = -1.0; 7385 6797 // } 7386 6798 //numberTries=CoinMax(numberTries,100); … … 7437 6849 if (numberTries < 0 && keepGoing) { 7438 6850 // switch off all normal generators (by the generator's opinion of normal) 7439 7440 6851 // Intended for situations where the primal problem really isn't complete, 6852 // and there are `not normal' cut generators that will augment. 7441 6853 for (int i = 0; i < numberCutGenerators_; i++) { 7442 6854 if (!generator_[i]->mustCallAgain()) … … 7505 6917 7506 6918 The need to resolve here should only happen after a heuristic solution. 7507 optimalBasisIsAvailable resolves to basisIsAvailable, which seems to be part7508 of the old OsiSimplex API. Doc'n says `Returns true if a basis is available7509 and the problem is optimal. Should be used to see if the BinvARow type7510 operations are possible and meaningful.' Which means any solver other the clp7511 is probably doing a lot of unnecessary resolves right here.6919 optimalBasisIsAvailable resolves to basisIsAvailable, which seems to be part 6920 of the old OsiSimplex API. Doc'n says `Returns true if a basis is available 6921 and the problem is optimal. Should be used to see if the BinvARow type 6922 operations are possible and meaningful.' Which means any solver other the clp 6923 is probably doing a lot of unnecessary resolves right here. 7512 6924 (Note default OSI implementation of optimalBasisIsAvailable always returns 7513 6925 false.) … … 7570 6982 //probingInfo_->initializeFixing(); 7571 6983 int i; 7572 /* 7573 threadMode with bit 2^1 set indicates we should use threads for root cut 7574 generation. 7575 */ 6984 // If necessary make cut generators work harder 6985 bool strongCuts = (!node && cut_obj[CUT_HISTORY-1] != -COIN_DBL_MAX && 6986 fabs(cut_obj[CUT_HISTORY-1] - cut_obj[CUT_HISTORY-2]) < 1.0e-7 + 6987 1.0e-6 * fabs(cut_obj[CUT_HISTORY-1])); 6988 for (i = 0; i < numberCutGenerators_; i++) 6989 generator_[i]->setIneffectualCuts(strongCuts); 6990 // Print details 6991 if (!node) { 6992 handler_->message(CBC_ROOT_DETAIL, messages_) 6993 << currentPassNumber_ 6994 << solver_->getNumRows() 6995 << solver_->getNumRows() - numberRowsAtContinuous_ 6996 << solver_->getObjValue() 6997 << CoinMessageEol ; 6998 } 6999 // Status for single pass of cut generation 7000 int status = 0; 7001 /* 7002 threadMode with bit 2^1 set indicates we should use threads for root cut 7003 generation. 7004 */ 7576 7005 if ((threadMode_&2) == 0 || numberNodes_) { 7577 # ifdef COIN_HAS_CLP 7578 if (!node && !parentModel_ && intParam_[CbcMaxNumNode] == -123456) { 7579 OsiClpSolverInterface * clpSolver 7580 = dynamic_cast<OsiClpSolverInterface *> (solver_); 7581 if (clpSolver) { 7582 clpSolver->lexSolve(); 7583 } 7584 } 7585 # endif 7586 int switchOff = (!doCutsNow(1) && !fullScan) ? 1 : 0; 7587 //if (2*solver_->getNumRows()+solver_->getNumCols()>1000) 7588 //switchOff *= 2; 7589 for (i = 0; i < numberCutGenerators_; i++) { 7590 int numberRowCutsBefore = theseCuts.sizeRowCuts() ; 7591 int numberColumnCutsBefore = theseCuts.sizeColCuts() ; 7592 int numberRowCutsAfter = numberRowCutsBefore; 7593 int numberColumnCutsAfter = numberColumnCutsBefore; 7594 bool generate = generator_[i]->normal(); 7595 // skip if not optimal and should be (maybe a cut generator has fixed variables) 7596 if (generator_[i]->howOften() == -100 || 7597 (generator_[i]->needsOptimalBasis() && !solver_->basisIsAvailable()) 7598 || generator_[i]->switchedOff()) 7599 generate = false; 7600 if (switchOff) { 7601 // switch off if default 7602 if (generator_[i]->howOften() == 1 && generator_[i]->whatDepth() < 0) { 7603 /*if (generate) 7604 printf("Gg %d %d %d\n",i, 7605 generator_[i]->howOften(),generator_[i]->whatDepth());*/ 7606 generate = false; 7607 } else if (currentDepth_ > -10 && switchOff == 2) { 7608 generate = false; 7609 } 7610 } 7611 if (generate) { 7612 if (!node && cut_obj[CUT_HISTORY-1] != -COIN_DBL_MAX && 7613 fabs(cut_obj[CUT_HISTORY-1] - cut_obj[CUT_HISTORY-2]) < 1.0e-7 + 7614 1.0e-6*fabs(cut_obj[CUT_HISTORY-1])) 7615 generator_[i]->setIneffectualCuts(true); 7616 bool mustResolve = 7617 generator_[i]->generateCuts(theseCuts, fullScan, solver_, node) ; 7618 generator_[i]->setIneffectualCuts(false); 7619 numberRowCutsAfter = theseCuts.sizeRowCuts() ; 7620 if (fullScan && generator_[i]->howOften() == 1000000 + SCANCUTS_PROBING) { 7621 CglProbing * probing = 7622 dynamic_cast<CglProbing*>(generator_[i]->generator()); 7623 if (probing && (numberRowCutsBefore < numberRowCutsAfter || 7624 numberColumnCutsBefore < theseCuts.sizeColCuts())) { 7625 // switch on 7626 #ifdef COIN_DEVELOP 7627 printf("Switching on probing\n"); 7628 #endif 7629 generator_[i]->setHowOften(1); 7630 } 7631 } 7632 if (numberRowCutsBefore < numberRowCutsAfter && 7633 generator_[i]->mustCallAgain()) 7634 keepGoing = true; // say must go round 7635 // Check last cut to see if infeasible 7636 /* 7637 The convention is that if the generator proves infeasibility, it should 7638 return as its last cut something with lb > ub. 7639 */ 7640 if (numberRowCutsBefore < numberRowCutsAfter) { 7641 const OsiRowCut * thisCut = theseCuts.rowCutPtr(numberRowCutsAfter - 1) ; 7642 if (thisCut->lb() > thisCut->ub()) { 7643 feasible = false; // sub-problem is infeasible 7644 break; 7645 } 7646 } 7647 #ifdef CBC_DEBUG 7648 { 7649 int k ; 7650 for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) { 7651 OsiRowCut thisCut = theseCuts.rowCut(k) ; 7652 /* check size of elements. 7653 We can allow smaller but this helps debug generators as it 7654 is unsafe to have small elements */ 7655 int n = thisCut.row().getNumElements(); 7656 const int * column = thisCut.row().getIndices(); 7657 const double * element = thisCut.row().getElements(); 7658 //assert (n); 7659 for (int i = 0; i < n; i++) { 7660 double value = element[i]; 7661 assert(fabs(value) > 1.0e-12 && fabs(value) < 1.0e20); 7662 } 7663 } 7664 } 7665 #endif 7666 if (mustResolve) { 7667 int returnCode = resolve(node ? node->nodeInfo() : NULL, 2); 7668 feasible = (returnCode != 0) ; 7669 if (returnCode < 0) 7670 numberTries = 0; 7671 if ((specialOptions_&1) != 0) { 7672 debugger = solver_->getRowCutDebugger() ; 7673 if (debugger) 7674 onOptimalPath = (debugger->onOptimalPath(*solver_)) ; 7675 else 7676 onOptimalPath = false; 7677 if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) 7678 assert(feasible) ; 7679 } 7680 if (!feasible) 7681 break ; 7682 } 7683 } 7684 numberRowCutsAfter = theseCuts.sizeRowCuts() ; 7685 numberColumnCutsAfter = theseCuts.sizeColCuts() ; 7686 if ((specialOptions_&1) != 0) { 7687 if (onOptimalPath) { 7688 int k ; 7689 for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) { 7690 OsiRowCut thisCut = theseCuts.rowCut(k) ; 7691 if (debugger->invalidCut(thisCut)) { 7692 solver_->getRowCutDebuggerAlways()->printOptimalSolution(*solver_); 7693 solver_->writeMpsNative("badCut.mps", NULL, NULL, 2); 7694 printf("Cut generator %d (%s) produced invalid cut (%dth in this go)\n", 7695 i, generator_[i]->cutGeneratorName(), k - numberRowCutsBefore); 7696 const double *lower = getColLower() ; 7697 const double *upper = getColUpper() ; 7698 int numberColumns = solver_->getNumCols(); 7699 if (numberColumns < 200) { 7700 for (int i = 0; i < numberColumns; i++) 7701 printf("%d bounds %g,%g\n", i, lower[i], upper[i]); 7702 } 7703 #ifdef CGL_DEBUG_GOMORY 7704 printf("Value of gomory_try is %d, recompile with -%d\n", 7705 gomory_try, gomory_try); 7706 #endif 7707 abort(); 7708 } 7709 assert(!debugger->invalidCut(thisCut)) ; 7710 } 7711 } 7712 } 7713 /* 7714 The cut generator has done its thing, and maybe it generated some 7715 cuts. Do a bit of bookkeeping: load 7716 whichGenerator[i] with the index of the generator responsible for a cut, 7717 and place cuts flagged as global in the global cut pool for the model. 7718 7719 lastNumberCuts is the sum of cuts added in previous iterations; it's the 7720 offset to the proper starting position in whichGenerator. 7721 */ 7722 int numberBefore = 7723 numberRowCutsBefore + lastNumberCuts ; 7724 int numberAfter = 7725 numberRowCutsAfter + lastNumberCuts ; 7726 // possibly extend whichGenerator 7727 resizeWhichGenerator(numberBefore, numberAfter); 7728 int j ; 7729 7730 /* 7731 Look for numerically unacceptable cuts. 7732 */ 7733 bool dodgyCuts = false; 7734 for (j = numberRowCutsBefore; j < numberRowCutsAfter; j++) { 7735 const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ; 7736 if (thisCut->lb() > 1.0e10 || thisCut->ub() < -1.0e10) { 7737 dodgyCuts = true; 7738 break; 7739 } 7740 whichGenerator_[numberBefore++] = i ; 7741 if (thisCut->lb() > thisCut->ub()) 7742 violated = -2; // sub-problem is infeasible 7743 if (thisCut->globallyValid()) { 7744 // add to global list 7745 OsiRowCut newCut(*thisCut); 7746 newCut.setGloballyValid(true); 7747 newCut.mutableRow().setTestForDuplicateIndex(false); 7748 globalCuts_.insert(newCut) ; 7749 } 7750 } 7751 if (dodgyCuts) { 7752 for (int k = numberRowCutsAfter - 1; k >= j; k--) { 7753 const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ; 7754 if (thisCut->lb() > thisCut->ub()) 7755 violated = -2; // sub-problem is infeasible 7756 if (thisCut->lb() > 1.0e10 || thisCut->ub() < -1.0e10) 7757 theseCuts.eraseRowCut(k); 7758 } 7759 numberRowCutsAfter = theseCuts.sizeRowCuts() ; 7760 for (; j < numberRowCutsAfter; j++) { 7761 const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ; 7762 whichGenerator_[numberBefore++] = i ; 7763 if (thisCut->globallyValid()) { 7764 // add to global list 7765 OsiRowCut newCut(*thisCut); 7766 newCut.setGloballyValid(true); 7767 newCut.mutableRow().setTestForDuplicateIndex(false); 7768 globalCuts_.insert(newCut) ; 7769 } 7770 } 7771 } 7772 for (j = numberColumnCutsBefore; j < numberColumnCutsAfter; j++) { 7773 //whichGenerator_[numberBefore++] = i ; 7774 const OsiColCut * thisCut = theseCuts.colCutPtr(j) ; 7775 if (thisCut->globallyValid()) { 7776 // add to global list 7777 OsiColCut newCut(*thisCut); 7778 newCut.setGloballyValid(true); 7779 globalCuts_.insert(newCut) ; 7780 } 7781 } 7782 } 7783 /* 7784 End of loop to run each cut generator. 7785 */ 7786 if (!node) { 7787 handler_->message(CBC_ROOT_DETAIL, messages_) 7788 << currentPassNumber_ 7789 << solver_->getNumRows() 7790 << solver_->getNumRows() - numberRowsAtContinuous_ 7791 << solver_->getObjValue() 7792 << CoinMessageEol ; 7793 } 7794 if (violated >= 0 && feasible) { 7795 #ifdef JJF_ZERO 7796 //winnowCuts(theseCuts); 7797 // look at all cuts here 7798 int nCuts = theseCuts.sizeRowCuts() ; 7799 int k ; 7800 int nEls = 0; 7801 const double * solution = solver_->getColSolution(); 7802 int depth; 7803 if (node) 7804 depth = node->depth(); 7805 else 7806 depth = 0; 7807 for (k = 0; k < nCuts; k++) { 7808 const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ; 7809 int n = thisCut->row().getNumElements(); 7810 nEls += n; 7811 } 7812 //printf("%s has %d cuts and %d elements\n",generatorName_, 7813 // nCuts,nEls); 7814 int nElsNow = solver_->getMatrixByCol()->getNumElements(); 7815 int numberColumns = solver_->getNumCols(); 7816 int numberRows = solver_->getNumRows(); 7817 //double averagePerRow = static_cast<double>(nElsNow)/ 7818 //static_cast<double>(numberRows); 7819 7820 // Check in CbcCutGenerator for similar code. 7821 int nAdd; 7822 int nAdd2; 7823 int nReasonable; 7824 if (!parentModel_ && depth < 2) { 7825 nAdd = 10000; 7826 if (currentPassNumber_ > 1) 7827 nAdd = CoinMin(nAdd, nElsNow + 2 * numberRows); 7828 nAdd2 = 5 * numberColumns; 7829 nReasonable = CoinMax(nAdd2, nElsNow / 8 + nAdd); 7830 } else { 7831 nAdd = 200; 7832 nAdd2 = 2 * numberColumns; 7833 nReasonable = CoinMax(nAdd2, nElsNow / 8 + nAdd); 7834 } 7835 #define SCALE_UP 5 7836 nAdd *= SCALE_UP; 7837 nReasonable *= SCALE_UP; 7838 7839 if (nCuts > nAdd || nEls > nReasonable) { 7840 //printf("need to remove cuts\n"); 7841 // just add most effective 7842 int nDelete = nEls - nReasonable; 7843 7844 nElsNow = nEls; 7845 double * sort = new double [nCuts]; 7846 int * which = new int [nCuts]; 7847 // For parallel cuts 7848 double * element2 = new double [numberColumns]; 7849 #define USE_OBJECTIVE 7850 #ifdef USE_OBJECTIVE 7851 const double *objective = solver_->getObjCoefficients() ; 7852 #endif 7853 CoinZeroN(element2, numberColumns); 7854 for (k = 0; k < nCuts; k++) { 7855 const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ; 7856 double sum = 0.0; 7857 int n = thisCut->row().getNumElements(); 7858 const int * column = thisCut->row().getIndices(); 7859 const double * element = thisCut->row().getElements(); 7860 double norm = 1.0e-3; 7861 #ifdef USE_OBJECTIVE 7862 double normObj = 0.0; 7863 #endif 7864 for (int i = 0; i < n; i++) { 7865 int iColumn = column[i]; 7866 double value = element[i]; 7867 sum += value * solution[iColumn]; 7868 norm += value * value; 7869 #ifdef USE_OBJECTIVE 7870 normObj += value * objective[iColumn]; 7871 #endif 7872 } 7873 if (sum > thisCut->ub()) { 7874 sum = sum - thisCut->ub(); 7875 } else if (sum < thisCut->lb()) { 7876 sum = thisCut->lb() - sum; 7877 } else { 7878 sum = 0.0; 7879 } 7880 #ifdef USE_OBJECTIVE 7881 if (sum) { 7882 normObj = CoinMax(1.0e-6, fabs(normObj)); 7883 norm = sqrt(normObj * norm); 7884 //sum += fabs(normObj)*invObjNorm; 7885 //printf("sum %g norm %g normobj %g invNorm %g mod %g\n", 7886 // sum,norm,normObj,invObjNorm,normObj*invObjNorm); 7887 } 7888 #endif 7889 // normalize 7890 sum /= sqrt(norm); 7891 sort[k] = sum; 7892 which[k] = k; 7893 } 7894 CoinSort_2(sort, sort + nCuts, which); 7895 k = 0; 7896 while (nDelete > 0) { 7897 int iCut = which[k]; 7898 const OsiRowCut * thisCut = theseCuts.rowCutPtr(iCut) ; 7899 int n = thisCut->row().getNumElements(); 7900 nDelete -= n; 7901 k++; 7902 if (k >= nCuts) 7903 break; 7904 } 7905 std::sort(which, which + k); 7906 k--; 7907 for (; k >= 0; k--) { 7908 theseCuts.eraseRowCut(which[k]); 7909 } 7910 delete [] sort; 7911 delete [] which; 7912 } 7913 #else 7914 // delete null cuts 7915 int nCuts = theseCuts.sizeRowCuts() ; 7916 int k ; 7917 for (k = nCuts - 1; k >= 0; k--) { 7918 const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ; 7919 int n = thisCut->row().getNumElements(); 7920 if (!n) 7921 theseCuts.eraseRowCut(k); 7922 } 7923 #endif 7924 } 7925 // Add in any violated saved cuts 7926 if (!theseCuts.sizeRowCuts() && !theseCuts.sizeColCuts()) { 7927 int numberOld = theseCuts.sizeRowCuts() + lastNumberCuts; 7928 int numberCuts = slackCuts.sizeRowCuts() ; 7929 int i; 7930 // possibly extend whichGenerator 7931 resizeWhichGenerator(numberOld, numberOld + numberCuts); 7932 for ( i = 0; i < numberCuts; i++) { 7933 const OsiRowCut * thisCut = slackCuts.rowCutPtr(i) ; 7934 if (thisCut->violated(cbcColSolution_) > 100.0*primalTolerance) { 7935 if (messageHandler()->logLevel() > 2) 7936 printf("Old cut added - violation %g\n", 7937 thisCut->violated(cbcColSolution_)) ; 7938 whichGenerator_[numberOld++] = -1; 7939 theseCuts.insert(*thisCut) ; 7940 } 7941 } 7942 } 7006 status = serialCuts(theseCuts, node, slackCuts, lastNumberCuts); 7943 7007 } else { 7944 7008 // do cuts independently 7945 OsiCuts * eachCuts = new OsiCuts [numberCutGenerators_];;7946 7009 #ifdef CBC_THREAD 7947 if (!threadModel) { 7948 #endif 7949 // generate cuts 7950 for (i = 0; i < numberCutGenerators_; i++) { 7951 bool generate = generator_[i]->normal(); 7952 // skip if not optimal and should be (maybe a cut generator has fixed variables) 7953 if (generator_[i]->needsOptimalBasis() && !solver_->basisIsAvailable()) 7954 generate = false; 7955 if (generator_[i]->switchedOff()) 7956 generate = false;; 7957 if (generate) 7958 generator_[i]->generateCuts(eachCuts[i], fullScan, solver_, node) ; 7959 } 7960 #ifdef CBC_THREAD 7961 } else { 7962 for (i = 0; i < numberThreads_; i++) { 7963 // set solver here after cloning 7964 threadModel[i]->solver_ = solver_->clone(); 7965 threadModel[i]->numberNodes_ = (fullScan) ? 1 : 0; 7966 } 7967 // generate cuts 7968 for (i = 0; i < numberCutGenerators_; i++) { 7969 bool generate = generator_[i]->normal(); 7970 // skip if not optimal and should be (maybe a cut generator has fixed variables) 7971 if (generator_[i]->needsOptimalBasis() && !solver_->basisIsAvailable()) 7972 generate = false; 7973 if (generator_[i]->switchedOff()) 7974 generate = false;; 7975 if (generate) { 7976 bool finished = false; 7977 int iThread = -1; 7978 // see if any available 7979 for (iThread = 0; iThread < numberThreads_; iThread++) { 7980 if (threadInfo[iThread].returnCode) { 7981 finished = true; 7982 break; 7983 } else if (threadInfo[iThread].returnCode == 0) { 7984 pthread_cond_signal(threadInfo[iThread].condition2); // unlock 7985 } 7986 } 7987 while (!finished) { 7988 pthread_mutex_lock(&condition_mutex); 7989 struct timespec absTime; 7990 my_gettime(&absTime); 7991 absTime.tv_nsec += 1000000; // millisecond 7992 if (absTime.tv_nsec >= 1000000000) { 7993 absTime.tv_nsec -= 1000000000; 7994 absTime.tv_sec++; 7995 } 7996 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime); 7997 pthread_mutex_unlock(&condition_mutex); 7998 for (iThread = 0; iThread < numberThreads_; iThread++) { 7999 if (threadInfo[iThread].returnCode > 0) { 8000 finished = true; 8001 break; 8002 } else if (threadInfo[iThread].returnCode == 0) { 8003 pthread_cond_signal(threadInfo[iThread].condition2); // unlock 8004 } 8005 } 8006 } 8007 assert (iThread < numberThreads_); 8008 assert (threadInfo[iThread].returnCode); 8009 threadModel[iThread]->generator_[0] = generator_[i]; 8010 threadModel[iThread]->object_ = reinterpret_cast<OsiObject **> (eachCuts + i); 8011 // allow to start 8012 threadInfo[iThread].returnCode = 0; 8013 pthread_cond_signal(threadInfo[iThread].condition2); // unlock 8014 } 8015 } 8016 // wait 8017 for (int iThread = 0; iThread < numberThreads_; iThread++) { 8018 if (threadInfo[iThread].returnCode == 0) { 8019 bool finished = false; 8020 pthread_cond_signal(threadInfo[iThread].condition2); // unlock 8021 while (!finished) { 8022 pthread_mutex_lock(&condition_mutex); 8023 struct timespec absTime; 8024 my_gettime(&absTime); 8025 absTime.tv_nsec += 1000000; // millisecond 8026 if (absTime.tv_nsec >= 1000000000) { 8027 absTime.tv_nsec -= 1000000000; 8028 absTime.tv_sec++; 8029 } 8030 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime); 8031 pthread_mutex_unlock(&condition_mutex); 8032 if (threadInfo[iThread].returnCode > 0) { 8033 finished = true; 8034 break; 8035 } else if (threadInfo[iThread].returnCode == 0) { 8036 pthread_cond_signal(threadInfo[iThread].condition2); // unlock 8037 } 8038 } 8039 } 8040 assert (threadInfo[iThread].returnCode); 8041 // say available 8042 threadInfo[iThread].returnCode = -1; 8043 delete threadModel[iThread]->solver_; 8044 threadModel[iThread]->solver_ = NULL; 8045 } 8046 } 8047 #endif 8048 // Now put together 8049 for (i = 0; i < numberCutGenerators_; i++) { 8050 // add column cuts 8051 int numberColumnCutsBefore = theseCuts.sizeColCuts() ; 8052 int numberColumnCuts = eachCuts[i].sizeColCuts(); 8053 int numberColumnCutsAfter = numberColumnCutsBefore 8054 + numberColumnCuts; 8055 int j; 8056 for (j = 0; j < numberColumnCuts; j++) { 8057 theseCuts.insert(eachCuts[i].colCut(j)); 8058 } 8059 int numberRowCutsBefore = theseCuts.sizeRowCuts() ; 8060 int numberRowCuts = eachCuts[i].sizeRowCuts(); 8061 int numberRowCutsAfter = numberRowCutsBefore 8062 + numberRowCuts; 8063 if (numberRowCuts) { 8064 for (j = 0; j < numberRowCuts; j++) { 8065 const OsiRowCut * thisCut = eachCuts[i].rowCutPtr(j) ; 8066 if (thisCut->lb() <= 1.0e10 && thisCut->ub() >= -1.0e10) 8067 theseCuts.insert(eachCuts[i].rowCut(j)); 8068 } 8069 if (generator_[i]->mustCallAgain()) 8070 keepGoing = true; // say must go round 8071 // Check last cut to see if infeasible 8072 const OsiRowCut * thisCut = theseCuts.rowCutPtr(numberRowCutsAfter - 1) ; 8073 if (thisCut->lb() > thisCut->ub()) { 8074 feasible = false; // sub-problem is infeasible 8075 break; 8076 } 8077 } 8078 #ifdef CBC_DEBUG 8079 { 8080 int k ; 8081 for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) { 8082 OsiRowCut thisCut = theseCuts.rowCut(k) ; 8083 /* check size of elements. 8084 We can allow smaller but this helps debug generators as it 8085 is unsafe to have small elements */ 8086 int n = thisCut.row().getNumElements(); 8087 const int * column = thisCut.row().getIndices(); 8088 const double * element = thisCut.row().getElements(); 8089 //assert (n); 8090 for (int i = 0; i < n; i++) { 8091 double value = element[i]; 8092 assert(fabs(value) > 1.0e-12 && fabs(value) < 1.0e20); 8093 } 8094 } 8095 } 8096 #endif 8097 if ((specialOptions_&1) != 0) { 8098 if (onOptimalPath) { 8099 int k ; 8100 for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) { 8101 OsiRowCut thisCut = theseCuts.rowCut(k) ; 8102 if (debugger->invalidCut(thisCut)) { 8103 solver_->getRowCutDebuggerAlways()->printOptimalSolution(*solver_); 8104 solver_->writeMpsNative("badCut.mps", NULL, NULL, 2); 8105 #ifdef NDEBUG 8106 printf("Cut generator %d (%s) produced invalid cut (%dth in this go)\n", 8107 i, generator_[i]->cutGeneratorName(), k - numberRowCutsBefore); 8108 const double *lower = getColLower() ; 8109 const double *upper = getColUpper() ; 8110 int numberColumns = solver_->getNumCols(); 8111 for (int i = 0; i < numberColumns; i++) 8112 printf("%d bounds %g,%g\n", i, lower[i], upper[i]); 8113 abort(); 8114 #endif 8115 } 8116 assert(!debugger->invalidCut(thisCut)) ; 8117 } 8118 } 8119 } 8120 /* 8121 The cut generator has done its thing, and maybe it generated some 8122 cuts. Do a bit of bookkeeping: load 8123 whichGenerator[i] with the index of the generator responsible for a cut, 8124 and place cuts flagged as global in the global cut pool for the model. 8125 8126 lastNumberCuts is the sum of cuts added in previous iterations; it's the 8127 offset to the proper starting position in whichGenerator. 8128 */ 8129 int numberBefore = 8130 numberRowCutsBefore + numberColumnCutsBefore + lastNumberCuts ; 8131 int numberAfter = 8132 numberRowCutsAfter + numberColumnCutsAfter + lastNumberCuts ; 8133 // possibly extend whichGenerator 8134 resizeWhichGenerator(numberBefore, numberAfter); 8135 8136 for (j = numberRowCutsBefore; j < numberRowCutsAfter; j++) { 8137 whichGenerator_[numberBefore++] = i ; 8138 const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ; 8139 if (thisCut->lb() > thisCut->ub()) 8140 violated = -2; // sub-problem is infeasible 8141 if (thisCut->globallyValid()) { 8142 // add to global list 8143 OsiRowCut newCut(*thisCut); 8144 newCut.setGloballyValid(true); 8145 newCut.mutableRow().setTestForDuplicateIndex(false); 8146 globalCuts_.insert(newCut) ; 8147 } 8148 } 8149 for (j = numberColumnCutsBefore; j < numberColumnCutsAfter; j++) { 8150 //whichGenerator_[numberBefore++] = i ; 8151 const OsiColCut * thisCut = theseCuts.colCutPtr(j) ; 8152 if (thisCut->globallyValid()) { 8153 // add to global list 8154 OsiColCut newCut(*thisCut); 8155 newCut.setGloballyValid(true); 8156 globalCuts_.insert(newCut) ; 8157 } 8158 } 8159 } 8160 // Add in any violated saved cuts 8161 if (!theseCuts.sizeRowCuts() && !theseCuts.sizeColCuts()) { 8162 int numberOld = theseCuts.sizeRowCuts() + lastNumberCuts; 8163 int numberCuts = slackCuts.sizeRowCuts() ; 8164 int i; 8165 // possibly extend whichGenerator 8166 resizeWhichGenerator(numberOld, numberOld + numberCuts); 8167 for ( i = 0; i < numberCuts; i++) { 8168 const OsiRowCut * thisCut = slackCuts.rowCutPtr(i) ; 8169 if (thisCut->violated(cbcColSolution_) > 100.0*primalTolerance) { 8170 if (messageHandler()->logLevel() > 2) 8171 printf("Old cut added - violation %g\n", 8172 thisCut->violated(cbcColSolution_)) ; 8173 whichGenerator_[numberOld++] = -1; 8174 theseCuts.insert(*thisCut) ; 8175 } 8176 } 8177 } 8178 delete [] eachCuts; 8179 } 7010 status = parallelCuts(master, theseCuts, node, slackCuts, lastNumberCuts); 7011 #endif 7012 } 7013 // Do we need feasible and violated? 7014 feasible = (status >= 0); 7015 if (status == 1) 7016 keepGoing = true; 7017 else if (status == 2) 7018 numberTries = 0; 7019 if (!feasible) 7020 violated = -2; 8180 7021 //if (!feasible) 8181 7022 //break; … … 8209 7050 lastHeuristic_->heuristicName(), whereFrom); 8210 7051 #endif 8211 7052 // CBC_ROUNDING is symbolic; just says found by heuristic 8212 7053 setBestSolution(CBC_ROUNDING, heuristicValue, newSolution) ; 8213 7054 whereFrom |= 8; // say solution found … … 8490 7331 } 8491 7332 int nBadPasses = 0; 8492 7333 // The standard way of determining escape 8493 7334 if (!experimentBreak) { 8494 7335 double test = 0.01 * minimumDrop; … … 8507 7348 badObj = false; // carry on 8508 7349 } else { 8509 7350 // Experimental escape calculations 8510 7351 //if (currentPassNumber_==13||currentPassNumber_>50) 8511 7352 //minimumDrop = CoinMax(1.5*minimumDrop,1.0e-5*fabs(thisObj)); … … 8538 7379 } 8539 7380 } 8540 8541 7381 // magic numbers, they seemed reasonable; there's a possibility here of going more than 7382 // nominal number of passes if we're doing really well. 8542 7383 if (numberTries == 1 && currentDepth_ < 12 && currentPassNumber_ < 10) { 8543 7384 double drop[12] = {1.0, 2.0, 3.0, 10.0, 10.0, 10.0, 10.0, 20.0, 100.0, 100.0, 1000.0, 1000.0}; … … 8585 7426 int i ; 8586 7427 if (currentNumberCuts_) { 8587 if (parallelMode() > 0) 8588 lockThread(); 7428 lockThread(); 8589 7429 for (i = 0; i < currentNumberCuts_; i++) { 8590 7430 // take off node … … 8599 7439 } 8600 7440 } while (numberTries > 0 || keepGoing) ; 8601 /*8602 End cut generation loop.8603 */7441 /* 7442 End cut generation loop. 7443 */ 8604 7444 { 8605 7445 // switch on … … 8626 7466 } 8627 7467 testSolution_ = save; 8628 8629 7468 // Consider the possibility that some alternatives here only make sense in context 7469 // of bonmin. 8630 7470 if (integerFeasible) { //update 8631 7471 double objValue = solver_->getObjValue(); … … 8677 7517 } 8678 7518 /* 8679 End of code block to check for a solution, when cuts may be added as a result8680 of a feasible solution.7519 End of code block to check for a solution, when cuts may be added as a result 7520 of a feasible solution. 8681 7521 8682 7522 Reduced cost fix at end. Must also check feasible, in case we've popped out … … 8753 7593 //printf("XXb sum obj changed by %g\n",sumChangeObjective2_); 8754 7594 /* 8755 8756 8757 adjust the frequency of use for any of the cut generators. If the client8758 specified a positive number for howOften, it will never change. If the8759 original value was negative, it'll be converted to 1000000+|howOften|, and8760 this value will be adjusted each time fullScan is true. Actual cut8761 generation is performed every howOften%1000000 nodes; the 1000000 offset is8762 just a convenient way to specify that the frequency is adjustable.8763 -lh7595 lh: 7596 Is this a full scan interval? If so, consider if we want to disable or 7597 adjust the frequency of use for any of the cut generators. If the client 7598 specified a positive number for howOften, it will never change. If the 7599 original value was negative, it'll be converted to 1000000+|howOften|, and 7600 this value will be adjusted each time fullScan is true. Actual cut 7601 generation is performed every howOften%1000000 nodes; the 1000000 offset is 7602 just a convenient way to specify that the frequency is adjustable. 7603 -lh 8764 7604 End of cut generation loop. 8765 7605 … … 8778 7618 TODO: All this should probably be hidden in a method of the CbcCutGenerator 8779 7619 class. 8780 lh:8781 TODO: Can the loop that scans over whichGenerator to accumulate per8782 8783 8784 8785 8786 8787 8788 The root is automatically a full scan interval. At the root, decide if8789 we're going to do cuts in the tree, and whether we should keep the cuts we8790 have.8791 8792 Codes for willBeCutsInTree:7620 lh: 7621 TODO: Can the loop that scans over whichGenerator to accumulate per 7622 generator counts be replaced by values in countRowCuts and 7623 countColumnCuts? 7624 7625 << I think the answer is yes, but not the other way 'round. Row and 7626 column cuts are block interleaved in whichGenerator. >> 7627 7628 The root is automatically a full scan interval. At the root, decide if 7629 we're going to do cuts in the tree, and whether we should keep the cuts we 7630 have. 7631 7632 Codes for willBeCutsInTree: 8793 7633 -1: no cuts in tree and currently active cuts seem ineffective; delete 8794 7634 them 8795 7635 0: no cuts in tree but currently active cuts seem effective; make them 8796 7636 into architecturals (faster than treating them as cuts) 8797 7637 1: cuts will be generated in the tree; currently active cuts remain as 8798 8799 -lh7638 cuts 7639 -lh 8800 7640 */ 8801 7641 #ifdef NODE_LOG … … 8817 7657 double densityNew = numberRowsAdded ? (static_cast<double> (numberElementsAdded)) / static_cast<double> (numberRowsAdded) 8818 7658 : 0.0; 8819 /*8820 If we're at the root, and we added cuts, and the cuts haven't changed the8821 objective, and the cuts resulted in a significant increase (> 20%) in nonzero8822 coefficients, do no cuts in the tree and ditch the current cuts. They're not8823 cost-effective.8824 */7659 /* 7660 If we're at the root, and we added cuts, and the cuts haven't changed the 7661 objective, and the cuts resulted in a significant increase (> 20%) in nonzero 7662 coefficients, do no cuts in the tree and ditch the current cuts. They're not 7663 cost-effective. 7664 */ 8825 7665 if (!numberNodes_) { 8826 7666 if (numberRowsAdded) … … 8939 7779 } 8940 7780 } 8941 /*8942 Noop block 071219.8943 */7781 /* 7782 Noop block 071219. 7783 */ 8944 7784 if ((numberRowsAdded > 100 + 0.5*numberRowsAtStart 8945 7785 || numberElementsAdded > 0.5*numberElementsAtStart) … … 8951 7791 // numberRowsAdded,densityNew); 8952 7792 } 8953 /*8954 Noop block 071219.8955 */7793 /* 7794 Noop block 071219. 7795 */ 8956 7796 if (densityNew > 100.0 && numberRowsAdded > 2 && densityNew > 2.0*densityOld) { 8957 7797 //if (thisObjective-startObjective<0.1*fabs(startObjective)+1.0e-5) … … 8961 7801 } 8962 7802 // Root node or every so often - see what to turn off 8963 /*8964 Hmmm ... > -90 for any generator will overrule previous decision to do no8965 cuts in tree and delete existing cuts.8966 */7803 /* 7804 Hmmm ... > -90 for any generator will overrule previous decision to do no 7805 cuts in tree and delete existing cuts. 7806 */ 8967 7807 int i ; 8968 7808 for (i = 0; i < numberCutGenerators_; i++) { … … 8977 7817 << currentPassNumber_ 8978 7818 << CoinMessageEol ; 8979 /*8980 Count the number of cuts produced by each cut generator on this call. Not8981 clear to me that the accounting is equivalent here. whichGenerator_ records8982 the generator for column and row cuts. So unless numberNewCuts is row cuts8983 only, we're double counting for JUST_ACTIVE. Note too the multiplier applied8984 to column cuts.8985 */7819 /* 7820 Count the number of cuts produced by each cut generator on this call. Not 7821 clear to me that the accounting is equivalent here. whichGenerator_ records 7822 the generator for column and row cuts. So unless numberNewCuts is row cuts 7823 only, we're double counting for JUST_ACTIVE. Note too the multiplier applied 7824 to column cuts. 7825 */ 8986 7826 if (!numberNodes_) { 8987 7827 double value = CoinMax(minimumDrop_, 0.005 * (thisObjective - startObjective) / … … 9014 7854 totalCuts += value; 9015 7855 } 9016 /*9017 Open up a loop to step through the cut generators and decide what (if any)9018 adjustment should be made for calling frequency.9019 */7856 /* 7857 Open up a loop to step through the cut generators and decide what (if any) 7858 adjustment should be made for calling frequency. 7859 */ 9020 7860 int iProbing = -1; 9021 7861 double smallProblem = (0.2 * totalCuts) / … … 9025 7865 /* Probing can be set to just do column cuts in treee. 9026 7866 But if doing good then leave as on 9027 Ok, let me try to explain this. rowCuts = 3 says do disaggregation (1<<0) and9028 coefficient (1<<1) cuts. But if the value is negative, there's code at the9029 entry to generateCuts, and generateCutsAndModify, that temporarily changes9030 the value to 4 (1<<2) if we're in a search tree.9031 9032 Which does nothing to explain this next bit. We set a boolean, convert9033 howOften to the code for `generate while objective is improving', and change9034 over to `do everywhere'. Hmmm ... now I write it out, this makes sense in the9035 context of the original comment. If we're doing well (objective improving)9036 we'll keep probing fully active.9037 9038 7867 Ok, let me try to explain this. rowCuts = 3 says do disaggregation (1<<0) and 7868 coefficient (1<<1) cuts. But if the value is negative, there's code at the 7869 entry to generateCuts, and generateCutsAndModify, that temporarily changes 7870 the value to 4 (1<<2) if we're in a search tree. 7871 7872 Which does nothing to explain this next bit. We set a boolean, convert 7873 howOften to the code for `generate while objective is improving', and change 7874 over to `do everywhere'. Hmmm ... now I write it out, this makes sense in the 7875 context of the original comment. If we're doing well (objective improving) 7876 we'll keep probing fully active. 7877 7878 */ 9039 7879 bool probingWasOnBut = false; 9040 7880 CglProbing * probing = dynamic_cast<CglProbing*>(generator_[i]->generator()); … … 9052 7892 } 9053 7893 } 9054 /*9055 Convert `as long as objective is improving' into `only at root' if we've9056 decided cuts just aren't worth it.9057 */7894 /* 7895 Convert `as long as objective is improving' into `only at root' if we've 7896 decided cuts just aren't worth it. 7897 */ 9058 7898 if (willBeCutsInTree < 0 && howOften == -98) 9059 7899 howOften = -99; 9060 /*9061 And check to see if the objective is improving. But don't do the check if9062 the user has specified some minimum number of cuts.9063 9064 This exclusion seems bogus, or at least counterintuitive. Why would a user9065 suspect that setting a minimum cut limit would invalidate the objective9066 check? Nor do I see the point in comparing the number of rows and columns9067 in the second test.9068 */7900 /* 7901 And check to see if the objective is improving. But don't do the check if 7902 the user has specified some minimum number of cuts. 7903 7904 This exclusion seems bogus, or at least counterintuitive. Why would a user 7905 suspect that setting a minimum cut limit would invalidate the objective 7906 check? Nor do I see the point in comparing the number of rows and columns 7907 in the second test. 7908 */ 9069 7909 if (!probing && howOften == -98 && !generator_[i]->numberShortCutsAtRoot() && 9070 7910 generator_[i]->numberCutsInTotal()) { … … 9080 7920 howOften = -99; // switch off 9081 7921 } 9082 /*9083 Below -99, this generator is switched off. There's no need to consider9084 further. Then again, there was no point in persisting this far!9085 */7922 /* 7923 Below -99, this generator is switched off. There's no need to consider 7924 further. Then again, there was no point in persisting this far! 7925 */ 9086 7926 if (howOften < -99) 9087 7927 continue ; 9088 /*9089 Adjust, if howOften is adjustable.9090 */7928 /* 7929 Adjust, if howOften is adjustable. 7930 */ 9091 7931 if (howOften < 0 || howOften >= 1000000) { 9092 7932 if ( !numberNodes_) { 9093 /*9094 If root only, or objective improvement but no cuts generated, switch off. If9095 it's just that the generator found no cuts at the root, give it one more9096 chance.9097 */7933 /* 7934 If root only, or objective improvement but no cuts generated, switch off. If 7935 it's just that the generator found no cuts at the root, give it one more 7936 chance. 7937 */ 9098 7938 // If small number switch mostly off 9099 7939 #ifdef JUST_ACTIVE … … 9121 7961 } 9122 7962 } 9123 /*9124 Not productive, but not zero either.9125 */7963 /* 7964 Not productive, but not zero either. 7965 */ 9126 7966 } else if ((thisCuts + generator_[i]->numberColumnCuts() < smallProblem) 9127 7967 && !generator_[i] ->whetherToUse()) { 9128 /*9129 Not unadjustable every node, and not strong probing.9130 */7968 /* 7969 Not unadjustable every node, and not strong probing. 7970 */ 9131 7971 if (howOften != 1 && !probingWasOnBut) { 9132 /*9133 No depth spec, or not adjustable every node.9134 */7972 /* 7973 No depth spec, or not adjustable every node. 7974 */ 9135 7975 if (generator_[i]->whatDepth() < 0 || howOften != -1) { 9136 7976 int k = static_cast<int> (sqrt(smallProblem / thisCuts)) ; 9137 /*9138 Not objective improvement, set to new frequency, otherwise turn off.9139 */7977 /* 7978 Not objective improvement, set to new frequency, otherwise turn off. 7979 */ 9140 7980 if (howOften != -98) 9141 7981 howOften = k + 1000000 ; 9142 7982 else 9143 7983 howOften = -100; 9144 /*9145 Depth spec, or adjustable every node. Force to unadjustable every node.9146 */7984 /* 7985 Depth spec, or adjustable every node. Force to unadjustable every node. 7986 */ 9147 7987 } else { 9148 7988 howOften = 1; 9149 7989 } 9150 /*9151 Unadjustable every node, or strong probing. Force unadjustable every node and9152 force not strong probing? I don't understand.9153 */7990 /* 7991 Unadjustable every node, or strong probing. Force unadjustable every node and 7992 force not strong probing? I don't understand. 7993 */ 9154 7994 } else { 9155 7995 howOften = 1; … … 9157 7997 probingWasOnBut = false; 9158 7998 } 9159 /*9160 Productive cut generator. Say we'll do it every node, adjustable. But if the9161 objective isn't improving, restrict that to every fifth depth level9162 (whatDepth overrides howOften in generateCuts).9163 */7999 /* 8000 Productive cut generator. Say we'll do it every node, adjustable. But if the 8001 objective isn't improving, restrict that to every fifth depth level 8002 (whatDepth overrides howOften in generateCuts). 8003 */ 9164 8004 } else { 9165 8005 if (thisObjective - startObjective < 0.1*fabs(startObjective) + 1.0e-5 && generator_[i]->whatDepth() < 0) … … 9168 8008 } 9169 8009 } 9170 /*9171 End root actions.9172 9173 sumChangeObjective2_ is the objective change due to cuts. If we're getting9174 much better results from branching over a large number of nodes, switch off9175 cuts.9176 9177 Except it doesn't, really --- it just puts off the decision 'til the9178 next full scan, when it'll put it off again unless cuts look better.9179 */8010 /* 8011 End root actions. 8012 8013 sumChangeObjective2_ is the objective change due to cuts. If we're getting 8014 much better results from branching over a large number of nodes, switch off 8015 cuts. 8016 8017 Except it doesn't, really --- it just puts off the decision 'til the 8018 next full scan, when it'll put it off again unless cuts look better. 8019 */ 9180 8020 // If cuts useless switch off 9181 8021 if (numberNodes_ >= 100000 && sumChangeObjective1_ > 2.0e2*(sumChangeObjective2_ + 1.0e-12)) { … … 9184 8024 } 9185 8025 } 9186 /*9187 Ok, that's the frequency adjustment bit.9188 9189 Now, if we're at the root, force probing back on at every node, for column9190 cuts at least, even if it looks useless for row cuts. Notice that if it9191 looked useful, the values set above mean we'll be doing strong probing in9192 the tree subject to objective improvement.9193 */8026 /* 8027 Ok, that's the frequency adjustment bit. 8028 8029 Now, if we're at the root, force probing back on at every node, for column 8030 cuts at least, even if it looks useless for row cuts. Notice that if it 8031 looked useful, the values set above mean we'll be doing strong probing in 8032 the tree subject to objective improvement. 8033 */ 9194 8034 if (!numberNodes_) { 9195 8035 if (probingWasOnBut && howOften == -100) { … … 9203 8043 willBeCutsInTree = 1; 9204 8044 } 9205 /*9206 Set the new frequency in the generator. If this is an adjustable frequency,9207 use the value to set whatDepth.9208 9209 Hey! Seems like this could override the user's depth setting.9210 */8045 /* 8046 Set the new frequency in the generator. If this is an adjustable frequency, 8047 use the value to set whatDepth. 8048 8049 Hey! Seems like this could override the user's depth setting. 8050 */ 9211 8051 generator_[i]->setHowOften(howOften) ; 9212 8052 if (howOften >= 1000000 && howOften < 2000000 && 0) { … … 9249 8089 } 9250 8090 } 9251 /*9252 End loop to adjust cut generator frequency of use.9253 */8091 /* 8092 End loop to adjust cut generator frequency of use. 8093 */ 9254 8094 delete [] count ; 9255 8095 if ( !numberNodes_) { … … 9259 8099 generator_[i]->setNumberActiveCutsAtRoot(generator_[i]->numberCutsActive()); 9260 8100 } 9261 /*9262 Garbage code 0712199263 */8101 /* 8102 Garbage code 071219 8103 */ 9264 8104 // decide on pseudo cost strategy 9265 8105 int howOften = iProbing >= 0 ? generator_[iProbing]->howOften() : 0; … … 9286 8126 if (willBeCutsInTree == -2) 9287 8127 willBeCutsInTree = 0; 9288 /*9289 End garbage code.9290 9291 Now I've reached the problem area. This is a problem only at the root node,9292 so that should simplify the issue of finding a workable basis? Or maybe not.9293 */8128 /* 8129 End garbage code. 8130 8131 Now I've reached the problem area. This is a problem only at the root node, 8132 so that should simplify the issue of finding a workable basis? Or maybe not. 8133 */ 9294 8134 if ( willBeCutsInTree <= 0) { 9295 8135 // Take off cuts … … 9378 8218 # endif 9379 8219 #ifdef CBC_THREAD 9380 if (threadModel) { 9381 // stop threads 9382 int i; 9383 for (i = 0; i < numberThreads_; i++) { 9384 while (threadInfo[i].returnCode == 0) { 9385 pthread_cond_signal(threadInfo[i].condition2); // unlock 9386 pthread_mutex_lock(&condition_mutex); 9387 struct timespec absTime; 9388 my_gettime(&absTime); 9389 absTime.tv_nsec += 1000000; // millisecond 9390 if (absTime.tv_nsec >= 1000000000) { 9391 absTime.tv_nsec -= 1000000000; 9392 absTime.tv_sec++; 9393 } 9394 pthread_cond_timedwait(&condition_main, &condition_mutex, &absTime); 9395 my_gettime(&absTime); 9396 pthread_mutex_unlock(&condition_mutex); 9397 } 9398 threadModel[i]->numberThreads_ = 0; // say exit 9399 threadInfo[i].returnCode = 0; 9400 pthread_cond_signal(threadInfo[i].condition2); // unlock 9401 pthread_join(threadId[i].thr, NULL); 9402 threadId[i].status = 0; 9403 pthread_mutex_destroy (threadInfo[i].mutex2); 9404 pthread_cond_destroy (threadInfo[i].condition2); 9405 threadModel[i]->generator_[0] = NULL; 9406 delete [] threadModel[i]->generator_; 9407 threadModel[i]->generator_ = NULL; 9408 threadModel[i]->object_ = NULL; 9409 } 9410 pthread_cond_destroy (&condition_main); 9411 pthread_mutex_destroy (&condition_mutex); 9412 // delete models and solvers 9413 for (i = 0; i < numberThreads_; i++) { 9414 // make sure message handler will be deleted 9415 threadModel[i]->defaultHandler_ = true; 9416 delete threadModel[i]; 9417 } 9418 delete [] mutex2; 9419 delete [] condition2; 9420 delete [] threadId; 9421 delete [] threadInfo; 9422 delete [] threadModel; 9423 mutex_ = saveMutex; 8220 // Get rid of all threaded stuff 8221 if (master) { 8222 master->stopThreads(); 8223 delete master; 9424 8224 } 9425 8225 #endif … … 9430 8230 } 9431 8231 8232 // Generate one round of cuts - serial mode 8233 int 8234 CbcModel::serialCuts(OsiCuts & theseCuts, CbcNode * node, OsiCuts & slackCuts, int lastNumberCuts) 8235 { 8236 /* 8237 Is it time to scan the cuts in order to remove redundant cuts? If so, set 8238 up to do it. 8239 */ 8240 int fullScan = 0 ; 8241 if ((numberNodes_ % SCANCUTS) == 0 || (specialOptions_&256) != 0) { 8242 fullScan = 1 ; 8243 if (!numberNodes_ || (specialOptions_&256) != 0) 8244 fullScan = 2; 8245 specialOptions_ &= ~256; // mark as full scan done 8246 } 8247 # ifdef COIN_HAS_CLP 8248 if (!node && !parentModel_ && intParam_[CbcMaxNumNode] == -123456) { 8249 OsiClpSolverInterface * clpSolver 8250 = dynamic_cast<OsiClpSolverInterface *> (solver_); 8251 if (clpSolver) { 8252 clpSolver->lexSolve(); 8253 } 8254 } 8255 # endif 8256 int switchOff = (!doCutsNow(1) && !fullScan) ? 1 : 0; 8257 int status = 0; 8258 int i; 8259 for (i = 0; i < numberCutGenerators_; i++) { 8260 int numberRowCutsBefore = theseCuts.sizeRowCuts() ; 8261 int numberColumnCutsBefore = theseCuts.sizeColCuts() ; 8262 int numberRowCutsAfter = numberRowCutsBefore; 8263 int numberColumnCutsAfter = numberColumnCutsBefore; 8264 bool generate = generator_[i]->normal(); 8265 // skip if not optimal and should be (maybe a cut generator has fixed variables) 8266 if (generator_[i]->howOften() == -100 || 8267 (generator_[i]->needsOptimalBasis() && !solver_->basisIsAvailable()) 8268 || generator_[i]->switchedOff()) 8269 generate = false; 8270 if (switchOff) { 8271 // switch off if default 8272 if (generator_[i]->howOften() == 1 && generator_[i]->whatDepth() < 0) { 8273 generate = false; 8274 } else if (currentDepth_ > -10 && switchOff == 2) { 8275 generate = false; 8276 } 8277 } 8278 const OsiRowCutDebugger * debugger = NULL; 8279 bool onOptimalPath = false; 8280 if (generate) { 8281 bool mustResolve = 8282 generator_[i]->generateCuts(theseCuts, fullScan, solver_, node) ; 8283 numberRowCutsAfter = theseCuts.sizeRowCuts() ; 8284 if (fullScan && generator_[i]->howOften() == 1000000 + SCANCUTS_PROBING) { 8285 CglProbing * probing = 8286 dynamic_cast<CglProbing*>(generator_[i]->generator()); 8287 if (probing && (numberRowCutsBefore < numberRowCutsAfter || 8288 numberColumnCutsBefore < theseCuts.sizeColCuts())) { 8289 // switch on 8290 generator_[i]->setHowOften(1); 8291 } 8292 } 8293 if (numberRowCutsBefore < numberRowCutsAfter && 8294 generator_[i]->mustCallAgain() && status >= 0) 8295 status = 1 ; // say must go round 8296 // Check last cut to see if infeasible 8297 /* 8298 The convention is that if the generator proves infeasibility, it should 8299 return as its last cut something with lb > ub. 8300 */ 8301 if (numberRowCutsBefore < numberRowCutsAfter) { 8302 const OsiRowCut * thisCut = theseCuts.rowCutPtr(numberRowCutsAfter - 1) ; 8303 if (thisCut->lb() > thisCut->ub()) { 8304 status = -1; // sub-problem is infeasible 8305 break; 8306 } 8307 } 8308 #ifdef CBC_DEBUG 8309 { 8310 int k ; 8311 for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) { 8312 OsiRowCut thisCut = theseCuts.rowCut(k) ; 8313 /* check size of elements. 8314 We can allow smaller but this helps debug generators as it 8315 is unsafe to have small elements */ 8316 int n = thisCut.row().getNumElements(); 8317 const int * column = thisCut.row().getIndices(); 8318 const double * element = thisCut.row().getElements(); 8319 //assert (n); 8320 for (int i = 0; i < n; i++) { 8321 double value = element[i]; 8322 assert(fabs(value) > 1.0e-12 && fabs(value) < 1.0e20); 8323 } 8324 } 8325 } 8326 #endif 8327 if (mustResolve) { 8328 int returnCode = resolve(node ? node->nodeInfo() : NULL, 2); 8329 if (returnCode == 0) 8330 status = -1; 8331 if (returnCode < 0 && !status) 8332 status = 2; 8333 if ((specialOptions_&1) != 0) { 8334 debugger = solver_->getRowCutDebugger() ; 8335 if (debugger) 8336 onOptimalPath = (debugger->onOptimalPath(*solver_)) ; 8337 else 8338 onOptimalPath = false; 8339 if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) 8340 assert(status >= 0) ; 8341 } 8342 if (status < 0) 8343 break ; 8344 } 8345 } 8346 numberRowCutsAfter = theseCuts.sizeRowCuts() ; 8347 numberColumnCutsAfter = theseCuts.sizeColCuts() ; 8348 if ((specialOptions_&1) != 0) { 8349 if (onOptimalPath) { 8350 int k ; 8351 for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) { 8352 OsiRowCut thisCut = theseCuts.rowCut(k) ; 8353 if (debugger->invalidCut(thisCut)) { 8354 solver_->getRowCutDebuggerAlways()->printOptimalSolution(*solver_); 8355 solver_->writeMpsNative("badCut.mps", NULL, NULL, 2); 8356 printf("Cut generator %d (%s) produced invalid cut (%dth in this go)\n", 8357 i, generator_[i]->cutGeneratorName(), k - numberRowCutsBefore); 8358 const double *lower = getColLower() ; 8359 const double *upper = getColUpper() ; 8360 int numberColumns = solver_->getNumCols(); 8361 if (numberColumns < 200) { 8362 for (int i = 0; i < numberColumns; i++) 8363 printf("%d bounds %g,%g\n", i, lower[i], upper[i]); 8364 } 8365 abort(); 8366 } 8367 assert(!debugger->invalidCut(thisCut)) ; 8368 } 8369 } 8370 } 8371 /* 8372 The cut generator has done its thing, and maybe it generated some 8373 cuts. Do a bit of bookkeeping: load 8374 whichGenerator[i] with the index of the generator responsible for a cut, 8375 and place cuts flagged as global in the global cut pool for the model. 8376 8377 lastNumberCuts is the sum of cuts added in previous iterations; it's the 8378 offset to the proper starting position in whichGenerator. 8379 */ 8380 int numberBefore = 8381 numberRowCutsBefore + lastNumberCuts ; 8382 int numberAfter = 8383 numberRowCutsAfter + lastNumberCuts ; 8384 // possibly extend whichGenerator 8385 resizeWhichGenerator(numberBefore, numberAfter); 8386 int j ; 8387 8388 /* 8389 Look for numerically unacceptable cuts. 8390 */ 8391 bool dodgyCuts = false; 8392 for (j = numberRowCutsBefore; j < numberRowCutsAfter; j++) { 8393 const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ; 8394 if (thisCut->lb() > 1.0e10 || thisCut->ub() < -1.0e10) { 8395 dodgyCuts = true; 8396 break; 8397 } 8398 whichGenerator_[numberBefore++] = i ; 8399 if (thisCut->lb() > thisCut->ub()) 8400 status = -1; // sub-problem is infeasible 8401 if (thisCut->globallyValid()) { 8402 // add to global list 8403 OsiRowCut newCut(*thisCut); 8404 newCut.setGloballyValid(true); 8405 newCut.mutableRow().setTestForDuplicateIndex(false); 8406 globalCuts_.insert(newCut) ; 8407 } 8408 } 8409 if (dodgyCuts) { 8410 for (int k = numberRowCutsAfter - 1; k >= j; k--) { 8411 const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ; 8412 if (thisCut->lb() > thisCut->ub()) 8413 status = -1; // sub-problem is infeasible 8414 if (thisCut->lb() > 1.0e10 || thisCut->ub() < -1.0e10) 8415 theseCuts.eraseRowCut(k); 8416 } 8417 numberRowCutsAfter = theseCuts.sizeRowCuts() ; 8418 for (; j < numberRowCutsAfter; j++) { 8419 const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ; 8420 whichGenerator_[numberBefore++] = i ; 8421 if (thisCut->globallyValid()) { 8422 // add to global list 8423 OsiRowCut newCut(*thisCut); 8424 newCut.setGloballyValid(true); 8425 newCut.mutableRow().setTestForDuplicateIndex(false); 8426 globalCuts_.insert(newCut) ; 8427 } 8428 } 8429 } 8430 for (j = numberColumnCutsBefore; j < numberColumnCutsAfter; j++) { 8431 //whichGenerator_[numberBefore++] = i ; 8432 const OsiColCut * thisCut = theseCuts.colCutPtr(j) ; 8433 if (thisCut->globallyValid()) { 8434 // add to global list 8435 OsiColCut newCut(*thisCut); 8436 newCut.setGloballyValid(true); 8437 globalCuts_.insert(newCut) ; 8438 } 8439 } 8440 } 8441 /* 8442 End of loop to run each cut generator. 8443 */ 8444 if (status >= 0) { 8445 // delete null cuts 8446 int nCuts = theseCuts.sizeRowCuts() ; 8447 int k ; 8448 for (k = nCuts - 1; k >= 0; k--) { 8449 const OsiRowCut * thisCut = theseCuts.rowCutPtr(k) ; 8450 int n = thisCut->row().getNumElements(); 8451 if (!n) 8452 theseCuts.eraseRowCut(k); 8453 } 8454 } 8455 // Add in any violated saved cuts 8456 if (!theseCuts.sizeRowCuts() && !theseCuts.sizeColCuts()) { 8457 int numberOld = theseCuts.sizeRowCuts() + lastNumberCuts; 8458 int numberCuts = slackCuts.sizeRowCuts() ; 8459 int i; 8460 // possibly extend whichGenerator 8461 resizeWhichGenerator(numberOld, numberOld + numberCuts); 8462 double primalTolerance; 8463 solver_->getDblParam(OsiPrimalTolerance, primalTolerance) ; 8464 for ( i = 0; i < numberCuts; i++) { 8465 const OsiRowCut * thisCut = slackCuts.rowCutPtr(i) ; 8466 if (thisCut->violated(cbcColSolution_) > 100.0*primalTolerance) { 8467 if (messageHandler()->logLevel() > 2) 8468 printf("Old cut added - violation %g\n", 8469 thisCut->violated(cbcColSolution_)) ; 8470 whichGenerator_[numberOld++] = -1; 8471 theseCuts.insert(*thisCut) ; 8472 } 8473 } 8474 } 8475 return status; 8476 } 9432 8477 9433 8478 /* … … 9507 8552 int oldCutIndex = 0 ; 9508 8553 if (numberOldActiveCuts_) { 9509 if (parallelMode() > 0) 9510 lockThread(); 8554 lockThread(); 9511 8555 for (i = 0 ; i < numberOldActiveCuts_ ; i++) { 9512 8556 status = ws->getArtifStatus(i + firstOldCut) ; … … 9534 8578 } 9535 8579 } 9536 if (parallelMode() > 0) 9537 unlockThread(); 8580 unlockThread(); 9538 8581 } 9539 8582 /* … … 9962 9005 int returnStatus = feasible ? 1 : 0; 9963 9006 if (strategy_) { 9964 /*9965 Possible returns from status:9966 -1: no recommendation9967 0: treat as optimal9968 1: treat as optimal and finished (no more resolves, cuts, etc.)9969 2: treat as infeasible.9970 */9007 /* 9008 Possible returns from status: 9009 -1: no recommendation 9010 0: treat as optimal 9011 1: treat as optimal and finished (no more resolves, cuts, etc.) 9012 2: treat as infeasible. 9013 */ 9971 9014 // user can play clever tricks here 9972 9015 int status = strategy_->status(this, parent, whereFrom); … … 10040 9083 const double * rowLower = getRowLower(); 10041 9084 const double * rowUpper = getRowUpper(); 10042 /*10043 Scan the rows, looking for individual rows that are clique constraints.10044 */9085 /* 9086 Scan the rows, looking for individual rows that are clique constraints. 9087 */ 10045 9088 10046 9089 for (iRow = 0; iRow < numberRows; iRow++) { … … 10051 9094 bool good = true; 10052 9095 int slack = -1; 10053 /*10054 Does this row qualify? All variables must be binary and all coefficients10055 +/- 1.0. Variables with positive coefficients are recorded at the low end of10056 which, variables with negative coefficients the high end.10057 */9096 /* 9097 Does this row qualify? All variables must be binary and all coefficients 9098 +/- 1.0. Variables with positive coefficients are recorded at the low end of 9099 which, variables with negative coefficients the high end. 9100 */ 10058 9101 for (j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) { 10059 9102 int iColumn = column[j]; … … 10086 9129 int iUpper = static_cast<int> (floor(upperValue + 1.0e-5)); 10087 9130 int iLower = static_cast<int> (ceil(lowerValue - 1.0e-5)); 10088 /*10089 What do we have? If the row upper bound is greater than 1-numberM1, this10090 isn't a clique. If the row upper bound is 1-numberM1, we have the classic10091 clique (an SOS1 on binary variables, if numberM1 = 0). If the upper bound10092 equals numberM1, we can fix all variables. If the upper bound is less than10093 numberM1, we're infeasible.10094 10095 A similar analysis applies using numberP1 against the lower bound.10096 */9131 /* 9132 What do we have? If the row upper bound is greater than 1-numberM1, this 9133 isn't a clique. If the row upper bound is 1-numberM1, we have the classic 9134 clique (an SOS1 on binary variables, if numberM1 = 0). If the upper bound 9135 equals numberM1, we can fix all variables. If the upper bound is less than 9136 numberM1, we're infeasible. 9137 9138 A similar analysis applies using numberP1 against the lower bound. 9139 */ 10097 9140 int state = 0; 10098 9141 if (upperValue < 1.0e6) { … … 10112 9155 state = -3; 10113 9156 } 10114 /*10115 What to do? If we learned nothing, move on to the next iteration. If we're10116 infeasible, we're outta here. If we decided we can fix variables, do it.10117 */10118 if (good && state) {9157 /* 9158 What to do? If we learned nothing, move on to the next iteration. If we're 9159 infeasible, we're outta here. If we decided we can fix variables, do it. 9160 */ 9161 if (good && state) { 10119 9162 if (abs(state) == 3) { 10120 9163 // infeasible … … 10140 9183 } 10141 9184 } else { 10142 /*10143 And the final case: we have a clique constraint. If it's within the allowed10144 size range, make a clique object.10145 */9185 /* 9186 And the final case: we have a clique constraint. If it's within the allowed 9187 size range, make a clique object. 9188 */ 10146 9189 int length = numberP1 + numberM1; 10147 9190 if (length >= atLeastThisMany && length < lessThanThis) { … … 10149 9192 bool addOne = false; 10150 9193 int objectType; 10151 /*10152 Choose equality (type 1) or inequality (type 0). If we're forcing equalities,10153 add a slack.10154 */9194 /* 9195 Choose equality (type 1) or inequality (type 0). If we're forcing equalities, 9196 add a slack. 9197 */ 10155 9198 if (iLower == iUpper) { 10156 9199 objectType = 1; … … 10165 9208 } 10166 9209 } 10167 /*10168 Record the strong values for the variables. Variables with positive10169 coefficients force all others when set to 1; variables with negative10170 coefficients force when set to 0. If the clique is formed against the row10171 lower bound, convert to the canonical form of a clique against the row10172 upper bound.10173 */9210 /* 9211 Record the strong values for the variables. Variables with positive 9212 coefficients force all others when set to 1; variables with negative 9213 coefficients force when set to 0. If the clique is formed against the row 9214 lower bound, convert to the canonical form of a clique against the row 9215 upper bound. 9216 */ 10174 9217 if (state > 0) { 10175 9218 totalP1 += numberP1; … … 10236 9279 } 10237 9280 #endif 10238 /*10239 If required, augment the constraint matrix with clique slacks. Seems like we10240 should be able to add the necessary integer objects without a complete10241 rebuild of existing integer objects, but I'd need to look further to confirm10242 that (lh, 071219). Finally, add the clique objects.10243 */9281 /* 9282 If required, augment the constraint matrix with clique slacks. Seems like we 9283 should be able to add the necessary integer objects without a complete 9284 rebuild of existing integer objects, but I'd need to look further to confirm 9285 that (lh, 071219). Finally, add the clique objects. 9286 */ 10244 9287 if (numberCliques > 0 && numberSlacks && makeEquality) { 10245 9288 printf("adding %d integer slacks\n", numberSlacks); … … 10920 9963 //newObject->setNumberBeforeTrust(numberBeforeTrust_); 10921 9964 newObject->setPriority(priority); 9965 newObject->setPosition(iObject); 10922 9966 newObject->setPreferredWay(preferredWay); 10923 9967 object_[iObject] = newObject; … … 13096 12140 13097 12141 CBCMODEL_DEBUG: Seems like stateOfSearch_ should be 2 if 13098 12142 numberHeuristicSolutions_ == numberSolutions_. 13099 12143 13100 12144 */ … … 13150 12194 #endif 13151 12195 currentNode_ = newNode; // so can be used elsewhere 13152 /*13153 Enough preparation. Get down to the business of choosing a branching13154 variable.13155 */12196 /* 12197 Enough preparation. Get down to the business of choosing a branching 12198 variable. 12199 */ 13156 12200 while (anyAction == -1) { 13157 12201 // Set objective value (not so obvious if NLP etc) … … 13159 12203 //if (numberPassesLeft<=0) 13160 12204 //branchingState=1; 13161 /*13162 Is there a CbcBranchDecision object installed? Does it specify a13163 chooseVariable method? If not, we're using the old (Cbc) side of the branch13164 decision hierarchy. In quick summary, CbcNode::chooseBranch uses strong13165 branching on any objects, while CbcNode::chooseDynamicBranch uses dynamic13166 branching, but only on simple integers (-3 is the code for punt due to13167 complex objects). Serious bugs remain on the Cbc side, particularly in13168 chooseDynamicBranch.13169 */12205 /* 12206 Is there a CbcBranchDecision object installed? Does it specify a 12207 chooseVariable method? If not, we're using the old (Cbc) side of the branch 12208 decision hierarchy. In quick summary, CbcNode::chooseBranch uses strong 12209 branching on any objects, while CbcNode::chooseDynamicBranch uses dynamic 12210 branching, but only on simple integers (-3 is the code for punt due to 12211 complex objects). Serious bugs remain on the Cbc side, particularly in 12212 chooseDynamicBranch. 12213 */ 13170 12214 if (!branchingMethod_ || !branchingMethod_->chooseMethod()) { 13171 12215 #ifdef COIN_HAS_CLP … … 13203 12247 anyAction = newNode->chooseBranch(this, oldNode, numberPassesLeft) ; // dynamic did nothing 13204 12248 } 13205 /*13206 We're on the new (Osi) side of the branching hierarchy.13207 */12249 /* 12250 We're on the new (Osi) side of the branching hierarchy. 12251 */ 13208 12252 } else { 13209 12253 OsiBranchingInformation usefulInfo = usefulInformation(); … … 13300 12344 } 13301 12345 } 13302 /*13303 End main loop to choose a branching variable.13304 */12346 /* 12347 End main loop to choose a branching variable. 12348 */ 13305 12349 if (anyAction >= 0) { 13306 12350 if (resolved) { … … 13415 12459 if (cuts.sizeRowCuts()) { 13416 12460 int initialNumber = ((threadMode_ & 1) == 0) ? 0 : 1000000000; 13417 if (parallelMode() > 0) 13418 lockThread(); 12461 lockThread(); 13419 12462 newNode->nodeInfo()->addCuts(cuts, newNode->numberBranches(), 13420 12463 //whichGenerator_, 13421 12464 initialNumber) ; 13422 if (parallelMode() > 0) 13423 unlockThread(); 12465 unlockThread(); 13424 12466 } 13425 12467 } … … 13600 12642 int i; 13601 12643 if (deleteHeuristicsAfterwards != 2) { 13602 /*13603 If mode == 1, we delete and recreate here, then delete at the bottom. The13604 create/delete part makes sense, but why delete the existing array? Seems like13605 it should be preserved and restored.13606 */12644 /* 12645 If mode == 1, we delete and recreate here, then delete at the bottom. The 12646 create/delete part makes sense, but why delete the existing array? Seems like 12647 it should be preserved and restored. 12648 */ 13607 12649 if (deleteHeuristicsAfterwards) { 13608 12650 delete [] usedInSolution_; … … 13615 12657 if (eventHandler) 13616 12658 eventHandler->setModel(this); 13617 /*13618 currentPassNumber_ is described as `cut pass number'. Again, seems a bit13619 cavalier to just change it.13620 13621 Whether this has any effect is determined by individual heuristics. Typically13622 there will be a check at the front of the solution() routine that determines13623 whether it will run or simply return. Root heuristics are characterised by13624 node count of 0. In addition, currentPassNumber_ can be checked to to limit13625 execution in terms of passes through cut generation / heuristic execution in13626 solveWithCuts.13627 */12659 /* 12660 currentPassNumber_ is described as `cut pass number'. Again, seems a bit 12661 cavalier to just change it. 12662 12663 Whether this has any effect is determined by individual heuristics. Typically 12664 there will be a check at the front of the solution() routine that determines 12665 whether it will run or simply return. Root heuristics are characterised by 12666 node count of 0. In addition, currentPassNumber_ can be checked to to limit 12667 execution in terms of passes through cut generation / heuristic execution in 12668 solveWithCuts. 12669 */ 13628 12670 13629 12671 currentPassNumber_ = 1; // so root heuristics will run 13630 /*13631 A loop to run the heuristics. incrementUsed will mark entries in13632 usedInSolution corresponding to variables that are nonzero in the solution.13633 CBC_ROUNDING just identifies a message template, not the heuristic.13634 */12672 /* 12673 A loop to run the heuristics. incrementUsed will mark entries in 12674 usedInSolution corresponding to variables that are nonzero in the solution. 12675 CBC_ROUNDING just identifies a message template, not the heuristic. 12676 */ 13635 12677 // Modify based on size etc 13636 12678 adjustHeuristics(); … … 13643 12685 if (!exitNow) { 13644 12686 #ifdef CBC_THREAD 13645 if ((threadMode_& 8) != 0) {12687 if ((threadMode_&4) != 0) { 13646 12688 typedef struct { 13647 12689 double solutionValue; … … 13656 12698 chunk = numberThreads_; 13657 12699 for (int iChunk = 0; iChunk < numberHeuristics_; iChunk += chunk) { 13658 Coin_pthread_t * threadId = new Coin_pthread_t [chunk];13659 12700 argBundle * parameters = new argBundle [chunk]; 13660 12701 for (int i = 0; i < chunk; i++) 13661 12702 parameters[i].model = NULL; 13662 for (int i = iChunk; i < CoinMin(numberHeuristics_, iChunk + chunk); i++) { 12703 int nThisTime = CoinMin(numberHeuristics_ - iChunk, chunk); 12704 for (int i = iChunk; i < iChunk + nThisTime; i++) { 13663 12705 // skip if can't run here 13664 12706 if (!heuristic_[i]->shouldHeurRun(0)) … … 13682 12724 newModel->heuristic_[0]->resetModel(newModel); 13683 12725 newModel->numberHeuristics_ = 1; 13684 pthread_create(&(threadId[i-iChunk].thr), NULL, doHeurThread,13685 parameters + i - iChunk);13686 12726 } 13687 // now wait 13688 for (int i = 0; i < chunk; i++) { 13689 if (parameters[i].model) 13690 pthread_join(threadId[i].thr, NULL); 13691 } 12727 CbcSimpleThread(nThisTime, 0, static_cast<int>(sizeof(argBundle)), parameters); 13692 12728 double cutoff = heuristicValue; 13693 12729 for (int i = 0; i < chunk; i++) { … … 13720 12756 } 13721 12757 } 13722 delete [] threadId;13723 12758 delete [] parameters; 13724 12759 if (exitNow) … … 13778 12813 /* 13779 12814 Did any of the heuristics turn up a new solution? Record it before we free 13780 the vector. tree_ will not necessarily be a CbcTreeLocal; the main model gets13781 a CbcTree by default. CbcTreeLocal actually implements a k-neighbourhood13782 search heuristic. This initialises it with a solution and creates the13783 k-neighbourhood cut.12815 the vector. tree_ will not necessarily be a CbcTreeLocal; the main model gets 12816 a CbcTree by default. CbcTreeLocal actually implements a k-neighbourhood 12817 search heuristic. This initialises it with a solution and creates the 12818 k-neighbourhood cut. 13784 12819 */ 13785 12820 if (found >= 0) { … … 13795 12830 } 13796 12831 } 13797 /*13798 Cleanup. The feasibility pump heuristic is a root heuristic to look for an13799 initial feasible solution. It's had its chance; remove it.13800 13801 For modes 1 and 2, all the heuristics are deleted.13802 */12832 /* 12833 Cleanup. The feasibility pump heuristic is a root heuristic to look for an 12834 initial feasible solution. It's had its chance; remove it. 12835 12836 For modes 1 and 2, all the heuristics are deleted. 12837 */ 13803 12838 if (!deleteHeuristicsAfterwards) { 13804 12839 for (i = 0; i < numberHeuristics_; i++) { … … 14080 13115 bool feasible = true; 14081 13116 CoinWarmStartBasis *lastws = new CoinWarmStartBasis(); 14082 if (parallelMode() > 0) 14083 lockThread(); 13117 lockThread(); 14084 13118 // point to genuine ones 14085 13119 //int save1 = maximumNumberCuts_; … … 14112 13146 int branchesLeft = 0; 14113 13147 if (!retCode) { 14114 if (parallelMode() > 0) 14115 unlockThread(); 13148 unlockThread(); 14116 13149 int i ; 14117 13150 const double * lower = getColLower() ; … … 14125 13158 solverCharacteristics_->setBeforeUpper(upperBefore); 14126 13159 } 14127 if (parallelMode() > 0) 14128 lockThread(); 13160 lockThread(); 14129 13161 assert (node->objectiveValue() < 1.0e200); 14130 13162 if (messageHandler()->logLevel() > 2) … … 14148 13180 assert (branchesLeft == node->nodeInfo()->numberBranchesLeft()); 14149 13181 if (parallelMode() > 0) { 14150 assert(m utex_);13182 assert(masterThread_); 14151 13183 assert (node->nodeInfo()); 14152 13184 node->nodeInfo()->increment() ; … … 14808 13840 increment the reference count in the current (parent) nodeInfo. 14809 13841 */ 14810 if (parallelMode() > 0) 14811 lockThread(); 13842 lockThread(); 14812 13843 if (anyAction == -2) { 14813 13844 if (parallelMode() > 0) { 14814 assert (m utex_);13845 assert (masterThread_); 14815 13846 assert (node->nodeInfo()); 14816 13847 node->nodeInfo()->decrement() ; … … 14847 13878 } 14848 13879 } 14849 if (parallelMode() > 0) 14850 unlockThread(); 13880 unlockThread(); 14851 13881 } 14852 13882 /* … … 14879 13909 statistics_[numberNodes2_-1]->sayInfeasible(); 14880 13910 } 14881 if (parallelMode() > 0) 14882 lockThread(); 13911 lockThread(); 14883 13912 if (parallelMode() <= 0) { 14884 13913 if (numberUpdateItems_) { … … 14957 13986 } 14958 13987 } 14959 if (parallelMode() > 0) 14960 unlockThread(); 13988 unlockThread(); 14961 13989 14962 13990 double estValue = newNode->guessedObjectiveValue() ; … … 15006 14034 delete [] newSolution ; 15007 14035 newNode->setGuessedObjectiveValue(estValue) ; 15008 if (parallelMode() > 0) 15009 lockThread(); 14036 lockThread(); 15010 14037 if (parallelMode() >= 0) { 15011 if (!m utex_) // only if serial14038 if (!masterThread_) // only if serial 15012 14039 tree_->push(newNode) ; 15013 14040 } … … 15073 14100 node->nodeInfo()->setNodeNumber(numberNodes2_); 15074 14101 if (parallelMode() >= 0) { 15075 if (!m utex_) // only if serial14102 if (!masterThread_) // only if serial 15076 14103 tree_->push(node) ; 15077 14104 } … … 15106 14133 */ 15107 14134 if (parallelMode() > 0) { 15108 assert (m utex_) ;14135 assert (masterThread_) ; 15109 14136 assert (node->nodeInfo()); 15110 14137 node->nodeInfo()->decrement() ; … … 15120 14147 } 15121 14148 } 15122 if (parallelMode() > 0) 15123 unlockThread(); 14149 unlockThread(); 15124 14150 } else { 15125 14151 // add cuts found to be infeasible (on bound)! … … 15197 14223 } 15198 14224 updateItems_[numberUpdateItems_++] = data; 15199 }15200 #ifdef CBC_THREAD15201 // Split up nodes - returns number of CbcNodeInfo's affected15202 int15203 CbcModel::splitModel(int numberModels, CbcModel ** model,15204 int numberNodes)15205 {15206 int iModel;15207 int i;15208 for (iModel = 0; iModel < numberModels; iModel++) {15209 CbcModel * otherModel = model[iModel];15210 otherModel->moveToModel(this, 10);15211 assert (!otherModel->tree()->size());15212 otherModel->tree()->resetNodeNumbers();15213 otherModel->bestPossibleObjective_ = bestPossibleObjective_;15214 otherModel->sumChangeObjective1_ = sumChangeObjective1_;15215 otherModel->sumChangeObjective2_ = sumChangeObjective2_;15216 int numberColumns = solver_->getNumCols();15217 if (otherModel->bestSolution_) {15218 assert (bestSolution_);15219 memcpy(otherModel->bestSolution_, bestSolution_, numberColumns*sizeof(double));15220 } else if (bestSolution_) {15221 otherModel->bestSolution_ = CoinCopyOfArray(bestSolution_, numberColumns);15222 }15223 otherModel->globalCuts_ = globalCuts_;15224 otherModel->numberSolutions_ = numberSolutions_;15225 otherModel->numberHeuristicSolutions_ = numberHeuristicSolutions_;15226 otherModel->numberNodes_ = 1; //numberNodes_;15227 otherModel->numberIterations_ = numberIterations_;15228 #ifdef JJF_ZERO15229 if (maximumNumberCuts_ > otherModel->maximumNumberCuts_) {15230 otherModel->maximumNumberCuts_ = maximumNumberCuts_;15231 delete [] otherModel->addedCuts_;15232 otherModel->addedCuts_ = new CbcCountRowCut * [maximumNumberCuts_];15233 }15234 if (maximumDepth_ > otherModel->maximumDepth_) {15235 otherModel->maximumDepth_ = maximumDepth_;15236 delete [] otherModel->walkback_;15237 otherModel->walkback_ = new CbcNodeInfo * [maximumDepth_];15238 }15239 #endif15240 otherModel->currentNumberCuts_ = currentNumberCuts_;15241 if (otherModel->usedInSolution_) {15242 assert (usedInSolution_);15243 memcpy(otherModel->usedInSolution_, usedInSolution_, numberColumns*sizeof(int));15244 } else if (usedInSolution_) {15245 otherModel->usedInSolution_ = CoinCopyOfArray(usedInSolution_, numberColumns);15246 }15247 /// ??? tree_;15248 // Need flag (stopNumberIterations_>0?) which says don't update cut etc counts15249 for (i = 0; i < numberObjects_; i++) {15250 otherModel->object_[i]->updateBefore(object_[i]);15251 }15252 otherModel->maximumDepthActual_ = maximumDepthActual_;15253 // Real cuts are in node info15254 otherModel->numberOldActiveCuts_ = numberOldActiveCuts_;15255 otherModel->numberNewCuts_ = numberNewCuts_;15256 otherModel->numberStrongIterations_ = numberStrongIterations_;15257 }15258 double cutoff = getCutoff();15259 int nAffected = 0;15260 while (!tree_->empty()) {15261 for (iModel = 0; iModel < numberModels; iModel++) {15262 if (tree_->empty())15263 break;15264 CbcModel * otherModel = model[iModel];15265 CbcNode * node = tree_->bestNode(cutoff) ;15266 CbcNodeInfo * nodeInfo = node->nodeInfo();15267 assert (nodeInfo);15268 if (!nodeInfo->marked()) {15269 //while (nodeInfo&&!nodeInfo->marked()) {15270 if (nAffected == maximumDepth_) {15271 redoWalkBack();15272 }15273 nodeInfo->mark();15274 //nodeInfo->incrementCuts(1000000);15275 walkback_[nAffected++] = nodeInfo;15276 //nodeInfo = nodeInfo->parent() ;15277 //}15278 }15279 // Make node join otherModel15280 OsiBranchingObject * bobj = node->modifiableBranchingObject();15281 CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (bobj);15282 //assert (cbcobj);15283 if (cbcobj) {15284 CbcObject * object = cbcobj->object();15285 assert (object);15286 int position = object->position();15287 assert (position >= 0);15288 assert (object_[position] == object);15289 CbcObject * objectNew =15290 dynamic_cast<CbcObject *> (otherModel->object_[position]);15291 cbcobj->setOriginalObject(objectNew);15292 }15293 otherModel->tree_->push(node);15294 }15295 numberNodes--;15296 if (!numberNodes)15297 break;15298 }15299 return nAffected;15300 }15301 // Start threads15302 void15303 CbcModel::startSplitModel(int /*numberIterations*/)15304 {15305 abort();15306 }15307 // Merge models15308 void15309 CbcModel::mergeModels(int /*numberModel*/, CbcModel ** /*model*/,15310 int /*numberNodes*/)15311 {15312 abort();15313 }15314 /* Move/copy information from one model to another15315 -1 - initial setup15316 0 - from base model15317 1 - to base model (and reset)15318 2 - add in final statistics etc (and reset so can do clean destruction)15319 10 - from base model (deterministic)15320 11 - to base model (deterministic)15321 */15322 void15323 CbcModel::moveToModel(CbcModel * baseModel, int mode)15324 {15325 if (mode == 0) {15326 setCutoff(baseModel->getCutoff());15327 bestObjective_ = baseModel->bestObjective_;15328 assert (!baseModel->globalCuts_.sizeRowCuts());15329 numberSolutions_ = baseModel->numberSolutions_;15330 stateOfSearch_ = baseModel->stateOfSearch_;15331 numberNodes_ = baseModel->numberNodes_;15332 numberIterations_ = baseModel->numberIterations_;15333 numberFixedAtRoot_ = numberIterations_; // for statistics15334 numberSolves_ = 0;15335 phase_ = baseModel->phase_;15336 assert (!nextRowCut_);15337 nodeCompare_ = baseModel->nodeCompare_;15338 tree_ = baseModel->tree_;15339 assert (!subTreeModel_);15340 //branchingMethod_ = NULL; // need something but what15341 numberOldActiveCuts_ = baseModel->numberOldActiveCuts_;15342 cutModifier_ = NULL;15343 assert (!analyzeResults_);15344 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15345 assert (stuff);15346 //if (stuff)15347 stuff->createdNode = NULL;15348 // ?? searchStrategy_;15349 searchStrategy_ = baseModel->searchStrategy_;15350 stuff->saveStuff[0] = searchStrategy_;15351 stateOfSearch_ = baseModel->stateOfSearch_;15352 stuff->saveStuff[1] = stateOfSearch_;15353 for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) {15354 CbcSimpleIntegerDynamicPseudoCost * dynamicObject =15355 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object_[iObject]) ;15356 if (dynamicObject) {15357 CbcSimpleIntegerDynamicPseudoCost * baseObject =15358 dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(baseModel->object_[iObject]) ;15359 assert (baseObject);15360 dynamicObject->copySome(baseObject);15361 }15362 }15363 } else if (mode == 1) {15364 lockThread();15365 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15366 assert (stuff);15367 //stateOfSearch_15368 if (stuff->saveStuff[0] != searchStrategy_) {15369 #ifdef COIN_DEVELOP15370 printf("changing searchStrategy from %d to %d\n",15371 baseModel->searchStrategy_, searchStrategy_);15372 #endif15373 baseModel->searchStrategy_ = searchStrategy_;15374 }15375 if (stuff->saveStuff[1] != stateOfSearch_) {15376 #ifdef COIN_DEVELOP15377 printf("changing stateOfSearch from %d to %d\n",15378 baseModel->stateOfSearch_, stateOfSearch_);15379 #endif15380 baseModel->stateOfSearch_ = stateOfSearch_;15381 }15382 if (numberUpdateItems_) {15383 for (int i = 0; i < numberUpdateItems_; i++) {15384 CbcObjectUpdateData * update = updateItems_ + i;15385 int objectNumber = update->objectNumber_;15386 CbcObject * object = dynamic_cast<CbcObject *> (baseModel->object_[objectNumber]);15387 if (object)15388 object->updateInformation(*update);15389 }15390 numberUpdateItems_ = 0;15391 }15392 if (eventHappened_)15393 baseModel->eventHappened_ = true;15394 baseModel->numberNodes_++;15395 baseModel->numberIterations_ +=15396 numberIterations_ - numberFixedAtRoot_;15397 baseModel->numberSolves_ += numberSolves_;15398 if (stuff->node)15399 baseModel->tree_->push(stuff->node);15400 if (stuff->createdNode)15401 baseModel->tree_->push(stuff->createdNode);15402 unlockThread();15403 } else if (mode == 2) {15404 baseModel->sumChangeObjective1_ += sumChangeObjective1_;15405 baseModel->sumChangeObjective2_ += sumChangeObjective2_;15406 //baseModel->numberIterations_ += numberIterations_;15407 for (int iGenerator = 0; iGenerator < numberCutGenerators_; iGenerator++) {15408 CbcCutGenerator * generator = baseModel->generator_[iGenerator];15409 CbcCutGenerator * generator2 = generator_[iGenerator];15410 generator->incrementNumberTimesEntered(generator2->numberTimesEntered());15411 generator->incrementNumberCutsInTotal(generator2->numberCutsInTotal());15412 generator->incrementNumberCutsActive(generator2->numberCutsActive());15413 generator->incrementTimeInCutGenerator(generator2->timeInCutGenerator());15414 }15415 if (parallelMode() >= 0)15416 nodeCompare_ = NULL;15417 baseModel->maximumDepthActual_ = CoinMax(baseModel->maximumDepthActual_, maximumDepthActual_);15418 baseModel->numberDJFixed_ += numberDJFixed_;15419 baseModel->numberStrongIterations_ += numberStrongIterations_;15420 int i;15421 for (i = 0; i < 3; i++)15422 baseModel->strongInfo_[i] += strongInfo_[i];15423 if (parallelMode() >= 0) {15424 walkback_ = NULL;15425 lastNodeInfo_ = NULL;15426 lastNumberCuts_ = NULL;15427 lastCut_ = NULL;15428 //addedCuts_ = NULL;15429 tree_ = NULL;15430 }15431 eventHandler_ = NULL;15432 delete solverCharacteristics_;15433 solverCharacteristics_ = NULL;15434 bool newMethod = (baseModel->branchingMethod_ && baseModel->branchingMethod_->chooseMethod());15435 if (newMethod) {15436 // new method - we were using base models15437 numberObjects_ = 0;15438 object_ = NULL;15439 }15440 } else if (mode == -1) {15441 delete eventHandler_;15442 eventHandler_ = baseModel->eventHandler_;15443 assert (!statistics_);15444 assert(baseModel->solverCharacteristics_);15445 solverCharacteristics_ = new OsiBabSolver (*baseModel->solverCharacteristics_);15446 solverCharacteristics_->setSolver(solver_);15447 setMaximumNodes(COIN_INT_MAX);15448 if (parallelMode() >= 0) {15449 delete [] walkback_;15450 //delete [] addedCuts_;15451 walkback_ = NULL;15452 //addedCuts_ = NULL;15453 delete [] lastNodeInfo_ ;15454 lastNodeInfo_ = NULL;15455 delete [] lastNumberCuts_ ;15456 lastNumberCuts_ = NULL;15457 delete [] lastCut_ ;15458 lastCut_ = NULL;15459 delete tree_;15460 tree_ = NULL;15461 delete nodeCompare_;15462 nodeCompare_ = NULL;15463 } else {15464 delete tree_;15465 tree_ = new CbcTree();15466 tree_->setComparison(*nodeCompare_) ;15467 }15468 continuousSolver_ = baseModel->continuousSolver_->clone();15469 bool newMethod = (baseModel->branchingMethod_ && baseModel->branchingMethod_->chooseMethod());15470 if (newMethod) {15471 // new method uses solver - but point to base model15472 // We may update an object in wrong order - shouldn't matter?15473 numberObjects_ = baseModel->numberObjects_;15474 if (parallelMode() >= 0) {15475 object_ = baseModel->object_;15476 } else {15477 printf("*****WARNING - fix testosi option\n");15478 object_ = baseModel->object_;15479 }15480 }15481 mutex_ = baseModel->mutex_;15482 int i;15483 for (i = 0; i < numberHeuristics_; i++) {15484 delete heuristic_[i];15485 heuristic_[i] = baseModel->heuristic_[i]->clone();15486 heuristic_[i]->setModelOnly(this);15487 }15488 for (i = 0; i < numberCutGenerators_; i++) {15489 delete generator_[i];15490 generator_[i] = new CbcCutGenerator(*baseModel->generator_[i]);15491 // refreshModel was overkill as thought too many rows15492 generator_[i]->setModel(this);15493 }15494 } else if (mode == 10) {15495 setCutoff(baseModel->getCutoff());15496 bestObjective_ = baseModel->bestObjective_;15497 assert (!baseModel->globalCuts_.sizeRowCuts());15498 numberSolutions_ = baseModel->numberSolutions_;15499 assert (usedInSolution_);15500 assert (baseModel->usedInSolution_);15501 memcpy(usedInSolution_, baseModel->usedInSolution_, solver_->getNumCols()*sizeof(int));15502 stateOfSearch_ = baseModel->stateOfSearch_;15503 //numberNodes_ = baseModel->numberNodes_;15504 //numberIterations_ = baseModel->numberIterations_;15505 //numberFixedAtRoot_ = numberIterations_; // for statistics15506 phase_ = baseModel->phase_;15507 assert (!nextRowCut_);15508 delete nodeCompare_;15509 nodeCompare_ = baseModel->nodeCompare_->clone();15510 tree_->setComparison(*nodeCompare_) ;15511 assert (!subTreeModel_);15512 //branchingMethod_ = NULL; // need something but what15513 numberOldActiveCuts_ = baseModel->numberOldActiveCuts_;15514 cutModifier_ = NULL;15515 assert (!analyzeResults_);15516 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15517 assert (stuff);15518 //if (stuff)15519 stuff->createdNode = NULL;15520 // ?? searchStrategy_;15521 searchStrategy_ = baseModel->searchStrategy_;15522 stuff->saveStuff[0] = searchStrategy_;15523 stateOfSearch_ = baseModel->stateOfSearch_;15524 stuff->saveStuff[1] = stateOfSearch_;15525 OsiObject ** baseObject = baseModel->object_;15526 for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) {15527 object_[iObject]->updateBefore(baseObject[iObject]);15528 }15529 //delete [] stuff->nodeCount;15530 //stuff->nodeCount = new int [baseModel->maximumDepth_+1];15531 } else if (mode == 11) {15532 if (parallelMode() < 0) {15533 // from deterministic15534 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15535 assert (stuff);15536 // Move solution etc15537 // might as well mark all including continuous15538 int numberColumns = solver_->getNumCols();15539 for (int i = 0; i < numberColumns; i++) {15540 baseModel->usedInSolution_[i] += usedInSolution_[i];15541 //usedInSolution_[i]=0;15542 }15543 baseModel->numberSolutions_ += numberSolutions_;15544 if (bestObjective_ < baseModel->bestObjective_ && bestObjective_ < baseModel->getCutoff()) {15545 baseModel->bestObjective_ = bestObjective_ ;15546 int numberColumns = solver_->getNumCols();15547 if (!baseModel->bestSolution_)15548 baseModel->bestSolution_ = new double[numberColumns];15549 CoinCopyN(bestSolution_, numberColumns, baseModel->bestSolution_);15550 baseModel->setCutoff(getCutoff());15551 }15552 //stateOfSearch_15553 if (stuff->saveStuff[0] != searchStrategy_) {15554 #ifdef COIN_DEVELOP15555 printf("changing searchStrategy from %d to %d\n",15556 baseModel->searchStrategy_, searchStrategy_);15557 #endif15558 baseModel->searchStrategy_ = searchStrategy_;15559 }15560 if (stuff->saveStuff[1] != stateOfSearch_) {15561 #ifdef COIN_DEVELOP15562 printf("changing stateOfSearch from %d to %d\n",15563 baseModel->stateOfSearch_, stateOfSearch_);15564 #endif15565 baseModel->stateOfSearch_ = stateOfSearch_;15566 }15567 int i;15568 if (eventHappened_)15569 baseModel->eventHappened_ = true;15570 baseModel->numberNodes_ += stuff->nodesThisTime;15571 baseModel->numberIterations_ += stuff->iterationsThisTime;15572 double cutoff = baseModel->getCutoff();15573 while (!tree_->empty()) {15574 CbcNode * node = tree_->bestNode(COIN_DBL_MAX) ;15575 if (node->objectiveValue() < cutoff) {15576 assert(node->nodeInfo());15577 // Make node join correctly15578 OsiBranchingObject * bobj = node->modifiableBranchingObject();15579 CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (bobj);15580 if (cbcobj) {15581 CbcObject * object = cbcobj->object();15582 assert (object);15583 int position = object->position();15584 assert (position >= 0);15585 assert (object_[position] == object);15586 CbcObject * objectNew =15587 dynamic_cast<CbcObject *> (baseModel->object_[position]);15588 cbcobj->setOriginalObject(objectNew);15589 }15590 baseModel->tree_->push(node);15591 } else {15592 delete node;15593 }15594 }15595 for (i = 0; i < stuff->nDeleteNode; i++) {15596 //printf("CbcNode %x stuff delete\n",stuff->delNode[i]);15597 delete stuff->delNode[i];15598 }15599 }15600 } else {15601 abort();15602 }15603 }15604 #ifdef CBC_THREAD15605 static void * doNodesThread(void * voidInfo)15606 {15607 threadStruct * stuff = reinterpret_cast<threadStruct *> (voidInfo);15608 pthread_mutex_t * mutex = stuff->mutex2;15609 pthread_cond_t * condition = stuff->condition2;15610 CbcModel * thisModel = stuff->thisModel;15611 CbcModel * baseModel = stuff->baseModel;15612 while (true) {15613 pthread_mutex_lock (mutex);15614 while (stuff->returnCode) {15615 struct timespec absTime2;15616 my_gettime(&absTime2);15617 double time2 = absTime2.tv_sec + 1.0e-9 * absTime2.tv_nsec;15618 // timed wait as seems to hang on max nodes at times15619 absTime2.tv_sec += 10;15620 pthread_cond_timedwait(condition, mutex, &absTime2);15621 my_gettime(&stuff->absTime);15622 double time = stuff->absTime.tv_sec + 1.0e-9 * stuff->absTime.tv_nsec;15623 stuff->timeWaitingToStart += time - time2;;15624 stuff->numberTimesWaitingToStart++;15625 }15626 //printf("start node %x\n",stuff->node);15627 int mode = thisModel->getNumberThreads();15628 if (mode) {15629 // normal15630 double time2 = CoinCpuTime();15631 assert (stuff->returnCode == 0);15632 if (thisModel->parallelMode() >= 0) {15633 assert (stuff->node->nodeInfo());15634 thisModel->doOneNode(baseModel, stuff->node, stuff->createdNode);15635 stuff->returnCode = 1;15636 } else {15637 assert (!stuff->node);15638 assert (!stuff->createdNode);15639 int numberIterations = stuff->nDeleteNode;15640 int nDeleteNode = 0;15641 int maxDeleteNode = stuff->maxDeleteNode;15642 CbcNode ** delNode = stuff->delNode;15643 int returnCode = 1;15644 // this should be updated by heuristics strong branching etc etc15645 assert (numberIterations > 0);15646 thisModel->setNumberThreads(0);15647 int nodesThisTime = thisModel->getNodeCount();15648 int iterationsThisTime = thisModel->getIterationCount();15649 int strongThisTime = thisModel->numberStrongIterations();15650 thisModel->setStopNumberIterations(thisModel->getIterationCount() + numberIterations);15651 int numberColumns = thisModel->getNumCols();15652 int * used = CoinCopyOfArray(thisModel->usedInSolution(), numberColumns);15653 int numberSolutions = thisModel->getSolutionCount();15654 while (true) {15655 if (thisModel->tree()->empty()) {15656 returnCode = 1 + 1;15657 #ifdef CLP_INVESTIGATE_215658 printf("%x tree empty - time %18.6f\n", thisModel, CoinGetTimeOfDay() - 1.2348e9);15659 #endif15660 break;15661 }15662 #define NODE_ITERATIONS 215663 int nodesNow = thisModel->getNodeCount();15664 int iterationsNow = thisModel->getIterationCount();15665 int strongNow = thisModel->numberStrongIterations();15666 bool exit1 = (NODE_ITERATIONS * ((nodesNow - nodesThisTime) +15667 ((strongNow - strongThisTime) >> 1)) +15668 (iterationsNow - iterationsThisTime) > numberIterations);15669 //bool exit2 =(thisModel->getIterationCount()>thisModel->getStopNumberIterations()) ;15670 //assert (exit1==exit2);15671 if (exit1 && nodesNow - nodesThisTime >= 10) {15672 // out of loop15673 //printf("out of loop\n");15674 #ifdef CLP_INVESTIGATE315675 printf("%x tree %d nodes left, done %d and %d its - time %18.6f\n", thisModel,15676 thisModel->tree()->size(), nodesNow - nodesThisTime,15677 iterationsNow - iterationsThisTime, CoinGetTimeOfDay() - 1.2348e9);15678 #endif15679 break;15680 }15681 double cutoff = thisModel->getCutoff() ;15682 CbcNode *node = thisModel->tree()->bestNode(cutoff) ;15683 // Possible one on tree worse than cutoff15684 if (!node)15685 continue;15686 CbcNode * createdNode = NULL;15687 // Do real work of node15688 thisModel->doOneNode(NULL, node, createdNode);15689 assert (createdNode);15690 if (!createdNode->active()) {15691 delete createdNode;15692 } else {15693 // Say one more pointing to this **** postpone if marked15694 node->nodeInfo()->increment() ;15695 thisModel->tree()->push(createdNode) ;15696 }15697 if (node->active()) {15698 assert (node->nodeInfo());15699 if (node->nodeInfo()->numberBranchesLeft()) {15700 thisModel->tree()->push(node) ;15701 } else {15702 node->setActive(false);15703 }15704 } else {15705 if (node->nodeInfo()) {15706 if (!node->nodeInfo()->numberBranchesLeft())15707 node->nodeInfo()->allBranchesGone(); // can clean up15708 // So will delete underlying stuff15709 node->setActive(true);15710 }15711 if (nDeleteNode == maxDeleteNode) {15712 maxDeleteNode = (3 * maxDeleteNode) / 2 + 10;15713 stuff->maxDeleteNode = maxDeleteNode;15714 stuff->delNode = new CbcNode * [maxDeleteNode];15715 for (int i = 0; i < nDeleteNode; i++)15716 stuff->delNode[i] = delNode[i];15717 delete [] delNode;15718 delNode = stuff->delNode;15719 }15720 delNode[nDeleteNode++] = node;15721 }15722 }15723 // end of this sub-tree15724 int * usedA = thisModel->usedInSolution();15725 for (int i = 0; i < numberColumns; i++) {15726 usedA[i] -= used[i];15727 }15728 delete [] used;15729 thisModel->setSolutionCount(thisModel->getSolutionCount() - numberSolutions);15730 stuff->nodesThisTime = thisModel->getNodeCount() - nodesThisTime;15731 stuff->iterationsThisTime = thisModel->getIterationCount() - iterationsThisTime;15732 stuff->nDeleteNode = nDeleteNode;15733 stuff->returnCode = returnCode;15734 thisModel->setNumberThreads(mode);15735 }15736 //printf("end node %x\n",stuff->node);15737 threadStruct * stuffMain = reinterpret_cast<threadStruct *> (baseModel->mutex());15738 //pthread_mutex_t * condition_mutex = stuffMain->mutex2;15739 pthread_cond_t * condition_main = stuffMain->condition2;15740 pthread_cond_signal(condition_main); // unlock15741 pthread_mutex_unlock(mutex);15742 stuff->timeInThread += CoinCpuTime() - time2;15743 } else {15744 // exit15745 break;15746 }15747 }15748 pthread_mutex_unlock(mutex);15749 pthread_exit(NULL);15750 return NULL;15751 }15752 static void * doHeurThread(void * voidInfo)15753 {15754 typedef struct {15755 double solutionValue;15756 CbcModel * model;15757 double * solution;15758 int foundSol;15759 } argBundle;15760 argBundle * stuff = reinterpret_cast<argBundle *> (voidInfo);15761 stuff->foundSol =15762 stuff->model->heuristic(0)->solution(stuff->solutionValue,15763 stuff->solution);15764 pthread_exit(NULL);15765 return NULL;15766 }15767 static void * doCutsThread(void * voidInfo)15768 {15769 threadStruct * stuff = reinterpret_cast<threadStruct *> (voidInfo);15770 pthread_mutex_t * mutex = stuff->mutex2;15771 pthread_cond_t * condition = stuff->condition2;15772 CbcModel * thisModel = stuff->thisModel;15773 CbcModel * baseModel = stuff->baseModel;15774 while (true) {15775 pthread_mutex_lock(mutex);15776 while (stuff->returnCode) {15777 pthread_cond_wait(condition, mutex);15778 }15779 //printf("start node %x\n",stuff->node);15780 int mode = thisModel->getNumberThreads();15781 if (mode) {15782 // normal15783 assert (stuff->returnCode == 0);15784 int fullScan = thisModel->getNodeCount() == 0 ? 1 : 0; //? was >015785 CbcCutGenerator * generator = thisModel->cutGenerator(0);15786 OsiCuts * cuts = reinterpret_cast<OsiCuts *> (thisModel->objects());15787 OsiSolverInterface * thisSolver = thisModel->solver();15788 generator->generateCuts(*cuts, fullScan, thisSolver, NULL);15789 stuff->returnCode = 1;15790 //printf("end node %x\n",stuff->node);15791 threadStruct * stuffMain = reinterpret_cast<threadStruct *> (baseModel->mutex());15792 //pthread_mutex_t * condition_mutex = stuffMain->mutex2;15793 pthread_cond_t * condition_main = stuffMain->condition2;15794 pthread_cond_signal(condition_main); // unlock15795 pthread_mutex_unlock(mutex);15796 } else {15797 // exit15798 break;15799 }15800 }15801 pthread_mutex_unlock(mutex);15802 pthread_exit(NULL);15803 return NULL;15804 }15805 #endif15806 #endif15807 #ifdef CBC_THREAD15808 /*15809 Locks a thread if parallel so that stuff like cut pool15810 can be updated and/or used.15811 */15812 void15813 CbcModel::lockThread()15814 {15815 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15816 if (stuff) {15817 if (!stuff->locked) {15818 struct timespec absTime2;15819 my_gettime(&absTime2);15820 double time2 = absTime2.tv_sec + 1.0e-9 * absTime2.tv_nsec;15821 pthread_mutex_lock (stuff->mutex);15822 stuff->locked = true;15823 my_gettime(&stuff->absTime);15824 double time = stuff->absTime.tv_sec + 1.0e-9 * stuff->absTime.tv_nsec;15825 stuff->timeWaitingToLock += time - time2;;15826 stuff->numberTimesLocked++;15827 }15828 }15829 }15830 /*15831 Unlocks a thread if parallel15832 */15833 void15834 CbcModel::unlockThread()15835 {15836 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15837 if (stuff) {15838 if (stuff->locked) {15839 stuff->locked = false;15840 pthread_mutex_unlock (stuff->mutex);15841 struct timespec absTime2;15842 my_gettime(&absTime2);15843 double time2 = absTime2.tv_sec + 1.0e-9 * absTime2.tv_nsec;15844 double time = stuff->absTime.tv_sec + 1.0e-9 * stuff->absTime.tv_nsec;15845 stuff->timeLocked += time2 - time;15846 stuff->numberTimesUnlocked++;15847 }15848 }15849 }15850 #endif15851 // Returns true if locked15852 bool15853 CbcModel::isLocked() const15854 {15855 #ifdef CBC_THREAD15856 threadStruct * stuff = reinterpret_cast<threadStruct *> (mutex_);15857 if (stuff) {15858 return (stuff->locked);15859 } else {15860 return true;15861 }15862 #else15863 return true;15864 #endif15865 14225 } 15866 14226 // Returns bounds just before where - initially original bounds - also sets bounds … … 16219 14579 } 16220 14580 } 14581 #ifdef COIN_HAS_CLP 14582 void 14583 CbcModel::goToDantzig(int numberNodes, ClpDualRowPivot *& savePivotMethod) 14584 { 14585 // Possible change of pivot method 14586 if (!savePivotMethod && !parentModel_) { 14587 OsiClpSolverInterface * clpSolver 14588 = dynamic_cast<OsiClpSolverInterface *> (solver_); 14589 if (clpSolver && numberNodes_ >= numberNodes && numberNodes_ < 2*numberNodes) { 14590 if (numberIterations_ < (numberSolves_ + numberNodes_)*10) { 14591 //if (numberIterations_<numberNodes_*20) { 14592 ClpSimplex * simplex = clpSolver->getModelPtr(); 14593 ClpDualRowPivot * pivotMethod = simplex->dualRowPivot(); 14594 ClpDualRowDantzig * pivot = 14595 dynamic_cast< ClpDualRowDantzig*>(pivotMethod); 14596 if (!pivot) { 14597 savePivotMethod = pivotMethod->clone(true); 14598 ClpDualRowDantzig dantzig; 14599 simplex->setDualRowPivotAlgorithm(dantzig); 14600 #ifdef COIN_DEVELOP 14601 printf("%d node, %d iterations ->Dantzig\n", numberNodes_, 14602 numberIterations_); 14603 #endif 14604 #ifdef CBC_THREAD 14605 if (master_) 14606 master_->setDantzigState(); 14607 #endif 14608 } 14609 } 14610 } 14611 } 14612 } 14613 #endif 16221 14614 // Below this is deprecated or at least fairly deprecated 16222 14615 /* -
branches/sandbox/Cbc/src/CbcModel.hpp
r1400 r1409 20 20 21 21 class CbcCutGenerator; 22 class CbcBaseModel; 22 23 class OsiRowCut; 23 24 class OsiBabSolver; … … 29 30 class CbcHeuristic; 30 31 class OsiObject; 32 class CbcThread; 31 33 class CbcTree; 32 34 class CbcStrategy; … … 222 224 */ 223 225 bool solveWithCuts(OsiCuts & cuts, int numberTries, CbcNode * node); 226 /** Generate one round of cuts - serial mode 227 returns - 228 0 - normal 229 1 - must keep going 230 2 - set numberTries to zero 231 -1 - infeasible 232 */ 233 int serialCuts(OsiCuts & cuts, CbcNode * node, OsiCuts & slackCuts, int lastNumberCuts); 234 /** Generate one round of cuts - parallel mode 235 returns - 236 0 - normal 237 1 - must keep going 238 2 - set numberTries to zero 239 -1 - infeasible 240 */ 241 int parallelCuts(CbcBaseModel * master, OsiCuts & cuts, CbcNode * node, OsiCuts & slackCuts, int lastNumberCuts); 224 242 /** Input one node output N nodes to put on tree and optional solution update 225 243 This should be able to operate in parallel so is given a solver and is const(ish) … … 309 327 int doOneNode(CbcModel * baseModel, CbcNode * & node, CbcNode * & newNode); 310 328 311 /// Returns true if locked312 bool isLocked() const;313 #ifdef CBC_THREAD314 /**315 Locks a thread if parallel so that stuff like cut pool316 can be updated and/or used.317 */318 void lockThread();319 /**320 Unlocks a thread if parallel to say cut pool stuff not needed321 */322 void unlockThread();323 #else324 inline void lockThread() {}325 inline void unlockThread() {}326 #endif327 private:328 /** Move/copy information from one model to another329 -1 - initialization330 0 - from base model331 1 - to base model (and reset)332 2 - add in final statistics etc (and reset so can do clean destruction)333 */334 void moveToModel(CbcModel * baseModel, int mode);335 329 public: 336 330 /** \brief Reoptimise an LP relaxation … … 1378 1372 return workingBasis_; 1379 1373 } 1380 /// Get number of threads1381 inline int getNumberThreads() const {1382 return numberThreads_;1383 }1384 /// Set number of threads1385 inline void setNumberThreads(int value) {1386 numberThreads_ = value;1387 }1388 /// Get thread mode1389 inline int getThreadMode() const {1390 return threadMode_;1391 }1392 /** Set thread mode1393 always use numberThreads for branching1394 1 set then deterministic1395 2 set then use numberThreads for root cuts1396 4 set then use numberThreads in root mini branch and bound1397 8 set and numberThreads - do heuristics numberThreads at a time1398 8 set and numberThreads==0 do all heuristics at once1399 default is 01400 */1401 inline void setThreadMode(int value) {1402 threadMode_ = value;1403 }1404 /** Return1405 -2 if deterministic threaded and main thread1406 -1 if deterministic threaded and serial thread1407 0 if serial1408 1 if opportunistic threaded1409 */1410 inline int parallelMode() const {1411 if (!numberThreads_) {1412 if ((threadMode_&1) == 0)1413 return 0;1414 else1415 return -1;1416 return 0;1417 } else {1418 if ((threadMode_&1) == 0)1419 return 1;1420 else1421 return -2;1422 }1423 }1424 1374 /// Get number of "iterations" to stop after 1425 1375 inline int getStopNumberIterations() const { … … 1593 1543 /// Set the strategy. Clones 1594 1544 void setStrategy(CbcStrategy & strategy); 1545 /// Set the strategy. assigns 1546 inline void setStrategy(CbcStrategy * strategy) { 1547 strategy_ = strategy; 1548 } 1595 1549 /// Get the current parent model 1596 1550 inline CbcModel * parentModel() const { … … 1701 1655 //--------------------------------------------------------------------------- 1702 1656 1703 /**@name Message handling */1657 /**@name Message handling etc */ 1704 1658 //@{ 1705 1659 /// Pass in Message handler (not deleted at end) … … 1727 1681 inline int logLevel() const { 1728 1682 return handler_->logLevel(); 1683 } 1684 /** Set flag to say if handler_ is the default handler. 1685 1686 The default handler is deleted when the model is deleted. Other 1687 handlers (supplied by the client) will not be deleted. 1688 */ 1689 inline void setDefaultHandler(bool yesNo) { 1690 defaultHandler_ = yesNo; 1729 1691 } 1730 1692 //@} … … 1779 1741 return moreSpecialOptions_; 1780 1742 } 1743 /// Go to dantzig pivot selection if easy problem (clp only) 1744 #ifdef COIN_HAS_CLP 1745 void goToDantzig(int numberNodes, ClpDualRowPivot *& savePivotMethod); 1746 #endif 1781 1747 /// Now we may not own objects - just point to solver's objects 1782 1748 inline bool ownObjects() const { … … 1785 1751 /// Check original model before it gets messed up 1786 1752 void checkModel(); 1787 /// Pointer to a mutex1788 inline void * mutex() {1789 return mutex_;1790 }1791 /// Split up nodes1792 int splitModel(int numberModels, CbcModel ** model,1793 int numberNodes);1794 /// Start threads1795 void startSplitModel(int numberIterations);1796 /// Merge models1797 void mergeModels(int numberModel, CbcModel ** model,1798 int numberNodes);1799 1753 //@} 1800 1754 //--------------------------------------------------------------------------- … … 1911 1865 /// Move status, nodes etc etc across 1912 1866 void moveInfo(const CbcModel & rhs); 1867 //@} 1868 1869 /// To do with threads 1870 //@{ 1871 /// Get pointer to masterthread 1872 CbcThread * masterThread() const { 1873 return masterThread_; 1874 } 1875 /// Get pointer to walkback 1876 CbcNodeInfo ** walkback() const { 1877 return walkback_; 1878 } 1879 /// Get number of threads 1880 inline int getNumberThreads() const { 1881 return numberThreads_; 1882 } 1883 /// Set number of threads 1884 inline void setNumberThreads(int value) { 1885 numberThreads_ = value; 1886 } 1887 /// Get thread mode 1888 inline int getThreadMode() const { 1889 return threadMode_; 1890 } 1891 /** Set thread mode 1892 always use numberThreads for branching 1893 1 set then deterministic 1894 2 set then use numberThreads for root cuts 1895 4 set then use numberThreads in root mini branch and bound 1896 8 set and numberThreads - do heuristics numberThreads at a time 1897 8 set and numberThreads==0 do all heuristics at once 1898 default is 0 1899 */ 1900 inline void setThreadMode(int value) { 1901 threadMode_ = value; 1902 } 1903 /** Return 1904 -2 if deterministic threaded and main thread 1905 -1 if deterministic threaded and serial thread 1906 0 if serial 1907 1 if opportunistic threaded 1908 */ 1909 inline int parallelMode() const { 1910 if (!numberThreads_) { 1911 if ((threadMode_&1) == 0) 1912 return 0; 1913 else 1914 return -1; 1915 return 0; 1916 } else { 1917 if ((threadMode_&1) == 0) 1918 return 1; 1919 else 1920 return -2; 1921 } 1922 } 1923 /// From here to end of section - code in CbcThread.cpp until class changed 1924 /// Returns true if locked 1925 bool isLocked() const; 1926 #ifdef CBC_THREAD 1927 /** 1928 Locks a thread if parallel so that stuff like cut pool 1929 can be updated and/or used. 1930 */ 1931 void lockThread(); 1932 /** 1933 Unlocks a thread if parallel to say cut pool stuff not needed 1934 */ 1935 void unlockThread(); 1936 #else 1937 inline void lockThread() {} 1938 inline void unlockThread() {} 1939 #endif 1940 /** Set information in a child 1941 -3 pass pointer to child thread info 1942 -2 just stop 1943 -1 delete simple child stuff 1944 0 delete opportunistic child stuff 1945 1 delete deterministic child stuff 1946 */ 1947 void setInfoInChild(int type, CbcThread * info); 1948 /** Move/copy information from one model to another 1949 -1 - initialization 1950 0 - from base model 1951 1 - to base model (and reset) 1952 2 - add in final statistics etc (and reset so can do clean destruction) 1953 */ 1954 void moveToModel(CbcModel * baseModel, int mode); 1955 /// Split up nodes 1956 int splitModel(int numberModels, CbcModel ** model, 1957 int numberNodes); 1958 /// Start threads 1959 void startSplitModel(int numberIterations); 1960 /// Merge models 1961 void mergeModels(int numberModel, CbcModel ** model, 1962 int numberNodes); 1913 1963 //@} 1914 1964 … … 2426 2476 /// Pointer to user-defined data structure 2427 2477 void * appData_; 2428 /// Pointer to a mutex2429 void * mutex_;2430 2478 /// Presolve for CbcTreeLocal 2431 2479 int presolve_; … … 2612 2660 */ 2613 2661 int threadMode_; 2662 /// Thread stuff for master 2663 CbcBaseModel * master_; 2664 /// Pointer to masterthread 2665 CbcThread * masterThread_; 2614 2666 //@} 2615 2667 }; -
branches/sandbox/Cbc/src/CbcNode.cpp
r1406 r1409 2802 2802 solver->unmarkHotStart(); 2803 2803 } 2804 model->setLogLevel(saveLogLevel); 2804 2805 model->setBestSolution(CBC_STRONGSOL, 2805 2806 newObjectiveValue, … … 2857 2858 #endif 2858 2859 double objValue = solver->getObjValue(); 2860 model->setLogLevel(saveLogLevel); 2859 2861 model->setBestSolution(CBC_STRONGSOL, 2860 2862 objValue, … … 2950 2952 solver->unmarkHotStart(); 2951 2953 } 2954 model->setLogLevel(saveLogLevel); 2952 2955 model->setBestSolution(CBC_STRONGSOL, 2953 2956 newObjectiveValue, … … 2999 3002 numberObjectInfeasibilities)) { 3000 3003 double objValue = solver->getObjValue(); 3004 model->setLogLevel(saveLogLevel); 3001 3005 model->setBestSolution(CBC_STRONGSOL, 3002 3006 objValue, … … 3530 3534 double objMax = -1.0e50; 3531 3535 bool needResolve = false; 3532 /*3533 Now calculate the cost forcing the variable up and down.3534 */3536 /* 3537 Now calculate the cost forcing the variable up and down. 3538 */ 3535 3539 int iDo; 3536 3540 for (iDo = 0; iDo < numberToDo; iDo++) { … … 3544 3548 int iColumn = dynamicObject->columnNumber(); 3545 3549 int preferredWay; 3546 /*3547 Update the information held in the object.3548 */3550 /* 3551 Update the information held in the object. 3552 */ 3549 3553 object->infeasibility(&usefulInfo, preferredWay); 3550 3554 double value = currentSolution[iColumn]; -
branches/sandbox/Cbc/src/CbcThread.cpp
r1404 r1409 1 /* $Id: Cbc Model.cpp 1261 2009-10-30 12:45:20Z forrest $ */1 /* $Id: CbcThread.cpp 1261 2009-10-30 12:45:20Z forrest $ */ 2 2 // Copyright (C) 2002, International Business Machines 3 3 // Corporation and others. All Rights Reserved. … … 17 17 18 18 #include "OsiSolverInterface.hpp" 19 #include "OsiRowCutDebugger.hpp" 19 20 #include "CbcThread.hpp" 21 #include "CbcTree.hpp" 22 #include "CbcHeuristic.hpp" 23 #include "CbcCutGenerator.hpp" 20 24 #include "CbcModel.hpp" 21 25 #include "CbcFathom.hpp" 26 #include "CbcSimpleIntegerDynamicPseudoCost.hpp" 27 #include "ClpDualRowDantzig.hpp" 28 #include "OsiAuxInfo.hpp" 22 29 23 30 #include "CoinTime.hpp" 31 #ifdef CBC_THREAD 32 /// Default constructor 24 33 CbcThread::CbcThread() 34 : 35 baseModel_(NULL), 36 thisModel_(NULL), 37 node_(NULL), // filled in every time 38 createdNode_(NULL), // filled in every time on return 39 mutex2_(NULL), // for waking up threads 40 condition2_(NULL), // for waking up thread 41 returnCode_(-1), // -1 available, 0 busy, 1 finished , 2?? 42 timeLocked_(0.0), 43 timeWaitingToLock_(0.0), 44 timeWaitingToStart_(0.0), 45 timeInThread_(0.0), 46 numberTimesLocked_(0), 47 numberTimesUnlocked_(0), 48 numberTimesWaitingToStart_(0), 49 dantzigState_(0), // 0 unset, -1 waiting to be set, 1 set 50 locked_(false), 51 nDeleteNode_(0), 52 delNode_(NULL), 53 maxDeleteNode_(0), 54 nodesThisTime_(0), 55 iterationsThisTime_(0), 56 deterministic_(0) 25 57 { 26 58 } 27 59 // Constructor with base model 28 60 CbcThread::CbcThread (CbcModel & model, int deterministic, CbcModel * baseModel) 29 { 61 : 62 baseModel_(baseModel), 63 thisModel_(&model), 64 node_(NULL), // filled in every time 65 createdNode_(NULL), // filled in every time on return 66 mutex2_(NULL), // for waking up threads 67 condition2_(NULL), // for waking up thread 68 returnCode_(-1), // -1 available, 0 busy, 1 finished , 2?? 69 timeLocked_(0.0), 70 timeWaitingToLock_(0.0), 71 timeWaitingToStart_(0.0), 72 timeInThread_(0.0), 73 numberTimesLocked_(0), 74 numberTimesUnlocked_(0), 75 numberTimesWaitingToStart_(0), 76 dantzigState_(0), // 0 unset, -1 waiting to be set, 1 set 77 locked_(false), 78 nDeleteNode_(0), 79 delNode_(NULL), 80 maxDeleteNode_(0), 81 nodesThisTime_(0), 82 iterationsThisTime_(0), 83 deterministic_(deterministic) 84 { 85 } 86 void 87 CbcThread::gutsOfDelete() 88 { 89 baseModel_ = NULL; 90 thisModel_ = NULL; 91 node_ = NULL; 92 createdNode_ = NULL; 93 mutex2_ = NULL; 94 condition2_ = NULL; 95 delNode_ = NULL; 96 } 97 void CbcThread::gutsOfCopy(const CbcThread & rhs) 98 { 99 baseModel_ = rhs.baseModel_; 100 thisModel_ = rhs.thisModel_; 101 node_ = rhs.node_; 102 createdNode_ = rhs.createdNode_; 103 mutex2_ = rhs.mutex2_; 104 condition2_ = rhs.condition2_; 105 returnCode_ = rhs.returnCode_; 106 timeLocked_ = rhs.timeLocked_; 107 timeWaitingToLock_ = rhs.timeWaitingToLock_; 108 timeWaitingToStart_ = rhs.timeWaitingToStart_; 109 timeInThread_ = rhs.timeInThread_; 110 numberTimesLocked_ = rhs.numberTimesLocked_; 111 numberTimesUnlocked_ = rhs.numberTimesUnlocked_; 112 numberTimesWaitingToStart_ = rhs.numberTimesWaitingToStart_; 113 dantzigState_ = rhs.dantzigState_; 114 locked_ = rhs.locked_; 115 nDeleteNode_ = rhs.nDeleteNode_; 116 delNode_ = rhs.delNode_; 117 maxDeleteNode_ = rhs.maxDeleteNode_; 118 nodesThisTime_ = rhs.nodesThisTime_; 119 iterationsThisTime_ = rhs.iterationsThisTime_; 120 deterministic_ = rhs.deterministic_; 30 121 } 31 122 // Destructor … … 33 124 { 34 125 } 126 // Assignment operator 127 CbcThread & 128 CbcThread::operator=(const CbcThread & rhs) 129 { 130 if (this != &rhs) { 131 gutsOfDelete(); 132 gutsOfCopy(rhs); 133 } 134 return *this; 135 } 136 /* 137 Locks a thread if parallel so that stuff like cut pool 138 can be updated and/or used. 139 */ 140 void 141 CbcThread::lockThread() 142 { 143 if (!locked_) { 144 struct timespec absTime2; 145 my_gettime(&absTime2); 146 double time2 = absTime2.tv_sec + 1.0e-9 * absTime2.tv_nsec; 147 pthread_mutex_lock (mutex_); 148 locked_ = true; 149 my_gettime(&absTime_); 150 double time = absTime_.tv_sec + 1.0e-9 * absTime_.tv_nsec; 151 timeWaitingToLock_ += time - time2;; 152 numberTimesLocked_++; 153 } 154 } 155 /* 156 Unlocks a thread if parallel 157 */ 158 void 159 CbcThread::unlockThread() 160 { 161 if (locked_) { 162 locked_ = false; 163 pthread_mutex_unlock (mutex_); 164 struct timespec absTime2; 165 my_gettime(&absTime2); 166 double time2 = absTime2.tv_sec + 1.0e-9 * absTime2.tv_nsec; 167 double time = absTime_.tv_sec + 1.0e-9 * absTime_.tv_nsec; 168 timeLocked_ += time2 - time; 169 numberTimesUnlocked_++; 170 } else { 171 printf("already unlocked\n"); 172 } 173 } 174 // Default constructor 175 CbcBaseModel::CbcBaseModel() 176 : 177 numberThreads_(0), 178 children_(NULL), 179 type_(0), 180 threadId_(NULL), 181 threadCount_(NULL), 182 threadModel_(NULL), 183 mutex2_(NULL), 184 condition2_(NULL), 185 numberObjects_(0), 186 saveObjects_(NULL), 187 defaultParallelIterations_(400), 188 defaultParallelNodes_(2) 189 { 190 } 191 /// Thread functions 192 static void * doNodesThread(void * voidInfo); 193 static void * doCutsThread(void * voidInfo); 194 static void * doHeurThread(void * voidInfo); 195 // Constructor with model 196 CbcBaseModel::CbcBaseModel (CbcModel & model, int type) 197 : 198 children_(NULL), 199 type_(type), 200 threadId_(NULL), 201 threadCount_(NULL), 202 threadModel_(NULL), 203 mutex2_(NULL), 204 condition2_(NULL), 205 numberObjects_(0), 206 saveObjects_(NULL), 207 defaultParallelIterations_(400), 208 defaultParallelNodes_(2) 209 { 210 numberThreads_ = model.getNumberThreads(); 211 if (numberThreads_) { 212 threadId_ = new Coin_pthread_t [numberThreads_]; 213 threadCount_ = new int [numberThreads_]; 214 CoinZeroN(threadCount_, numberThreads_); 215 children_ = new CbcThread [numberThreads_+1]; 216 pthread_mutex_init(&mutex_main_, NULL); 217 pthread_cond_init(&condition_main_, NULL); 218 pthread_mutex_init(&condition_mutex_, NULL); 219 threadModel_ = new CbcModel * [numberThreads_+1]; 220 mutex2_ = new pthread_mutex_t [numberThreads_]; 221 condition2_ = new pthread_cond_t [numberThreads_]; 222 memset(threadStats_, 0, sizeof(threadStats_)); 223 if (type_ > 0) { 224 // May need for deterministic 225 numberObjects_ = model.numberObjects(); 226 saveObjects_ = new OsiObject * [numberObjects_]; 227 for (int i = 0; i < numberObjects_; i++) { 228 saveObjects_[i] = model.object(i)->clone(); 229 } 230 } 231 // we don't want a strategy object 232 CbcStrategy * saveStrategy = model.strategy(); 233 model.setStrategy(NULL); 234 for (int i = 0; i < numberThreads_; i++) { 235 pthread_mutex_init(mutex2_ + i, NULL); 236 pthread_cond_init(condition2_ + i, NULL); 237 threadId_[i].status = 0; 238 threadModel_[i] = new CbcModel(model, true); 239 //threadModel_[i]->setMasterThread(children_+i); 240 children_[i] = CbcThread(*threadModel_[i], type_, &model); 241 threadModel_[i]->synchronizeHandlers(1); 242 #ifdef COIN_HAS_CLP 243 // Solver may need to know about model 244 CbcModel * thisModel = threadModel_[i]; 245 CbcOsiSolver * solver = 246 dynamic_cast<CbcOsiSolver *>(thisModel->solver()) ; 247 if (solver) 248 solver->setCbcModel(thisModel); 249 #endif 250 threadModel_[i]->setInfoInChild(-3, children_ + i); 251 if (type_ >= 0) 252 threadModel_[i]->moveToModel(&model, -1); 253 children_[i].thisModel_ = threadModel_[i]; 254 children_[i].node_ = NULL; 255 children_[i].createdNode_ = NULL; 256 children_[i].threadIdOfBase_.thr = pthread_self(); 257 children_[i].mutex_ = &mutex_main_; 258 children_[i].master_ = children_ + numberThreads_; 259 children_[i].mutex2_ = mutex2_ + i; 260 children_[i].condition2_ = condition2_ + i; 261 children_[i].returnCode_ = -1; 262 children_[i].timeLocked_ = 0.0; 263 children_[i].timeWaitingToLock_ = 0.0; 264 children_[i].timeWaitingToStart_ = 0.0; 265 children_[i].timeInThread_ = 0.0; 266 children_[i].numberTimesLocked_ = 0; 267 children_[i].numberTimesUnlocked_ = 0; 268 children_[i].numberTimesWaitingToStart_ = 0; 269 children_[i].dantzigState_ = 0; // 0 unset, -1 waiting to be set, 1 set 270 children_[i].locked_ = false; 271 children_[i].delNode_ = NULL; 272 children_[i].maxDeleteNode_ = 0; 273 children_[i].nDeleteNode_ = 0; 274 children_[i].nodesThisTime_ = 0; 275 children_[i].iterationsThisTime_ = 0; 276 if (type == -1) 277 pthread_create(&(threadId_[i].thr), NULL, doCutsThread, children_ + i); 278 else 279 pthread_create(&(threadId_[i].thr), NULL, doNodesThread, children_ + i); 280 threadId_[i].status = 1; 281 } 282 model.setStrategy(saveStrategy); 283 // Do a partial one for base model 284 children_[numberThreads_].baseModel_ = &model; 285 //model.setMasterThread(children_+numberThreads_); 286 threadModel_[numberThreads_] = &model; 287 children_[numberThreads_].node_ = NULL; 288 children_[numberThreads_].mutex_ = &mutex_main_; 289 children_[numberThreads_].condition2_ = &condition_main_; 290 children_[numberThreads_].mutex2_ = &condition_mutex_; 291 children_[numberThreads_].timeLocked_ = 0.0; 292 children_[numberThreads_].timeWaitingToLock_ = 0.0; 293 children_[numberThreads_].numberTimesLocked_ = 0; 294 children_[numberThreads_].numberTimesUnlocked_ = 0; 295 children_[numberThreads_].locked_ = false; 296 } 297 } 298 // Stop threads 299 void 300 CbcBaseModel::stopThreads() 301 { 302 for (int i = 0; i < numberThreads_; i++) { 303 while (children_[i].returnCode_ == 0) { 304 pthread_cond_signal(children_[i].condition2_); // unlock 305 pthread_mutex_lock(children_[numberThreads_].mutex2_); 306 struct timespec absTime; 307 my_gettime(&absTime); 308 absTime.tv_nsec += 1000000; // millisecond 309 if (absTime.tv_nsec >= 1000000000) { 310 absTime.tv_nsec -= 1000000000; 311 absTime.tv_sec++; 312 } 313 pthread_cond_timedwait(children_[numberThreads_].condition2_, children_[numberThreads_].mutex2_, &absTime); 314 my_gettime(&absTime); 315 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 316 } 317 threadModel_[i]->setInfoInChild(-2, NULL); 318 children_[i].returnCode_ = 0; 319 pthread_cond_signal(children_[i].condition2_); // unlock 320 pthread_join(threadId_[i].thr, NULL); 321 threadId_[i].status = 0; 322 pthread_mutex_destroy (children_[i].mutex2_); 323 pthread_cond_destroy (children_[i].condition2_); 324 } 325 pthread_cond_destroy (children_[numberThreads_].condition2_); 326 pthread_mutex_destroy (children_[numberThreads_].mutex2_); 327 // delete models and solvers 328 for (int i = 0; i < numberThreads_; i++) { 329 threadModel_[i]->setInfoInChild(type_, NULL); 330 delete threadModel_[i]; 331 } 332 delete [] mutex2_; 333 delete [] condition2_; 334 delete [] threadId_; 335 delete [] children_; 336 delete [] threadModel_; 337 for (int i = 0; i < numberObjects_; i++) 338 delete saveObjects_[i]; 339 delete [] saveObjects_; 340 mutex2_ = NULL; 341 condition2_ = NULL; 342 threadId_ = NULL; 343 children_ = NULL; 344 threadModel_ = NULL; 345 saveObjects_ = NULL; 346 numberObjects_ = 0; 347 numberThreads_ = 0; 348 } 349 // Wait for threads in tree 350 int 351 CbcBaseModel::waitForThreadsInTree(int type) 352 { 353 CbcModel * baseModel = children_[0].baseModel_; 354 int anyLeft = 0; 355 // May be able to combine parts later 356 357 if (type == 0) { 358 #ifdef COIN_DEVELOP 359 printf("empty\n"); 360 #endif 361 // may still be outstanding nodes 362 while (true) { 363 int iThread; 364 for (iThread = 0; iThread < numberThreads_; iThread++) { 365 if (threadId_[iThread].status) { 366 if (children_[iThread].returnCode_ == 0) 367 break; 368 } 369 } 370 if (iThread < numberThreads_) { 371 #ifdef COIN_DEVELOP 372 printf("waiting for thread %d code 0\n", iThread); 373 #endif 374 unlockThread(); 375 pthread_cond_signal(children_[iThread].condition2_); // unlock in case 376 while (true) { 377 pthread_mutex_lock(children_[numberThreads_].mutex2_); 378 struct timespec absTime; 379 my_gettime(&absTime); 380 double time = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 381 absTime.tv_nsec += 1000000; // millisecond 382 if (absTime.tv_nsec >= 1000000000) { 383 absTime.tv_nsec -= 1000000000; 384 absTime.tv_sec++; 385 } 386 pthread_cond_timedwait(children_[numberThreads_].condition2_, children_[numberThreads_].mutex2_, &absTime); 387 my_gettime(&absTime); 388 double time2 = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 389 children_[numberThreads_].timeInThread_ += time2 - time; 390 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 391 if (children_[iThread].returnCode_ != 0) 392 break; 393 pthread_cond_signal(children_[iThread].condition2_); // unlock 394 } 395 threadModel_[iThread]->moveToModel(baseModel, 1); 396 anyLeft = 1; 397 assert (children_[iThread].returnCode_ == 1); 398 if (children_[iThread].dantzigState_ == -1) { 399 // 0 unset, -1 waiting to be set, 1 set 400 children_[iThread].dantzigState_ = 1; 401 CbcModel * model = children_[iThread].thisModel_; 402 OsiClpSolverInterface * clpSolver2 403 = dynamic_cast<OsiClpSolverInterface *> (model->solver()); 404 assert (clpSolver2); 405 ClpSimplex * simplex2 = clpSolver2->getModelPtr(); 406 ClpDualRowDantzig dantzig; 407 simplex2->setDualRowPivotAlgorithm(dantzig); 408 } 409 // say available 410 children_[iThread].returnCode_ = -1; 411 threadStats_[4]++; 412 #ifdef COIN_DEVELOP 413 printf("thread %d code now -1\n", iThread); 414 #endif 415 break; 416 } else { 417 #ifdef COIN_DEVELOP 418 printf("no threads at code 0 \n"); 419 #endif 420 // now check if any have just finished 421 for (iThread = 0; iThread < numberThreads_; iThread++) { 422 if (threadId_[iThread].status) { 423 if (children_[iThread].returnCode_ == 1) 424 break; 425 } 426 } 427 if (iThread < numberThreads_) { 428 unlockThread(); 429 threadModel_[iThread]->moveToModel(baseModel, 1); 430 anyLeft = 1; 431 assert (children_[iThread].returnCode_ == 1); 432 // say available 433 children_[iThread].returnCode_ = -1; 434 threadStats_[4]++; 435 #ifdef COIN_DEVELOP 436 printf("thread %d code now -1\n", iThread); 437 #endif 438 break; 439 } 440 } 441 if (!baseModel->tree()->empty()) { 442 #ifdef COIN_DEVELOP 443 printf("tree not empty!!!!!!\n"); 444 #endif 445 return 1; 446 break; 447 } 448 for (iThread = 0; iThread < numberThreads_; iThread++) { 449 if (threadId_[iThread].status) { 450 if (children_[iThread].returnCode_ != -1) { 451 printf("bad end of tree\n"); 452 abort(); 453 } 454 } 455 } 456 break; 457 } 458 #ifdef COIN_DEVELOP 459 printf("finished ************\n"); 460 #endif 461 if (!anyLeft) 462 unlockThread(); 463 return anyLeft; 464 } else if (type == 1) { 465 // normal 466 double cutoff = baseModel->getCutoff(); 467 CbcNode * node = baseModel->tree()->bestNode(cutoff) ; 468 // Possible one on tree worse than cutoff 469 if (!node || node->objectiveValue() > cutoff) 470 return 1; 471 threadStats_[0]++; 472 //need to think 473 int iThread; 474 // Start one off if any available 475 for (iThread = 0; iThread < numberThreads_; iThread++) { 476 if (children_[iThread].returnCode_ == -1) 477 break; 478 } 479 if (iThread < numberThreads_) { 480 children_[iThread].node_ = node; 481 //printf("empty thread %d node %x\n",iThread,children_[iThread].node_); 482 assert (children_[iThread].returnCode_ == -1); 483 // say in use 484 threadModel_[iThread]->moveToModel(baseModel, 0); 485 // This has to be AFTER moveToModel 486 children_[iThread].returnCode_ = 0; 487 pthread_cond_signal(children_[iThread].condition2_); // unlock 488 threadCount_[iThread]++; 489 } 490 lockThread(); 491 // see if any finished 492 for (iThread = 0; iThread < numberThreads_; iThread++) { 493 if (children_[iThread].returnCode_ > 0) 494 break; 495 } 496 unlockThread(); 497 if (iThread < numberThreads_) { 498 threadModel_[iThread]->moveToModel(baseModel, 1); 499 anyLeft = 1; 500 assert (children_[iThread].returnCode_ == 1); 501 // say available 502 children_[iThread].returnCode_ = -1; 503 // carry on 504 threadStats_[3]++; 505 } else { 506 // Start one off if any available 507 for (iThread = 0; iThread < numberThreads_; iThread++) { 508 if (children_[iThread].returnCode_ == -1) 509 break; 510 } 511 if (iThread < numberThreads_) { 512 // If any on tree get 513 if (!baseModel->tree()->empty()) { 514 //node = baseModel->tree()->bestNode(cutoff) ; 515 //assert (node); 516 threadStats_[1]++; 517 return 1; // ** get another node 518 } 519 } 520 // wait (for debug could sleep and use test) 521 bool finished = false; 522 while (!finished) { 523 pthread_mutex_lock(children_[numberThreads_].mutex2_); 524 struct timespec absTime; 525 my_gettime(&absTime); 526 double time = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 527 absTime.tv_nsec += 1000000; // millisecond 528 if (absTime.tv_nsec >= 1000000000) { 529 absTime.tv_nsec -= 1000000000; 530 absTime.tv_sec++; 531 } 532 pthread_cond_timedwait(children_[numberThreads_].condition2_, children_[numberThreads_].mutex2_, &absTime); 533 my_gettime(&absTime); 534 double time2 = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 535 children_[numberThreads_].timeInThread_ += time2 - time; 536 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 537 for (iThread = 0; iThread < numberThreads_; iThread++) { 538 if (children_[iThread].returnCode_ > 0) { 539 finished = true; 540 break; 541 } else if (children_[iThread].returnCode_ == 0) { 542 pthread_cond_signal(children_[iThread].condition2_); // unlock 543 } 544 } 545 } 546 assert (iThread < numberThreads_); 547 // move information to model 548 threadModel_[iThread]->moveToModel(baseModel, 1); 549 anyLeft = 1; 550 node = children_[iThread].node_; 551 //printf("off thread %d node %x\n",iThread,children_[iThread].node_); 552 children_[iThread].node_ = NULL; 553 assert (children_[iThread].returnCode_ == 1); 554 // say available 555 children_[iThread].returnCode_ = -1; 556 } 557 // carry on 558 threadStats_[2]++; 559 for (int iThread = 0; iThread < numberThreads_; iThread++) { 560 if (threadId_[iThread].status) { 561 if (children_[iThread].returnCode_ != -1) { 562 anyLeft = 1; 563 break; 564 } 565 } 566 } 567 return anyLeft; 568 } else if (type == 2) { 569 // do statistics 570 int i; 571 // Seems to be bug in CoinCpu on Linux - does threads as well despite documentation 572 double time = 0.0; 573 for (i = 0; i < numberThreads_; i++) 574 time += children_[i].timeInThread_; 575 bool goodTimer = time < (baseModel->getCurrentSeconds()); 576 for (i = 0; i < numberThreads_; i++) { 577 while (children_[i].returnCode_ == 0) { 578 pthread_cond_signal(children_[i].condition2_); // unlock 579 pthread_mutex_lock(children_[numberThreads_].mutex2_); 580 struct timespec absTime; 581 my_gettime(&absTime); 582 absTime.tv_nsec += 1000000; // millisecond 583 if (absTime.tv_nsec >= 1000000000) { 584 absTime.tv_nsec -= 1000000000; 585 absTime.tv_sec++; 586 } 587 pthread_cond_timedwait(children_[numberThreads_].condition2_, children_[numberThreads_].mutex2_, &absTime); 588 my_gettime(&absTime); 589 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 590 } 591 pthread_cond_signal(children_[i].condition2_); // unlock 592 pthread_mutex_lock(children_[numberThreads_].mutex2_); // not sure necessary but have had one hang on interrupt 593 threadModel_[i]->setNumberThreads(0); // say exit 594 if (children_[i].deterministic_ > 0) 595 delete [] children_[i].delNode_; 596 children_[i].returnCode_ = 0; 597 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 598 pthread_cond_signal(children_[i].condition2_); // unlock 599 //if (!stopped) 600 //pthread_join(threadId[i],NULL); 601 int returnCode; 602 returnCode = pthread_join(threadId_[i].thr, NULL); 603 threadId_[i].status = 0; 604 assert (!returnCode); 605 //else 606 //pthread_kill(threadId[i]); // kill rather than try and synchronize 607 threadModel_[i]->moveToModel(baseModel, 2); 608 pthread_mutex_destroy (children_[i].mutex2_); 609 pthread_cond_destroy (children_[i].condition2_); 610 assert (children_[i].numberTimesLocked_ == children_[i].numberTimesUnlocked_); 611 baseModel->messageHandler()->message(CBC_THREAD_STATS, baseModel->messages()) 612 << "Thread"; 613 baseModel->messageHandler()->printing(true) 614 << i << threadCount_[i] << children_[i].timeWaitingToStart_; 615 baseModel->messageHandler()->printing(goodTimer) << children_[i].timeInThread_; 616 baseModel->messageHandler()->printing(false) << 0.0; 617 baseModel->messageHandler()->printing(true) << children_[i].numberTimesLocked_ 618 << children_[i].timeLocked_ << children_[i].timeWaitingToLock_ 619 << CoinMessageEol; 620 } 621 assert (children_[numberThreads_].numberTimesLocked_ == children_[numberThreads_].numberTimesUnlocked_); 622 baseModel->messageHandler()->message(CBC_THREAD_STATS, baseModel->messages()) 623 << "Main thread"; 624 baseModel->messageHandler()->printing(false) << 0 << 0 << 0.0; 625 baseModel->messageHandler()->printing(false) << 0.0; 626 baseModel->messageHandler()->printing(true) << children_[numberThreads_].timeInThread_; 627 baseModel->messageHandler()->printing(true) << children_[numberThreads_].numberTimesLocked_ 628 << children_[numberThreads_].timeLocked_ << children_[numberThreads_].timeWaitingToLock_ 629 << CoinMessageEol; 630 //pthread_mutex_destroy (&mutex_main_); 631 //pthread_cond_destroy (children_[numberThreads_].condition2_); 632 //pthread_mutex_destroy (children_[numberThreads_].mutex2_); 633 // delete models (here in case some point to others) 634 for (i = 0; i < numberThreads_; i++) { 635 // make sure handler will be deleted 636 threadModel_[i]->setDefaultHandler(true); 637 //delete threadModel_[i]; 638 } 639 } else { 640 abort(); 641 } 642 return 0; 643 } 644 void 645 CbcBaseModel::waitForThreadsInCuts(int type, OsiCuts * eachCuts, 646 int whichGenerator) 647 { 648 if (type == 0) { 649 // cuts while doing 650 bool finished = false; 651 int iThread = -1; 652 // see if any available 653 for (iThread = 0; iThread < numberThreads_; iThread++) { 654 if (children_[iThread].returnCode_) { 655 finished = true; 656 break; 657 } else if (children_[iThread].returnCode_ == 0) { 658 pthread_cond_signal(children_[iThread].condition2_); // unlock 659 } 660 } 661 while (!finished) { 662 pthread_mutex_lock(children_[numberThreads_].mutex2_); 663 struct timespec absTime; 664 my_gettime(&absTime); 665 absTime.tv_nsec += 1000000; // millisecond 666 if (absTime.tv_nsec >= 1000000000) { 667 absTime.tv_nsec -= 1000000000; 668 absTime.tv_sec++; 669 } 670 pthread_cond_timedwait(children_[numberThreads_].condition2_, children_[numberThreads_].mutex2_, &absTime); 671 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 672 for (iThread = 0; iThread < numberThreads_; iThread++) { 673 if (children_[iThread].returnCode_ > 0) { 674 finished = true; 675 break; 676 } else if (children_[iThread].returnCode_ == 0) { 677 pthread_cond_signal(children_[iThread].condition2_); // unlock 678 } 679 } 680 } 681 assert (iThread < numberThreads_); 682 assert (children_[iThread].returnCode_); 683 // Use dantzigState to signal which generator 684 children_[iThread].dantzigState_ = whichGenerator; 685 // and delNode for eachCuts 686 children_[iThread].delNode_ = reinterpret_cast<CbcNode **> (eachCuts); 687 // allow to start 688 children_[iThread].returnCode_ = 0; 689 pthread_cond_signal(children_[iThread].condition2_); // unlock 690 } else if (type == 1) { 691 // cuts - finish up 692 for (int iThread = 0; iThread < numberThreads_; iThread++) { 693 if (children_[iThread].returnCode_ == 0) { 694 bool finished = false; 695 pthread_cond_signal(children_[iThread].condition2_); // unlock 696 while (!finished) { 697 pthread_mutex_lock(children_[numberThreads_].mutex2_); 698 struct timespec absTime; 699 my_gettime(&absTime); 700 absTime.tv_nsec += 1000000; // millisecond 701 if (absTime.tv_nsec >= 1000000000) { 702 absTime.tv_nsec -= 1000000000; 703 absTime.tv_sec++; 704 } 705 pthread_cond_timedwait(children_[numberThreads_].condition2_, children_[numberThreads_].mutex2_, &absTime); 706 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 707 if (children_[iThread].returnCode_ > 0) { 708 finished = true; 709 break; 710 } else if (children_[iThread].returnCode_ == 0) { 711 pthread_cond_signal(children_[iThread].condition2_); // unlock 712 } 713 } 714 } 715 assert (children_[iThread].returnCode_); 716 // say available 717 children_[iThread].returnCode_ = -1; 718 //delete threadModel_[iThread]->solver(); 719 //threadModel_[iThread]->setSolver(NULL); 720 } 721 } else { 722 abort(); 723 } 724 } 725 // Split model and do work in deterministic parallel 726 void 727 CbcBaseModel::deterministicParallel() 728 { 729 CbcModel * baseModel = children_[0].baseModel_; 730 for (int i = 0; i < numberThreads_; i++) 731 threadCount_[i]++; 732 int saveTreeSize = baseModel->tree()->size(); 733 // For now create threadModel - later modify splitModel 734 CbcModel ** threadModel = new CbcModel * [numberThreads_]; 735 int iThread; 736 for (iThread = 0; iThread < numberThreads_; iThread++) 737 threadModel[iThread] = children_[iThread].thisModel_; 738 739 int nAffected = baseModel->splitModel(numberThreads_, threadModel, defaultParallelNodes_); 740 // do all until finished 741 for (iThread = 0; iThread < numberThreads_; iThread++) { 742 // obviously tune 743 children_[iThread].nDeleteNode_ = defaultParallelIterations_; 744 } 745 // Save current state 746 int iObject; 747 OsiObject ** object = baseModel->objects(); 748 for (iObject = 0; iObject < numberObjects_; iObject++) { 749 saveObjects_[iObject]->updateBefore(object[iObject]); 750 } 751 for (iThread = 0; iThread < numberThreads_; iThread++) { 752 children_[iThread].returnCode_ = 0; 753 pthread_cond_signal(children_[iThread].condition2_); // unlock 754 } 755 // wait 756 bool finished = false; 757 while (!finished) { 758 pthread_mutex_lock(children_[numberThreads_].mutex2_); 759 struct timespec absTime; 760 my_gettime(&absTime); 761 double time = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 762 absTime.tv_nsec += 1000000; // millisecond 763 if (absTime.tv_nsec >= 1000000000) { 764 absTime.tv_nsec -= 1000000000; 765 absTime.tv_sec++; 766 } 767 pthread_cond_timedwait(children_[numberThreads_].condition2_, 768 children_[numberThreads_].mutex2_, &absTime); 769 my_gettime(&absTime); 770 double time2 = absTime.tv_sec + 1.0e-9 * absTime.tv_nsec; 771 children_[numberThreads_].timeInThread_ += time2 - time; 772 pthread_mutex_unlock(children_[numberThreads_].mutex2_); 773 finished = true; 774 for (iThread = 0; iThread < numberThreads_; iThread++) { 775 if (children_[iThread].returnCode_ <= 0) { 776 finished = false; 777 } 778 } 779 } 780 // Unmark marked 781 for (int i = 0; i < nAffected; i++) { 782 baseModel->walkback()[i]->unmark(); 783 } 784 int iModel; 785 double scaleFactor = 1.0; 786 for (iModel = 0; iModel < numberThreads_; iModel++) { 787 //printf("model %d tree size %d\n",iModel,threadModel[iModel]->baseModel->tree()->size()); 788 if (saveTreeSize > 4*numberThreads_*defaultParallelNodes_) { 789 if (!threadModel[iModel]->tree()->size()) { 790 scaleFactor *= 1.05; 791 } 792 } 793 threadModel[iModel]->moveToModel(baseModel, 11); 794 // Update base model 795 OsiObject ** threadObject = threadModel[iModel]->objects(); 796 for (iObject = 0; iObject < numberObjects_; iObject++) { 797 object[iObject]->updateAfter(threadObject[iObject], saveObjects_[iObject]); 798 } 799 } 800 if (scaleFactor != 1.0) { 801 int newNumber = static_cast<int> (defaultParallelNodes_ * scaleFactor + 0.5001); 802 if (newNumber*2 < defaultParallelIterations_) { 803 if (defaultParallelNodes_ == 1) 804 newNumber = 2; 805 if (newNumber != defaultParallelNodes_) { 806 char general[200]; 807 sprintf(general, "Changing tree size from %d to %d", 808 defaultParallelNodes_, newNumber); 809 baseModel->messageHandler()->message(CBC_GENERAL, 810 baseModel->messages()) 811 << general << CoinMessageEol ; 812 defaultParallelNodes_ = newNumber; 813 } 814 } 815 } 816 delete [] threadModel; 817 } 818 // Destructor 819 CbcBaseModel::~CbcBaseModel() 820 { 821 delete [] threadCount_; 822 #if 1 823 delete [] threadId_; 824 for (int i = 0; i < numberThreads_; i++) 825 delete threadModel_[i]; 826 delete [] threadModel_; 827 delete [] children_; 828 delete [] mutex2_; 829 delete [] condition2_; 830 #endif 831 for (int i = 0; i < numberObjects_; i++) 832 delete saveObjects_[i]; 833 delete [] saveObjects_; 834 } 835 // Sets Dantzig state in children 836 void 837 CbcBaseModel::setDantzigState() 838 { 839 for (int i = 0; i < numberThreads_; i++) { 840 children_[i].dantzigState_ = -1; 841 } 842 } 843 // Default constructor 844 CbcSimpleThread::CbcSimpleThread() 845 : 846 numberThreads_(0), 847 argBundle_(NULL) 848 { 849 } 850 // Constructor with model 851 CbcSimpleThread::CbcSimpleThread (int numberThreads, 852 void *(* function) (void *), 853 int sizeOfData, 854 void * data) 855 : 856 numberThreads_(numberThreads), 857 argBundle_(data) 858 { 859 Coin_pthread_t * threadId = new Coin_pthread_t [numberThreads_]; 860 char * args = reinterpret_cast<char *>(argBundle_); 861 for (int i = 0; i < numberThreads_; i++) { 862 pthread_create(&(threadId[i].thr), NULL, function, 863 args + i*sizeOfData); 864 } 865 // now wait 866 for (int i = 0; i < numberThreads_; i++) { 867 pthread_join(threadId[i].thr, NULL); 868 } 869 delete [] threadId; 870 } 871 // Constructor with stuff 872 CbcSimpleThread::CbcSimpleThread (int numberThreads, 873 int type, 874 int sizeOfData, 875 void * data) 876 : 877 numberThreads_(numberThreads), 878 argBundle_(data) 879 { 880 assert (type == 0); // heuristics 881 Coin_pthread_t * threadId = new Coin_pthread_t [numberThreads_]; 882 char * args = reinterpret_cast<char *>(argBundle_); 883 for (int i = 0; i < numberThreads_; i++) { 884 pthread_create(&(threadId[i].thr), NULL, doHeurThread, 885 args + i*sizeOfData); 886 } 887 // now wait 888 for (int i = 0; i < numberThreads_; i++) { 889 pthread_join(threadId[i].thr, NULL); 890 } 891 delete [] threadId; 892 } 893 // Destructor 894 CbcSimpleThread::~CbcSimpleThread() 895 { 896 } 897 static void * doNodesThread(void * voidInfo) 898 { 899 CbcThread * stuff = reinterpret_cast<CbcThread *> (voidInfo); 900 pthread_mutex_t * mutex = stuff->mutex2_; 901 pthread_cond_t * condition = stuff->condition2_; 902 CbcModel * thisModel = stuff->thisModel_; 903 CbcModel * baseModel = stuff->baseModel_; 904 while (true) { 905 pthread_mutex_lock (mutex); 906 while (stuff->returnCode_) { 907 struct timespec absTime2; 908 my_gettime(&absTime2); 909 double time2 = absTime2.tv_sec + 1.0e-9 * absTime2.tv_nsec; 910 // timed wait as seems to hang on max nodes at times