Ignore:
Timestamp:
Dec 5, 2009 10:54:48 AM (10 years ago)
Author:
EdwinStraver
Message:

Added comments from Lou

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox/Cbc/src/CbcHeuristicLocal.cpp

    r1359 r1364  
    122122    }
    123123}
     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*/
    124136// This version fixes stuff and does IP
    125137int
     
    128140                               const int * /*keep*/)
    129141{
     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
    130147    numCouldRun_++;
    131148    // See if to do
     
    135152    if (this == model_->lastHeuristic())
    136153        return 0;
     154/*
     155  Load up a new solver with the solution.
     156
     157  Why continuousSolver(), as opposed to solver()?
     158*/
    137159    OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
    138160    const double * colLower = newSolver->getColLower();
     
    141163    int numberIntegers = model_->numberIntegers();
    142164    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*/
    143172
    144173    int i;
     
    157186        }
    158187    }
     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*/
    159195    int returnCode = 0;
    160196#ifdef CLP_INVESTIGATE2
     
    198234        returnCode = smallBranchAndBound(newSolver, numberNodes_, newSolution, objectiveValue,
    199235                                         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) {
    201241            returnCode = 0; // returned on size
    202242            int numberColumns = newSolver->getNumCols();
     
    262302        }
    263303    }
     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*/
    264309    if ((returnCode&2) != 0) {
    265310        // could add cut
     
    273318  First tries setting a variable to better value.  If feasible then
    274319  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  */
    276344int
    277345CbcHeuristicLocal::solution(double & solutionValue,
    278346                            double * betterSolution)
    279347{
     348/*
     349  Execute only if a new solution has been discovered since the last time we
     350  were called.
     351*/
    280352
    281353    numCouldRun_++;
     
    283355        return 0;
    284356    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*/
    285367    if ((model_->getNumCols() > 100000 && model_->getNumCols() >
    286368            10*model_->getNumRows()) || numberSolutions_ <= 1)
     
    292374    const double * rowUpper = solver->getRowUpper();
    293375    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*/
    294380    if (!solution)
    295381        return 0; // No solution found yet
     
    338424    // space to save values so we don't introduce rounding errors
    339425    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*/
    340442
    341443    // clean solution
     
    364466        }
    365467        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*/
    366472        int iway = 0;
    367473
     
    372478        way[i] = static_cast<char>(iway);
    373479    }
     480/*
     481  Calculate lhs of each constraint for groomed solution.
     482*/
    374483    // get row activities
    375484    double * rowActivity = new double[numberRows];
     
    387496        }
    388497    }
     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*/
    389505    // check was feasible - if not adjust (cleaning may move)
    390506    // if very infeasible then give up
     
    401517        }
    402518    }
     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*/
    403524    // Switch off if may take too long
    404525    if (model_->getNumCols() > 10000 && model_->getNumCols() >
    405526            10*model_->getNumRows())
    406527        tryHeuristic = false;
     528/*
     529  Try the inc/dec heuristic?
     530*/
    407531    if (tryHeuristic) {
    408532
    409533        // best change in objective
    410534        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*/
    411545
    412546        for (i = 0; i < numberIntegers; i++) {
     
    418552            int goodK = -1;
    419553            int wayK = -1, wayI = -1;
     554/*
     555  Try decrementing x<i>.
     556*/
    420557            if ((way[i]&1) != 0) {
    421558                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*/
    422564                // save row activities and adjust
    423565                for (j = columnStart[iColumn];
     
    433575                    }
    434576                }
    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
    436585                for (k = i + 1; k < numberIntegers; k++) {
    437586                    if ((way[k]&1) != 0) {
     
    494643                    }
    495644                }
     645/*
     646  Remove effect of decrementing x<i> by restoring original lhs values.
     647*/
    496648                // restore row activities
    497649                for (j = columnStart[iColumn];
     
    502654                }
    503655            }
     656/*
     657  Try to increment x<i>. Actions as for decrement.
     658*/
    504659            if ((way[i]&2) != 0) {
    505660                int numberInfeasible = 0;
     
    586741                }
    587742            }
     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*/
    588749            if (goodK >= 0) {
    589750                // we found something - update solution
     
    601762                }
    602763                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 ?
    604769                const OsiObject * object = model_->object(goodK);
    605770                // get original bounds
     
    618783            }
    619784        }
     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*/
    620793        if (bestChange + newSolutionValue < solutionValue) {
    621794            // paranoid check
     
    662835                    }
    663836                }
     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*/
    664844                // new solution
    665845                memcpy(betterSolution, newSolution, numberColumns*sizeof(double));
     
    679859        }
    680860    }
     861/*
     862  We're done. Clean up.
     863*/
    681864    delete [] newSolution;
    682865    delete [] rowActivity;
     
    685868    delete [] save;
    686869    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*/
    687876    if (numberSolutions_ > 1 && swap_ == 1) {
    688877        // try merge
Note: See TracChangeset for help on using the changeset viewer.