Changeset 1364
- Timestamp:
- Dec 5, 2009 10:54:48 AM (11 years ago)
- Location:
- branches/sandbox/Cbc/src
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/sandbox/Cbc/src/CbcBranchDecision.hpp
r1357 r1364 90 90 /* If chooseMethod_ id non-null then the rest is fairly pointless 91 91 as choosemethod_ will be doing all work 92 */ 92 This comment makes more sense if you realise that there's a conversion in 93 process from the Cbc branching classes to Osi branching classes. The test 94 for use of the Osi branching classes is CbcModel::branchingMethod_ 95 non-null (i.e., it points to one of these CbcBranchDecision objects) and 96 that branch decision object has an OsiChooseVariable method set. In which 97 case, we'll use it, rather than the choose[*]Variable methods defined in 98 CbcNode. 99 */ 100 93 101 OsiChooseVariable * chooseMethod() const { 94 102 return chooseMethod_; -
branches/sandbox/Cbc/src/CbcFathom.hpp
r1286 r1364 5 5 #define CbcFathom_H 6 6 #include "CbcConfig.h" 7 8 /* 9 This file contains two classes, CbcFathom and CbcOsiSolver. It's unclear why 10 they're in the same file. CbcOsiSolver is a base class for CbcLinked. 11 12 --lh, 071031 -- 13 */ 14 7 15 8 16 class CbcModel; … … 74 82 75 83 This is for codes where solver needs to know about CbcModel 84 Seems to provide only one value-added feature, a CbcModel object. 85 76 86 */ 77 87 -
branches/sandbox/Cbc/src/CbcHeuristicFPump.cpp
r1286 r1364 221 221 char pumpPrint[LEN_PRINT]; 222 222 pumpPrint[0] = '\0'; 223 /* 224 Decide if we want to run. Standard values for when are described in 225 CbcHeuristic.hpp. If we're off, or running only at root and this isn't the 226 root, bail out. 227 228 The double test (against phase, then atRoot and passNumber) has a fair bit 229 of redundancy, but the results will differ depending on whether we're 230 actually at the root of the main search tree or at the root of a small tree 231 (recursive call to branchAndBound). 232 233 FPump also supports some exotic values (11 -- 15) for when, described in 234 CbcHeuristicFPump.hpp. 235 */ 223 236 if (!when() || (when() == 1 && model_->phase() != 1)) 224 237 return 0; // switched off … … 283 296 int numberIterationsLastPass = 0; 284 297 // 1. initially check 0-1 298 /* 299 I'm skeptical of the above comment, but it's likely accurate as the default. 300 Bit 4 or bit 8 needs to be set in order to consider working with general 301 integers. 302 */ 285 303 int i, j; 286 304 int general = 0; … … 290 308 bool doGeneral = (accumulate_ & 4) != 0; 291 309 j = 0; 310 /* 311 Scan the objects, recording the columns and counting general integers. 312 313 Seems like the NDEBUG tests could be made into an applicability test. If 314 a scan of the objects reveals complex objects, just clean up and return 315 failure. 316 */ 292 317 for (i = 0; i < numberIntegers; i++) { 293 318 int iColumn = integerVariableOrig[i]; … … 308 333 } 309 334 } 335 /* 336 If 2/3 of integers are general integers, and we're not going to work with 337 them, might as well go home. 338 339 The else case is unclear to me. We reach it if general integers are less than 340 2/3 of the total, or if either of bit 4 or 8 is set. But only bit 8 is used 341 in the decision. (Let manyGen = 1 if more than 2/3 of integers are general 342 integers. Then a k-map on manyGen, bit4, and bit8 shows it clearly.) 343 344 So there's something odd here. In the case where bit4 = 1 and bit8 = 0, 345 we've included general integers in integerVariable, but we're not going to 346 process them. 347 */ 310 348 if (general*3 > 2*numberIntegers && !doGeneral) { 311 349 delete [] integerVariable; … … 326 364 printf("DOing general with %d out of %d\n", general, numberIntegers); 327 365 #endif 366 /* 367 This `closest solution' will satisfy integrality, but violate some other 368 constraints? 369 */ 328 370 // For solution closest to feasible if none found 329 371 int * closestSolution = general ? NULL : new int[numberIntegers]; … … 345 387 } 346 388 double time1 = CoinCpuTime(); 389 /* 390 Obtain a relaxed lp solution. 391 */ 347 392 model_->solver()->resolve(); 348 393 if (!model_->solver()->isProvenOptimal()) { … … 363 408 } 364 409 } 410 /* 411 I have no idea why we're doing this, except perhaps that saveBasis will be 412 automagically deleted on exit from the routine. 413 */ 365 414 CoinWarmStartBasis saveBasis; 366 415 CoinWarmStartBasis * basis = … … 638 687 // 5. MAIN WHILE LOOP 639 688 //bool newLineNeeded=false; 689 /* 690 finished occurs exactly twice in this routine: immediately above, where it's 691 set to false, and here in the loop condition. 692 */ 640 693 while (!finished) { 641 694 double newTrueSolutionValue = 0.0; … … 1965 2018 } 1966 2019 } 2020 /* 2021 End of the `exitAll' loop. 2022 */ 1967 2023 #ifdef RAND_RAND 1968 2024 delete [] randomFactor; -
branches/sandbox/Cbc/src/CbcHeuristicFPump.hpp
r1286 r1364 55 55 14 - also fix all continuous variables staying at same internal value throughout 56 56 15 - as 13 but no internal integers 57 And beyond that, it's apparently possible for the range to be between 21 58 and 25, in which case it's reduced on entry to solution() to be between 59 11 and 15 and allSlack is set to true. Then, if we're not processing 60 general integers, we'll use an all-slack basis to solve ... what? Don't 61 see that yet. 57 62 */ 58 63 virtual int solution(double & objectiveValue, … … 151 156 3 - reuse solves, accumulate integer solutions for local search 152 157 If we add 4 then use second form of problem (with extra rows and variables for general integers) 158 At some point (date?), I added 159 160 And then there are a few bit fields: 161 4 - something about general integers 162 So my (lh) guess for 4 was at least in the ballpark, but I'll have to 163 rethink 8 entirely (and it may well not mean the same thing as it did 164 when I added that comment. 165 8 - determines whether we process general integers 166 167 And on 090831, John added 168 169 If we add 4 then use second form of problem (with extra rows and 170 variables for general integers) 153 171 If we add 8 then can run after initial cuts (if no solution) 154 172 */ -
branches/sandbox/Cbc/src/CbcHeuristicLocal.cpp
r1359 r1364 122 122 } 123 123 } 124 /* 125 Run a mini-BaB search after fixing all variables not marked as used by 126 solution(). (See comments there for semantics.) 127 128 Return values are: 129 1: smallBranchAndBound found a solution 130 0: everything else 131 132 The degree of overload as return codes from smallBranchAndBound are folded 133 into 0 is such that it's impossible to distinguish return codes that really 134 require attention from a simple `nothing of interest'. 135 */ 124 136 // This version fixes stuff and does IP 125 137 int … … 128 140 const int * /*keep*/) 129 141 { 142 /* 143 If when is set to off (0), or set to root (1) and we're not at the root, 144 return. If this heuristic discovered the current solution, don't continue. 145 */ 146 130 147 numCouldRun_++; 131 148 // See if to do … … 135 152 if (this == model_->lastHeuristic()) 136 153 return 0; 154 /* 155 Load up a new solver with the solution. 156 157 Why continuousSolver(), as opposed to solver()? 158 */ 137 159 OsiSolverInterface * newSolver = model_->continuousSolver()->clone(); 138 160 const double * colLower = newSolver->getColLower(); … … 141 163 int numberIntegers = model_->numberIntegers(); 142 164 const int * integerVariable = model_->integerVariable(); 165 /* 166 The net effect here is that anything that hasn't moved from its lower bound 167 will be fixed at lower bound. 168 169 See comments in solution() w.r.t. asymmetric treatment of upper and lower 170 bounds. 171 */ 143 172 144 173 int i; … … 157 186 } 158 187 } 188 /* 189 Try a `small' branch-and-bound search. The notion here is that we've fixed a 190 lot of variables and reduced the amount of `free' problem to a point where a 191 small BaB search will suffice to fully explore the remaining problem. This 192 routine will execute integer presolve, then call branchAndBound to do the 193 actual search. 194 */ 159 195 int returnCode = 0; 160 196 #ifdef CLP_INVESTIGATE2 … … 198 234 returnCode = smallBranchAndBound(newSolver, numberNodes_, newSolution, objectiveValue, 199 235 objectiveValue, "CbcHeuristicLocal"); 200 if (returnCode < 0) { 236 /* 237 -2 is return due to user event, and -1 is overloaded with what look to be 238 two contradictory meanings. 239 */ 240 if (returnCode < 0) { 201 241 returnCode = 0; // returned on size 202 242 int numberColumns = newSolver->getNumCols(); … … 262 302 } 263 303 } 304 /* 305 If the result is complete exploration with a solution (3) or proven 306 infeasibility (2), we could generate a cut (the AI folks would call it a 307 nogood) to prevent us from going down this route in the future. 308 */ 264 309 if ((returnCode&2) != 0) { 265 310 // could add cut … … 273 318 First tries setting a variable to better value. If feasible then 274 319 tries setting others. If not feasible then tries swaps 275 Returns 1 if solution, 0 if not */ 320 Returns 1 if solution, 0 if not 321 The main body of this routine implements an O((q^2)/2) brute force search 322 around the current solution, for q = number of integer variables. Call this 323 the inc/dec heuristic. For each integer variable x<i>, first decrement the 324 value. Then, for integer variables x<i+1>, ..., x<q-1>, try increment and 325 decrement. If one of these permutations produces a better solution, 326 remember it. Then repeat, with x<i> incremented. If we find a better 327 solution, update our notion of current solution and continue. 328 329 The net effect is a greedy walk: As each improving pair is found, the 330 current solution is updated and the search continues from this updated 331 solution. 332 333 Way down at the end, we call solutionFix, which will create a drastically 334 restricted problem based on variables marked as used, then do mini-BaC on 335 the restricted problem. This can occur even if we don't try the inc/dec 336 heuristic. This would be more obvious if the inc/dec heuristic were broken 337 out as a separate routine and solutionFix had a name that reflected where 338 it was headed. 339 340 The return code of 0 is grossly overloaded, because it maps to a return 341 code of 0 from solutionFix, which is itself grossly overloaded. See 342 comments in solutionFix and in CbcHeuristic::smallBranchAndBound. 343 */ 276 344 int 277 345 CbcHeuristicLocal::solution(double & solutionValue, 278 346 double * betterSolution) 279 347 { 348 /* 349 Execute only if a new solution has been discovered since the last time we 350 were called. 351 */ 280 352 281 353 numCouldRun_++; … … 283 355 return 0; 284 356 numberSolutions_ = model_->getSolutionCount(); 357 /* 358 Exclude long (column), thin (row) systems. 359 360 Given the n^2 nature of the search, more than 100,000 columns could get 361 expensive. But I don't yet see the rationale for the second part of the 362 condition (cols > 10*rows). And cost is proportional to number of integer 363 variables --- shouldn't we use that? 364 365 Why wait until we have more than one solution? 366 */ 285 367 if ((model_->getNumCols() > 100000 && model_->getNumCols() > 286 368 10*model_->getNumRows()) || numberSolutions_ <= 1) … … 292 374 const double * rowUpper = solver->getRowUpper(); 293 375 const double * solution = model_->bestSolution(); 376 /* 377 Shouldn't this test be redundant if we've already checked that 378 numberSolutions_ > 1? Stronger: shouldn't this be an assertion? 379 */ 294 380 if (!solution) 295 381 return 0; // No solution found yet … … 338 424 // space to save values so we don't introduce rounding errors 339 425 double * save = new double[numberRows]; 426 /* 427 Force variables within their original bounds, then to the nearest integer. 428 Overall, we seem to be prepared to cope with noninteger bounds. Is this 429 necessary? Seems like we'd be better off to force the bounds to integrality 430 as part of preprocessing. More generally, why do we need to do this? This 431 solution should have been cleaned and checked when it was accepted as a 432 solution! 433 434 Once the value is set, decide whether we can move up or down. 435 436 The only place that used_ is used is in solutionFix; if a variable is not 437 flagged as used, it will be fixed (at lower bound). Why the asymmetric 438 treatment? This makes some sense for binary variables (for which there are 439 only two options). But for general integer variables, why not make a similar 440 test against the original upper bound? 441 */ 340 442 341 443 // clean solution … … 364 466 } 365 467 cost[i] = direction * objective[iColumn]; 468 /* 469 Given previous computation we're checking that value is at least 1 away 470 from the original bounds. 471 */ 366 472 int iway = 0; 367 473 … … 372 478 way[i] = static_cast<char>(iway); 373 479 } 480 /* 481 Calculate lhs of each constraint for groomed solution. 482 */ 374 483 // get row activities 375 484 double * rowActivity = new double[numberRows]; … … 387 496 } 388 497 } 498 /* 499 Check that constraints are satisfied. For small infeasibility, force the 500 activity within bound. Again, why is this necessary if the current solution 501 was accepted as a valid solution? 502 503 Why are we scanning past the first unacceptable constraint? 504 */ 389 505 // check was feasible - if not adjust (cleaning may move) 390 506 // if very infeasible then give up … … 401 517 } 402 518 } 519 /* 520 This bit of code is not quite totally redundant: it'll bail at 10,000 521 instead of 100,000. Potentially we can do a lot of work to get here, only 522 to abandon it. 523 */ 403 524 // Switch off if may take too long 404 525 if (model_->getNumCols() > 10000 && model_->getNumCols() > 405 526 10*model_->getNumRows()) 406 527 tryHeuristic = false; 528 /* 529 Try the inc/dec heuristic? 530 */ 407 531 if (tryHeuristic) { 408 532 409 533 // best change in objective 410 534 double bestChange = 0.0; 535 /* 536 Outer loop to walk integer variables. Call the current variable x<i>. At the 537 end of this loop, bestChange will contain the best (negative) change in the 538 objective for any single pair. 539 540 The trouble is, we're limited to monotonically increasing improvement. 541 Suppose we discover an improvement of 10 for some pair. If, later in the 542 search, we discover an improvement of 9 for some other pair, we will not use 543 it. That seems wasteful. 544 */ 411 545 412 546 for (i = 0; i < numberIntegers; i++) { … … 418 552 int goodK = -1; 419 553 int wayK = -1, wayI = -1; 554 /* 555 Try decrementing x<i>. 556 */ 420 557 if ((way[i]&1) != 0) { 421 558 int numberInfeasible = 0; 559 /* 560 Adjust row activities where x<i> has a nonzero coefficient. Save the old 561 values for restoration. Mark any rows that become infeasible as a result 562 of the decrement. 563 */ 422 564 // save row activities and adjust 423 565 for (j = columnStart[iColumn]; … … 433 575 } 434 576 } 435 // try down 577 /* 578 Run through the remaining integer variables. Try increment and decrement on 579 each one. If the potential objective change is better than anything we've 580 seen so far, do a full evaluation of x<k> in that direction. If we can 581 repair all infeasibilities introduced by pushing x<i> down, we have a 582 winner. Remember the best variable, and the direction for x<i> and x<k>. 583 */ 584 // try down 436 585 for (k = i + 1; k < numberIntegers; k++) { 437 586 if ((way[k]&1) != 0) { … … 494 643 } 495 644 } 645 /* 646 Remove effect of decrementing x<i> by restoring original lhs values. 647 */ 496 648 // restore row activities 497 649 for (j = columnStart[iColumn]; … … 502 654 } 503 655 } 656 /* 657 Try to increment x<i>. Actions as for decrement. 658 */ 504 659 if ((way[i]&2) != 0) { 505 660 int numberInfeasible = 0; … … 586 741 } 587 742 } 743 /* 744 We've found a pair x<i> and x<k> which produce a better solution. Update our 745 notion of current solution to match. 746 747 Why does this not update newSolutionValue? 748 */ 588 749 if (goodK >= 0) { 589 750 // we found something - update solution … … 601 762 } 602 763 newSolution[kColumn] += wayK; 603 // See if k can go further ? 764 /* 765 Adjust motion range for x<k>. We may have banged up against a bound with that 766 last move. 767 */ 768 // See if k can go further ? 604 769 const OsiObject * object = model_->object(goodK); 605 770 // get original bounds … … 618 783 } 619 784 } 785 /* 786 End of loop to try increment/decrement of integer variables. 787 788 newSolutionValue does not necessarily match the current newSolution, and 789 bestChange simply reflects the best single change. Still, that's sufficient 790 to indicate that there's been at least one change. Check that we really do 791 have a valid solution. 792 */ 620 793 if (bestChange + newSolutionValue < solutionValue) { 621 794 // paranoid check … … 662 835 } 663 836 } 837 /* 838 Copy the solution to the array returned to the client. Grab a basis from 839 the solver (which, if it exists, is almost certainly infeasible, but it 840 should be ok for a dual start). The value returned as solutionValue is 841 conservative because of handling of newSolutionValue and bestChange, as 842 described above. 843 */ 664 844 // new solution 665 845 memcpy(betterSolution, newSolution, numberColumns*sizeof(double)); … … 679 859 } 680 860 } 861 /* 862 We're done. Clean up. 863 */ 681 864 delete [] newSolution; 682 865 delete [] rowActivity; … … 685 868 delete [] save; 686 869 delete [] mark; 870 /* 871 Do we want to try swapping values between solutions? 872 swap_ is set elsewhere; it's not adjusted during heuristic execution. 873 874 Again, redundant test. We shouldn't be here if numberSolutions_ = 1. 875 */ 687 876 if (numberSolutions_ > 1 && swap_ == 1) { 688 877 // try merge -
branches/sandbox/Cbc/src/CbcMain.cpp
r1286 r1364 2 2 // copyright (C) 2002, International Business Machines 3 3 // Corporation and others. All Rights Reserved. 4 5 /*! \file CbcMain.cpp 6 \brief Obsolete main routine for stand-alone cbc. 7 8 Unused since at least 2006. JJF forked off a clp-specific version, which 9 evolved into CoinSolve and CbcSolver. LH changed to a completely different 10 structure for CbcGeneric. 11 */ 4 12 5 13 #include "CbcConfig.h" -
branches/sandbox/Cbc/src/CbcModel.cpp
r1357 r1364 1656 1656 bool noObjects = (numberObjects_ == 0); 1657 1657 // Set up strategies 1658 /* 1659 See if the user has supplied a strategy object and deal with it if present. 1660 The call to setupOther will set numberStrong_ and numberBeforeTrust_, and 1661 perform integer preprocessing, if requested. 1662 1663 We need to hang on to a pointer to solver_. setupOther will assign a 1664 preprocessed solver to model, but will instruct assignSolver not to trash the 1665 existing one. 1666 */ 1658 1667 if (strategy_) { 1659 1668 // May do preprocessing … … 2024 2033 return ; 2025 2034 } 2035 /* 2036 See if we're using the Osi side of the branching hierarchy. If so, either 2037 convert existing CbcObjects to OsiObjects, or generate them fresh. In the 2038 first case, CbcModel owns the objects on the object_ list. In the second 2039 case, the solver holds the objects and object_ simply points to the 2040 solver's list. 2041 2042 080417 The conversion code here (the block protected by `if (obj)') cannot 2043 possibly be correct. On the Osi side, descent is OsiObject -> OsiObject2 -> 2044 all other Osi object classes. On the Cbc side, it's OsiObject -> CbcObject 2045 -> all other Cbc object classes. It's structurally impossible for any Osi 2046 object to descend from CbcObject. The only thing I can see is that this is 2047 really dead code, and object detection is now handled from the Osi side. 2048 */ 2026 2049 // Convert to Osi if wanted 2027 2050 bool useOsiBranching = false; … … 2072 2095 //} 2073 2096 } else { 2097 /* 2098 As of 080104, findIntegersAndSOS is misleading --- the default OSI 2099 implementation finds only integers. 2100 */ 2074 2101 // do from solver 2075 2102 deleteObjects(false); … … 2267 2294 double * upperBefore = new double [numberColumns] ; 2268 2295 /* 2296 Set up to run heuristics and generate cuts at the root node. The heavy 2297 lifting is hidden inside the calls to doHeuristicsAtRoot and solveWithCuts. 2298 2299 To start, tell cut generators they can be a bit more aggressive at the 2300 root node. 2301 2302 QUESTION: phase_ = 0 is documented as `initial solve', phase = 1 as `solve 2303 with cuts at root'. Is phase_ = 1 the correct indication when 2304 doHeurisiticsAtRoot is called to run heuristics outside of the main 2305 cut / heurisitc / reoptimise loop in solveWithCuts? 2269 2306 2270 2307 Generate cuts at the root node and reoptimise. solveWithCuts does the heavy … … 2349 2386 } 2350 2387 } 2388 /* 2389 Run heuristics at the root. This is the only opportunity to run FPump; it 2390 will be removed from the heuristics list by doHeuristicsAtRoot. 2391 */ 2351 2392 // Do heuristics 2352 2393 doHeuristicsAtRoot(); 2394 /* 2395 Grepping through the code, it would appear that this is a command line 2396 debugging hook. There's no obvious place in the code where this is set to 2397 a negative value. 2398 */ 2353 2399 if ( intParam_[CbcMaxNumNode] < 0) 2354 2400 eventHappened_ = true; // stop as fast as possible … … 2365 2411 //eventHappened_=true; // stop as fast as possible 2366 2412 } 2413 /* 2414 Set up for statistics collection, if requested. Standard values are 2415 documented in CbcModel.hpp. The magic number 100 will trigger a dump of 2416 CbcSimpleIntegerDynamicPseudoCost objects (no others). Looks like another 2417 command line debugging hook. 2418 */ 2367 2419 statistics_ = NULL; 2368 2420 // Do on switch … … 2375 2427 if (noObjects && numberIntegers_ < solver_->getNumCols() && (specialOptions_&65536) != 0 && !parentModel_) 2376 2428 AddIntegers(); 2377 2429 /* 2430 Do an initial round of cut generation for the root node. Depending on the 2431 type of underlying solver, we may want to do this even if the initial query 2432 to the objects indicates they're satisfied. 2433 2434 solveWithCuts does the heavy lifting. It will iterate a generate/reoptimise 2435 loop (including reduced cost fixing) until no cuts are generated, the 2436 change in objective falls off, or the limit on the number of rounds of cut 2437 generation is exceeded. 2438 2439 At the end of all this, any cuts will be recorded in cuts and also 2440 installed in the solver's constraint system. We'll have reoptimised, and 2441 removed any slack cuts (numberOldActiveCuts_ and numberNewCuts_ have been 2442 adjusted accordingly). 2443 */ 2378 2444 int iObject ; 2379 2445 int preferredWay ; … … 6905 6971 //solver_->writeMps("saved"); 6906 6972 #ifdef CBC_THREAD 6973 /* 6974 Thread mode makes a difference here only when it specifies using separate 6975 threads to generate cuts at the root (bit 2^1 set in threadMode_). In which 6976 case we'll create an array of empty CbcModels (!). Solvers will be cloned 6977 later. 6978 */ 6907 6979 CbcModel ** threadModel = NULL; 6908 6980 Coin_pthread_t * threadId = NULL; … … 6971 7043 onOptimalPath = (debugger->onOptimalPath(*solver_)) ; 6972 7044 } 7045 /* 7046 As the final action in each round of cut generation (the numberTries loop), 7047 we'll call takeOffCuts to remove slack cuts. These are saved into slackCuts 7048 and rechecked immediately after the cut generation phase of the loop. 7049 */ 6973 7050 OsiCuts slackCuts; 6974 7051 /* 6975 Resolve the problem. If we've lost feasibility, might as well bail out right 7052 lh: 7053 Resolve the problem 7054 7055 The resolve will also refresh cached copies of the solver solution 7056 (cbcColLower_, ...) held by CbcModel. 7057 This resolve looks like the best point to capture a warm start for use in 7058 the case where cut generation proves ineffective and we need to back out 7059 a few tight cuts. 7060 I've always maintained that this resolve is unnecessary. Let's put in a hook 7061 to report if it's every nontrivial. -lh 7062 7063 Resolve the problem. If we've lost feasibility, might as well bail out right 6976 7064 after the debug stuff. The resolve will also refresh cached copies of the 6977 7065 solver solution (cbcColLower_, ...) held by CbcModel. … … 6989 7077 cut_obj[CUT_HISTORY-1] = lastObjective; 6990 7078 //double firstObjective = lastObjective+1.0e-8+1.0e-12*fabs(lastObjective); 7079 /* 7080 Contemplate the result of the resolve. 7081 - CbcModel::resolve() has a hook that calls CbcStrategy::status to look 7082 over the solution. The net result is that resolve can return 7083 0 (infeasible), 1 (feasible), or -1 (feasible, but do no further work). 7084 - CbcFeasbililityBase::feasible() can return 0 (no comment), 7085 1 (pretend this is an integer solution), or -1 (pretend this is 7086 infeasible). As of 080104, this seems to be a stub to allow overrides, 7087 with a default implementation that always returns 0. 7088 7089 Setting numberTries = 0 for `do no more work' is problematic. The main cut 7090 generation loop will still execute once, so we do not observe the `no 7091 further work' semantics. 7092 7093 As best I can see, allBranchesGone is a null function as of 071220. 7094 */ 6991 7095 if (node && node->nodeInfo() && !node->nodeInfo()->numberBranchesLeft()) 6992 7096 node->nodeInfo()->allBranchesGone(); // can clean up … … 6997 7101 feasible = false; // pretend infeasible 6998 7102 } 7103 /* 7104 NEW_UPDATE_OBJECT is defined to 0 when unthreaded (CBC_THREAD undefined), 2 7105 when threaded. No sign of 1 as of 071220. 7106 7107 At present, there are two sets of hierarchies for branching classes. Call 7108 them CbcHier and OsiHier. For example, we have OsiBranchingObject, with 7109 children CbcBranchingObject and OsiTwoWayBranchingObject. All 7110 specialisations descend from one of these two children. Similarly, there is 7111 OsiObject, with children CbcObject and OsiObject2. 7112 7113 In the original setup, there's a single CbcBranchDecision object attached 7114 to CbcModel (branchingMethod_). It has a field to hold the current CbcHier 7115 branching object, and the updateInformation routine reaches through the 7116 branching object to update the underlying CbcHier object. 7117 7118 NEW_UPDATE_OBJECT = 0 would seem to assume the original setup. But, 7119 if we're using the OSI hierarchy for objects and branching, a call to a 7120 nontrivial branchingMethod_->updateInformation would have no effect (it 7121 would expect a CbcObject to work on) or perhaps crash. For the 7122 default CbcBranchDefaultDecision, updateInformation is a noop (actually 7123 defined in the base CbcBranchDecision class). 7124 7125 NEW_UPDATE_OBJECT = 2 looks like it's prepared to cope with either CbcHier or 7126 OsiHier, but it'll be executed only when threads are activated. See the 7127 comments below. The setup is scary. 7128 7129 But ... if the OsiHier update actually reaches right through to the object 7130 list in the solver, it should work just fine in unthreaded mode. It would 7131 seem that the appropriate thing to do in unthreaded mode would be to choose 7132 between the existing code for NEW_UPDATE_OBJECT = 0 and the OsiHier code for 7133 NEW_UPDATE_OBJECT = 2. But I'm going to let John hash that out. The worst 7134 that can happen is inefficiency because I'm not properly updating an object. 7135 */ 6999 7136 7000 7137 // Update branching information if wanted … … 7312 7449 7313 7450 The need to resolve here should only happen after a heuristic solution. 7451 optimalBasisIsAvailable resolves to basisIsAvailable, which seems to be part 7452 of the old OsiSimplex API. Doc'n says `Returns true if a basis is available 7453 and the problem is optimal. Should be used to see if the BinvARow type 7454 operations are possible and meaningful.' Which means any solver other the clp 7455 is probably doing a lot of unnecessary resolves right here. 7314 7456 (Note default OSI implementation of optimalBasisIsAvailable always returns 7315 7457 false.) … … 7372 7514 //probingInfo_->initializeFixing(); 7373 7515 int i; 7516 /* 7517 threadMode with bit 2^1 set indicates we should use threads for root cut 7518 generation. 7519 */ 7374 7520 if ((threadMode_&2) == 0 || numberNodes_) { 7375 7521 # ifdef COIN_HAS_CLP … … 7572 7718 } 7573 7719 } 7720 /* 7721 End of loop to run each cut generator. 7722 */ 7574 7723 if (!node) { 7575 7724 handler_->message(CBC_ROOT_DETAIL, messages_) … … 8380 8529 } 8381 8530 } while (numberTries > 0 || keepGoing) ; 8531 /* 8532 End cut generation loop. 8533 */ 8382 8534 { 8383 8535 // switch on … … 8453 8605 } 8454 8606 /* 8607 End of code block to check for a solution, when cuts may be added as a result 8608 of a feasible solution. 8609 8455 8610 Reduced cost fix at end. Must also check feasible, in case we've popped out 8456 8611 because a generator indicated we're infeasible. … … 8526 8681 //printf("XXb sum obj changed by %g\n",sumChangeObjective2_); 8527 8682 /* 8683 lh: 8684 Is this a full scan interval? If so, consider if we want to disable or 8685 adjust the frequency of use for any of the cut generators. If the client 8686 specified a positive number for howOften, it will never change. If the 8687 original value was negative, it'll be converted to 1000000+|howOften|, and 8688 this value will be adjusted each time fullScan is true. Actual cut 8689 generation is performed every howOften%1000000 nodes; the 1000000 offset is 8690 just a convenient way to specify that the frequency is adjustable. 8691 -lh 8528 8692 End of cut generation loop. 8529 8693 … … 8542 8706 TODO: All this should probably be hidden in a method of the CbcCutGenerator 8543 8707 class. 8544 8708 lh: 8709 TODO: Can the loop that scans over whichGenerator to accumulate per 8710 generator counts be replaced by values in countRowCuts and 8711 countColumnCuts? 8712 8713 << I think the answer is yes, but not the other way 'round. Row and 8714 column cuts are block interleaved in whichGenerator. >> 8715 8716 The root is automatically a full scan interval. At the root, decide if 8717 we're going to do cuts in the tree, and whether we should keep the cuts we 8718 have. 8719 8720 Codes for willBeCutsInTree: 8721 -1: no cuts in tree and currently active cuts seem ineffective; delete 8722 them 8723 0: no cuts in tree but currently active cuts seem effective; make them 8724 into architecturals (faster than treating them as cuts) 8725 1: cuts will be generated in the tree; currently active cuts remain as 8726 cuts 8727 -lh 8545 8728 */ 8546 8729 #ifdef NODE_LOG … … 8562 8745 double densityNew = numberRowsAdded ? (static_cast<double> (numberElementsAdded)) / static_cast<double> (numberRowsAdded) 8563 8746 : 0.0; 8747 /* 8748 If we're at the root, and we added cuts, and the cuts haven't changed the 8749 objective, and the cuts resulted in a significant increase (> 20%) in nonzero 8750 coefficients, do no cuts in the tree and ditch the current cuts. They're not 8751 cost-effective. 8752 */ 8564 8753 if (!numberNodes_) { 8565 8754 if (numberRowsAdded) … … 8678 8867 } 8679 8868 } 8869 /* 8870 Noop block 071219. 8871 */ 8680 8872 if ((numberRowsAdded > 100 + 0.5*numberRowsAtStart 8681 8873 || numberElementsAdded > 0.5*numberElementsAtStart) … … 8687 8879 // numberRowsAdded,densityNew); 8688 8880 } 8881 /* 8882 Noop block 071219. 8883 */ 8689 8884 if (densityNew > 100.0 && numberRowsAdded > 2 && densityNew > 2.0*densityOld) { 8690 8885 //if (thisObjective-startObjective<0.1*fabs(startObjective)+1.0e-5) … … 8694 8889 } 8695 8890 // Root node or every so often - see what to turn off 8891 /* 8892 Hmmm ... > -90 for any generator will overrule previous decision to do no 8893 cuts in tree and delete existing cuts. 8894 */ 8696 8895 int i ; 8697 8896 for (i = 0; i < numberCutGenerators_; i++) { … … 8706 8905 << currentPassNumber_ 8707 8906 << CoinMessageEol ; 8907 /* 8908 Count the number of cuts produced by each cut generator on this call. Not 8909 clear to me that the accounting is equivalent here. whichGenerator_ records 8910 the generator for column and row cuts. So unless numberNewCuts is row cuts 8911 only, we're double counting for JUST_ACTIVE. Note too the multiplier applied 8912 to column cuts. 8913 */ 8708 8914 if (!numberNodes_) { 8709 8915 double value = CoinMax(minimumDrop_, 0.005 * (thisObjective - startObjective) / … … 8736 8942 totalCuts += value; 8737 8943 } 8944 /* 8945 Open up a loop to step through the cut generators and decide what (if any) 8946 adjustment should be made for calling frequency. 8947 */ 8738 8948 int iProbing = -1; 8739 8949 double smallProblem = (0.2 * totalCuts) / … … 8742 8952 int howOften = generator_[i]->howOften() ; 8743 8953 /* Probing can be set to just do column cuts in treee. 8744 But if doing good then leave as on */ 8954 But if doing good then leave as on 8955 Ok, let me try to explain this. rowCuts = 3 says do disaggregation (1<<0) and 8956 coefficient (1<<1) cuts. But if the value is negative, there's code at the 8957 entry to generateCuts, and generateCutsAndModify, that temporarily changes 8958 the value to 4 (1<<2) if we're in a search tree. 8959 8960 Which does nothing to explain this next bit. We set a boolean, convert 8961 howOften to the code for `generate while objective is improving', and change 8962 over to `do everywhere'. Hmmm ... now I write it out, this makes sense in the 8963 context of the original comment. If we're doing well (objective improving) 8964 we'll keep probing fully active. 8965 8966 */ 8745 8967 bool probingWasOnBut = false; 8746 8968 CglProbing * probing = dynamic_cast<CglProbing*>(generator_[i]->generator()); … … 8758 8980 } 8759 8981 } 8982 /* 8983 Convert `as long as objective is improving' into `only at root' if we've 8984 decided cuts just aren't worth it. 8985 */ 8760 8986 if (willBeCutsInTree < 0 && howOften == -98) 8761 8987 howOften = -99; 8988 /* 8989 And check to see if the objective is improving. But don't do the check if 8990 the user has specified some minimum number of cuts. 8991 8992 This exclusion seems bogus, or at least counterintuitive. Why would a user 8993 suspect that setting a minimum cut limit would invalidate the objective 8994 check? Nor do I see the point in comparing the number of rows and columns 8995 in the second test. 8996 */ 8762 8997 if (!probing && howOften == -98 && !generator_[i]->numberShortCutsAtRoot() && 8763 8998 generator_[i]->numberCutsInTotal()) { … … 8773 9008 howOften = -99; // switch off 8774 9009 } 9010 /* 9011 Below -99, this generator is switched off. There's no need to consider 9012 further. Then again, there was no point in persisting this far! 9013 */ 8775 9014 if (howOften < -99) 8776 9015 continue ; 9016 /* 9017 Adjust, if howOften is adjustable. 9018 */ 8777 9019 if (howOften < 0 || howOften >= 1000000) { 8778 9020 if ( !numberNodes_) { 9021 /* 9022 If root only, or objective improvement but no cuts generated, switch off. If 9023 it's just that the generator found no cuts at the root, give it one more 9024 chance. 9025 */ 8779 9026 // If small number switch mostly off 8780 9027 #ifdef JUST_ACTIVE … … 8802 9049 } 8803 9050 } 9051 /* 9052 Not productive, but not zero either. 9053 */ 8804 9054 } else if ((thisCuts + generator_[i]->numberColumnCuts() < smallProblem) 8805 9055 && !generator_[i] ->whetherToUse()) { 9056 /* 9057 Not unadjustable every node, and not strong probing. 9058 */ 8806 9059 if (howOften != 1 && !probingWasOnBut) { 9060 /* 9061 No depth spec, or not adjustable every node. 9062 */ 8807 9063 if (generator_[i]->whatDepth() < 0 || howOften != -1) { 8808 9064 int k = static_cast<int> (sqrt(smallProblem / thisCuts)) ; 9065 /* 9066 Not objective improvement, set to new frequency, otherwise turn off. 9067 */ 8809 9068 if (howOften != -98) 8810 9069 howOften = k + 1000000 ; 8811 9070 else 8812 9071 howOften = -100; 9072 /* 9073 Depth spec, or adjustable every node. Force to unadjustable every node. 9074 */ 8813 9075 } else { 8814 9076 howOften = 1; 8815 9077 } 9078 /* 9079 Unadjustable every node, or strong probing. Force unadjustable every node and 9080 force not strong probing? I don't understand. 9081 */ 8816 9082 } else { 8817 9083 howOften = 1; … … 8819 9085 probingWasOnBut = false; 8820 9086 } 9087 /* 9088 Productive cut generator. Say we'll do it every node, adjustable. But if the 9089 objective isn't improving, restrict that to every fifth depth level 9090 (whatDepth overrides howOften in generateCuts). 9091 */ 8821 9092 } else { 8822 9093 if (thisObjective - startObjective < 0.1*fabs(startObjective) + 1.0e-5 && generator_[i]->whatDepth() < 0) … … 8825 9096 } 8826 9097 } 9098 /* 9099 End root actions. 9100 9101 sumChangeObjective2_ is the objective change due to cuts. If we're getting 9102 much better results from branching over a large number of nodes, switch off 9103 cuts. 9104 9105 Except it doesn't, really --- it just puts off the decision 'til the 9106 next full scan, when it'll put it off again unless cuts look better. 9107 */ 8827 9108 // If cuts useless switch off 8828 9109 if (numberNodes_ >= 100000 && sumChangeObjective1_ > 2.0e2*(sumChangeObjective2_ + 1.0e-12)) { … … 8831 9112 } 8832 9113 } 9114 /* 9115 Ok, that's the frequency adjustment bit. 9116 9117 Now, if we're at the root, force probing back on at every node, for column 9118 cuts at least, even if it looks useless for row cuts. Notice that if it 9119 looked useful, the values set above mean we'll be doing strong probing in 9120 the tree subject to objective improvement. 9121 */ 8833 9122 if (!numberNodes_) { 8834 9123 if (probingWasOnBut && howOften == -100) { … … 8842 9131 willBeCutsInTree = 1; 8843 9132 } 9133 /* 9134 Set the new frequency in the generator. If this is an adjustable frequency, 9135 use the value to set whatDepth. 9136 9137 Hey! Seems like this could override the user's depth setting. 9138 */ 8844 9139 generator_[i]->setHowOften(howOften) ; 8845 9140 if (howOften >= 1000000 && howOften < 2000000 && 0) { … … 8882 9177 } 8883 9178 } 9179 /* 9180 End loop to adjust cut generator frequency of use. 9181 */ 8884 9182 delete [] count ; 8885 9183 if ( !numberNodes_) { … … 8889 9187 generator_[i]->setNumberActiveCutsAtRoot(generator_[i]->numberCutsActive()); 8890 9188 } 9189 /* 9190 Garbage code 071219 9191 */ 8891 9192 // decide on pseudo cost strategy 8892 9193 int howOften = iProbing >= 0 ? generator_[iProbing]->howOften() : 0; … … 8913 9214 if (willBeCutsInTree == -2) 8914 9215 willBeCutsInTree = 0; 9216 /* 9217 End garbage code. 9218 9219 Now I've reached the problem area. This is a problem only at the root node, 9220 so that should simplify the issue of finding a workable basis? Or maybe not. 9221 */ 8915 9222 if ( willBeCutsInTree <= 0) { 8916 9223 // Take off cuts … … 9263 9570 return numberDropped; 9264 9571 } 9265 9572 /* 9573 Return values: 9574 1: feasible 9575 0: infeasible 9576 -1: feasible and finished (do no more work on this subproblem) 9577 */ 9266 9578 int 9267 9579 CbcModel::resolve(CbcNodeInfo * parent, int whereFrom, … … 9578 9890 int returnStatus = feasible ? 1 : 0; 9579 9891 if (strategy_) { 9892 /* 9893 Possible returns from status: 9894 -1: no recommendation 9895 0: treat as optimal 9896 1: treat as optimal and finished (no more resolves, cuts, etc.) 9897 2: treat as infeasible. 9898 */ 9580 9899 // user can play clever tricks here 9581 9900 int status = strategy_->status(this, parent, whereFrom); … … 9649 9968 const double * rowLower = getRowLower(); 9650 9969 const double * rowUpper = getRowUpper(); 9970 /* 9971 Scan the rows, looking for individual rows that are clique constraints. 9972 */ 9651 9973 9652 9974 for (iRow = 0; iRow < numberRows; iRow++) { … … 9657 9979 bool good = true; 9658 9980 int slack = -1; 9981 /* 9982 Does this row qualify? All variables must be binary and all coefficients 9983 +/- 1.0. Variables with positive coefficients are recorded at the low end of 9984 which, variables with negative coefficients the high end. 9985 */ 9659 9986 for (j = rowStart[iRow]; j < rowStart[iRow] + rowLength[iRow]; j++) { 9660 9987 int iColumn = column[j]; … … 9687 10014 int iUpper = static_cast<int> (floor(upperValue + 1.0e-5)); 9688 10015 int iLower = static_cast<int> (ceil(lowerValue - 1.0e-5)); 10016 /* 10017 What do we have? If the row upper bound is greater than 1-numberM1, this 10018 isn't a clique. If the row upper bound is 1-numberM1, we have the classic 10019 clique (an SOS1 on binary variables, if numberM1 = 0). If the upper bound 10020 equals numberM1, we can fix all variables. If the upper bound is less than 10021 numberM1, we're infeasible. 10022 10023 A similar analysis applies using numberP1 against the lower bound. 10024 */ 9689 10025 int state = 0; 9690 10026 if (upperValue < 1.0e6) { … … 9704 10040 state = -3; 9705 10041 } 9706 if (good && state) { 10042 /* 10043 What to do? If we learned nothing, move on to the next iteration. If we're 10044 infeasible, we're outta here. If we decided we can fix variables, do it. 10045 */ 10046 if (good && state) { 9707 10047 if (abs(state) == 3) { 9708 10048 // infeasible … … 9728 10068 } 9729 10069 } else { 10070 /* 10071 And the final case: we have a clique constraint. If it's within the allowed 10072 size range, make a clique object. 10073 */ 9730 10074 int length = numberP1 + numberM1; 9731 10075 if (length >= atLeastThisMany && length < lessThanThis) { … … 9733 10077 bool addOne = false; 9734 10078 int objectType; 10079 /* 10080 Choose equality (type 1) or inequality (type 0). If we're forcing equalities, 10081 add a slack. 10082 */ 9735 10083 if (iLower == iUpper) { 9736 10084 objectType = 1; … … 9745 10093 } 9746 10094 } 10095 /* 10096 Record the strong values for the variables. Variables with positive 10097 coefficients force all others when set to 1; variables with negative 10098 coefficients force when set to 0. If the clique is formed against the row 10099 lower bound, convert to the canonical form of a clique against the row 10100 upper bound. 10101 */ 9747 10102 if (state > 0) { 9748 10103 totalP1 += numberP1; … … 9809 10164 } 9810 10165 #endif 10166 /* 10167 If required, augment the constraint matrix with clique slacks. Seems like we 10168 should be able to add the necessary integer objects without a complete 10169 rebuild of existing integer objects, but I'd need to look further to confirm 10170 that (lh, 071219). Finally, add the clique objects. 10171 */ 9811 10172 if (numberCliques > 0 && numberSlacks && makeEquality) { 9812 10173 printf("adding %d integer slacks\n", numberSlacks); … … 12523 12884 return solver->isProvenOptimal() ? 1 : 0; 12524 12885 } 12886 /*! 12887 \todo It'd be really nice if there were an overload for this method that 12888 allowed a separate value for the underlying solver's log level. The 12889 overload could be coded to allow an increase in the log level of the 12890 underlying solver. 12891 12892 It's worth contemplating whether OSI should have a setLogLevel method 12893 that's more specific than the hint mechanism. 12894 */ 12525 12895 12526 12896 // Set log level … … 12618 12988 } 12619 12989 /* Encapsulates choosing a variable - 12620 anyAction -2, infeasible (-1 round again), 0 done 12990 anyAction: -2 infeasible 12991 -1 round again 12992 0 done 12993 12994 At the point where chooseBranch is called, we've decided that this problem 12995 will need to be placed in the live set and we need to choose a branching 12996 variable. 12997 12998 Parameters: 12999 newNode: the node just created for the active subproblem. 13000 oldNode: newNode's parent. 13001 lastws: oldNode's basis 13002 lowerBefore, upperBefore: column bound arrays for oldNode 13003 cuts: list of cuts added to newNode. 13004 13005 resolved: (o) set to true if newNode is resolved during processing 13006 branches: (o) will be filled in with ... ? Null on entry 12621 13007 */ 12622 13008 int … … 12635 13021 4 - no solution but many nodes 12636 13022 add 10 if depth >= K 13023 K is currently hardcoded to 8, a few lines below. 13024 13025 CBCMODEL_DEBUG: Seems like stateOfSearch_ should be 2 if 13026 numberHeuristicSolutions_ == numberSolutions_. 13027 12637 13028 */ 12638 13029 stateOfSearch_ = 1; … … 12687 13078 #endif 12688 13079 currentNode_ = newNode; // so can be used elsewhere 13080 /* 13081 Enough preparation. Get down to the business of choosing a branching 13082 variable. 13083 */ 12689 13084 while (anyAction == -1) { 12690 13085 // Set objective value (not so obvious if NLP etc) … … 12692 13087 //if (numberPassesLeft<=0) 12693 13088 //branchingState=1; 13089 /* 13090 Is there a CbcBranchDecision object installed? Does it specify a 13091 chooseVariable method? If not, we're using the old (Cbc) side of the branch 13092 decision hierarchy. In quick summary, CbcNode::chooseBranch uses strong 13093 branching on any objects, while CbcNode::chooseDynamicBranch uses dynamic 13094 branching, but only on simple integers (-3 is the code for punt due to 13095 complex objects). Serious bugs remain on the Cbc side, particularly in 13096 chooseDynamicBranch. 13097 */ 12694 13098 if (!branchingMethod_ || !branchingMethod_->chooseMethod()) { 12695 13099 #ifdef COIN_HAS_CLP … … 12727 13131 anyAction = newNode->chooseBranch(this, oldNode, numberPassesLeft) ; // dynamic did nothing 12728 13132 } 13133 /* 13134 We're on the new (Osi) side of the branching hierarchy. 13135 */ 12729 13136 } else { 12730 13137 OsiBranchingInformation usefulInfo = usefulInformation(); … … 12821 13228 } 12822 13229 } 13230 /* 13231 End main loop to choose a branching variable. 13232 */ 12823 13233 if (anyAction >= 0) { 12824 13234 if (resolved) { … … 13103 13513 1 - delete 13104 13514 2 - just delete - don't even use 13515 Parameter of 2 means what it says --- the routine will do nothing except 13516 delete the existing heuristics. A feasibility pump is always deleted, 13517 independent of the parameter value, as it's only useful at the root. 13518 13519 The routine is called from branchAndBound to process the root node. But it 13520 will also be called when we've recursed into branchAndBound via smallBaB. 13105 13521 */ 13106 13522 void … … 13112 13528 int i; 13113 13529 if (deleteHeuristicsAfterwards != 2) { 13530 /* 13531 If mode == 1, we delete and recreate here, then delete at the bottom. The 13532 create/delete part makes sense, but why delete the existing array? Seems like 13533 it should be preserved and restored. 13534 */ 13114 13535 if (deleteHeuristicsAfterwards) { 13115 13536 delete [] usedInSolution_; … … 13122 13543 if (eventHandler) 13123 13544 eventHandler->setModel(this); 13545 /* 13546 currentPassNumber_ is described as `cut pass number'. Again, seems a bit 13547 cavalier to just change it. 13548 13549 Whether this has any effect is determined by individual heuristics. Typically 13550 there will be a check at the front of the solution() routine that determines 13551 whether it will run or simply return. Root heuristics are characterised by 13552 node count of 0. In addition, currentPassNumber_ can be checked to to limit 13553 execution in terms of passes through cut generation / heuristic execution in 13554 solveWithCuts. 13555 */ 13124 13556 13125 13557 currentPassNumber_ = 1; // so root heuristics will run 13558 /* 13559 A loop to run the heuristics. incrementUsed will mark entries in 13560 usedInSolution corresponding to variables that are nonzero in the solution. 13561 CBC_ROUNDING just identifies a message template, not the heuristic. 13562 */ 13126 13563 // Modify based on size etc 13127 13564 adjustHeuristics(); … … 13269 13706 /* 13270 13707 Did any of the heuristics turn up a new solution? Record it before we free 13271 the vector. 13708 the vector. tree_ will not necessarily be a CbcTreeLocal; the main model gets 13709 a CbcTree by default. CbcTreeLocal actually implements a k-neighbourhood 13710 search heuristic. This initialises it with a solution and creates the 13711 k-neighbourhood cut. 13272 13712 */ 13273 13713 if (found >= 0) { … … 13283 13723 } 13284 13724 } 13725 /* 13726 Cleanup. The feasibility pump heuristic is a root heuristic to look for an 13727 initial feasible solution. It's had its chance; remove it. 13728 13729 For modes 1 and 2, all the heuristics are deleted. 13730 */ 13285 13731 if (!deleteHeuristicsAfterwards) { 13286 13732 for (i = 0; i < numberHeuristics_; i++) {
Note: See TracChangeset
for help on using the changeset viewer.