Tuesday, June 19, 2018

Callback Cuts That Repeat

The following post is specific to the CPLEX integer programming solver. I have no idea whether it applies to other solvers, or even which other solver have cut callbacks.

Every so often, a user will discover that a callback routine they wrote has "rediscovered" a cut it previously generated. This can be a bit concerning at first, for a few reasons: it seems implausible, and therefore raises concerns of a bug someplace; it represents repeated work, and thus wasted effort; and it suggests at least the possibility of getting stuck in a loop, the programmatic equivalent of "Groundhog Day". (Sorry, couldn't resist.) As it happens, though, repeating the same cut can legitimately happen (though hopefully not too often).

First, I should probably define what I mean by callbacks here (although I'm tempted to assume that if you don't know what I mean, you've already stopped reading). If you want to get your geek on, feel free to wade through the Wikipedia explanation of a callback function. In the context of CPLEX, what I'm referring to is a user-written function that CPLEX will call at certain points in the search process. I will focus on functions called when CPLEX is generating cuts to tighten the bound at a given node of the search tree (a "user cut callback" in their terminology) or when CPLEX thinks it has identified an integer-feasible solution better than the current incumbent (a "lazy constraint callback"). That terminology pertains to versions of CPLEX prior to 12.8, when those would be two separate (now "legacy") callbacks. As of CPLEX version 12.8, there is a single ("generic") type of callback, but generic callbacks continue to be called from multiple "contexts", including those two (solving a node LP, checking a new candidate solution).

The purpose here is to let the user either generate a bound-tightening constraint ("user cut") using particular knowledge of the problem structure, or to vet a candidate solution and, if unsuitable, issue a new constraint ("lazy constraint") that cuts off that solution, again based on problem information not part of the original IP model. The latter is particularly common with decomposition techniques such as Benders decomposition.

So why would the same user cut or lazy constraint be generated more than once (other than due to a bug)? There are at least two, and possibly three, explanations.

Local versus Global


A user cut can be either local or global. The difference is whether the cut is valid in the original model ("global") or whether it is contingent on branching decisions that led to the current node ("local"). The user can specify in the callback whether a new cut is global or local. If the cut is specified as local, it will be enforced only at descendants of the current node.

That said, it is possible that a local cut might be valid at more than one node of the search tree, in which case it might be rediscovered when those other nodes are visited. In the worst case, if the cut is actually globally valid but for some reason added with the local flag set, it may be rediscovered quite a few times.

Parallel Threading


On a system with multiple cores (or multiple processors), using parallel threads can speed CPLEX up. Parallel threads, though, are probably the most common cause for cuts and lazy constraints repeating.

The issue is that threads operate somewhat independently and only synchronize periodically. So suppose that thread A triggers a callback that generates a globally valid user cut or lazy constraint, which is immediately added to the problem A is solving. Thread B, which is working on a somewhat different problem (from a different part of the search tree), is unaware of the new cut/constraint until it reaches a synchronization point (and finds out what A and any other sibling threads have been up to). Prior to that, B might stumble on the same cut/constraint. Since A and B are calling the same user callback function, if the user is tracking what has been generated inside that function, the function will register a repetition. This is normal (and harmless).

Cut Tables


This last explanation is one I am not entirely sure about. When cuts and lazy constraints are added, CPLEX stores them internally in some sort of table. I believe that it is possible in some circumstances for a callback function to be called before the table is (fully) checked, in which case the callback might generate a cut or constraint that is already in the table. Since this deals with the internal workings of CPLEX (the secret sauce), I don't know first-hand if this is true or not ... but if it is, it is again slightly wasteful of time but generally harmless.

User Error


Of course, none of this precludes the possibility of a bug in the user's code. If, for example, the user reacts to a candidate solution with a lazy constraint that is intended to cut off that solution but does not (due to incorrect formulation or construction), CPLEX will register the user constraint, notice that the solution is still apparently valid, and give the callback another crack at it. (At least that is how it worked with legacy callbacks, and I think that is how it works with generics.) Seeing the same solution, the user callback might generate the same (incorrect) lazy constraints, and off the code goes, chasing its own tail.

5 comments:

  1. Dear Prof. Rubin,

    First of all, many thanks to your blog post series on callback-based Benders implementations in CPLEX. I really learned a lot.

    Regarding the third explanation (cut table), I think it is only possible under two cases, at least for the lazy constraints, with the premise that all cuts in the cut table will be tested:
    1. when the cut table is empty;
    2. when the callback identifies multiple cuts and some of them are identical.

    If the premise holds, then no integer-feasible solutions cut off by lazy constraints in the cut table should ever be proposed as a candidate. So a repeated cut indicates either an empty cut table, or a newly invoked callback returning repeated cuts.

    Do you think the above reasoning is correct?

    Luyu

    ReplyDelete
    Replies
    1. If a cut repeats, why would the cut table be empty the second time the cut was generated? Presumably it would have been added to the table the first time ... with one qualification. When using legacy callbacks, there is an optional "cut management" parameter that can be used to tell CPLEX whether to retain the cut no matter what or whether the solver is free to drop the cut if it appears "ineffective" after a while. I don't recall if that parameter is available in generic callbacks. So with the right setting a lazy constraint might be added to the table but then disappear later before being rediscovered. I forgot to mention that above. Other than expiration, I don't see how the cut table could be empty the second time the cut is generated. Regarding the second point, if the callback identifies identical cuts, I would consider that a coding issue. In the post, I tacitly assume that the callback will not identify the same constraint multiple times *within the same invocation*. As for the premise that all cuts in the table will be tested, I would like to believe that, but I'm not sure it's true. The callback documentation says that if you add lazy constraints "... then CPLEX can use these constraints to cut off further candidate solutions that CPLEX finds. (There is no guarantee that CPLEX does so, though.)"

      Delete
    2. Dear Prof. Rubin,

      Thank you for the detailed comment.

      I made up the 'empty cut table' point. It is viable only in the sense that it could be inferred from the premise. I did not check whether it is really achievable with either the legacy or the generic callback APIs. My apology for the confusion. I think your elaboration on the 'cut management' parameter in the legacy callback makes perfect sense.

      On the second point. I'm actually imagining solving a stochastic programming problem with multiple scenario subproblems by Benders. My vague guess is that some of the subproblems may, occasionally, return identical cuts on specific master problem solutions. Nevertheless, such occasions could be checked within the callback to prevent multiple identical cuts being fed back to CPLEX. So I agree that it should be acccounted as a coding issue.

      Delete
    3. To the second point, I thought you meant that the same cut was added more than once *within one call* to the callback. Generating the same cut within different subproblems, or during parallel-threaded subproblem solves, is certainly possible, but I would not worry about it. CPLEX should recognize that you are passing a cut it already knows and simply ignore the duplicates. Note that the cuts should not duplicate cuts that were generated earlier (prior to the most recent master problem iteration). If you are solving a Benders subproblem, it is because CPLEX identified what it thought was a possible master incumbent. If the subproblem finds an already known cut violated by the candidate solution, CPLEX should not have considered it a candidate (unless one of the factors, such as making the cut local or allowing the cut to expire) caused the original cut not to be considered.

      Delete
    4. I agree. If the lazy constraints in the cut table were fully considered, CPLEX should never propose repeated master incumbent. By repeated I mean one that has already been checked by the subproblem(s).

      However, as suggested by the CPLEX documentation, the lazy constraints that are fed to CPLEX by the reject candidate method are not guaranteed to be used by CPLEX.

      I'm using Julia, and the package works with CPLEX by calling the C API. In the documentation on the routine `CPXcallbackrejectcandidate` [1], a warning says:

      "There is no guarantee that CPLEX will use the constraints that you specify. CPLEX will try to do so, but for technical reasons, it is not always possible to use the constraints. You can thus not assume that in subsequent callback invocations the candidate solutions satisfy the constraints you specified here. "

      I know you are using Java. I guess the Java counterpart to
      `CPXcallbackrejectcandidate` is the `rejectCandidate` method that belongs to the `IloCplex.Callback.Context` class. In the description of the argument of the method [2], it says:

      "A set of constraints that cut off the candidate solution. This set can potentially be empty. This argument can also be `null`. If not `null` and not empty, then CPLEX can use these constraints to cut off further candidate solutions that CPLEX finds. (There is no guarantee that CPLEX does so, though.)"

      I'm afraid that your speculation on the "cut table" might be true. In fact, I did encounter repeated master incumbent when experiementing with a very simple MILP instance (2 binary variables and 1 continuous variable). Presolves and reductions are explicitly turned off. And the number of thread is set to 1. So I'm very suspicious about how the user generated lazy constraints are handled by CPLEX.

      [1] https://www.ibm.com/docs/en/icos/12.10.0?topic=c-cpxxcallbackrejectcandidate-cpxcallbackrejectcandidate

      [2] https://www.ibm.com/docs/api/v1/content/SSSA5P_12.10.0/ilog.odms.cplex.help/refjavacplex/html/ilog/cplex/IloCplex.Callback.Context.html#rejectCandidate(ilog.concert.IloRange[])

      Delete

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.