Changeset 1364 for branches/sandbox/Cbc/src/CbcHeuristicLocal.cpp
 Timestamp:
 Dec 5, 2009 10:54:48 AM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/sandbox/Cbc/src/CbcHeuristicLocal.cpp
r1359 r1364 122 122 } 123 123 } 124 /* 125 Run a miniBaB 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' branchandbound 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<q1>, 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 miniBaC 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
Note: See TracChangeset
for help on using the changeset viewer.