Wednesday, August 14, 2013

Different Solvers, Different Solutions

I've seen multiple variations of the following general question online lately: "I ran my model (linear or integer linear program) through two different solvers (or two different versions of the same solver) (or the same version of the same solver during two different phases of the moon) and got two different answers. What went wrong?"

Well, let's break this down according to what is meant by "answers" and just what is different.

Both solutions "optimal", same objective value, different variable values.


Barring an error by one solver or the other, you've just discovered that your problem has multiple optimal solutions.
  • If you used two different solvers, there is no reason to expect them to find the same solution, so this is an unsurprising outcome.
  • If you used two versions of the same solver, it is quite possible that changes to the "plumbing" of the solver would occasionally lead the newer version to find a different one of the multiple optimal solutions.
  • If you used the same version of the same solver on two different computers, you may be the "victim" of subtle differences in how they do floating point arithmetic (leading to slightly different round/truncation errors, in turn steering the algorithm slightly differently each time).
  • If you used two different versions of the model file, for instance one in CPLEX's LP format and the other in their SAV format, differences in the precision of the input values or the order in which variables and/or constraints are listed could account for variations in which optimal solution is found.
  • If the solver uses multiple parallel threads, I believe it is possible that differences in the synchronization of those threads could result in different solutions being found. I suspect this is more likely with integer programs, but this is really a bit outside my expertise. The operating system will likely interrupt threads occasionally to use the processors/cores running them for other tasks. It could be that different threads were interrupted at different times during the two runs, so that for example a node that was pruned due to bound in the first run was separated in the second because the new incumbent (found in a different thread during the first run) was not found in time to prune it during the second run.
  • Computers are not as deterministic as one might hope. (Buy me a beer at a conference and I'll tell you about the computer that -- briefly -- had true and false confused. No, I'm not making that up just to score free beers.)
 

Both solutions "optimal" but with different objective values.


Solvers have various convergence criteria, typically including absolute and/or relative tolerances for the objective value. For integer programs, these are usually expressed in terms of the "gap" between the objective value and the best known bound (lower bound for minimization, upper bound for maximization). If either the absolute or relative (percentage) gap falls below a specified nonzero threshold, the solver declares victory and announces an "optimal" solution.

This means that the announced objective value for an optimal solution is only approximately equal to the true optimal value (charitably assuming that the solver has correctly identified an optimum). Therefore, unless the difference between the announced optimal values of the two solvers exceeds both the larger of the two absolute gap limits and the larger of the two relative gap limits, this is probably just a combination of rounding error and convergence tolerances. In short, you can accept both answers as plausibly correct.

One "optimal" solution, one suboptimal solution.


Perhaps the solvers had different convergence criteria specified. Very likely they had different values for an assortment of parameters that affect performance. Quite possibly, either one solver is better than the other or one just was luckier than the other (particularly plausible with integer programs, perverse beasties that they are). Move along, folks: nothing to see here. Just make sure that the suboptimal solution does not have a better objective value than the optimal solution (again, by more than the tolerance convergence of the first solver -- if the values are close, it could be that both have the optimal solution but the second solver has not yet proved it optimal).

One "optimal" solution, one "infeasible" diagnosis.


Obviously someone is pulling your leg here. In addition to the convergence tolerances mentioned above, solvers generally have non-zero tolerances for how close a solution has to come to satisfying a constraint (and, for integer problems, how close the value of an integer variable has to be to the nearest actual integer). This is necessary in order to avoid having darned near every problem declared "infeasible" due to rounding errors.

Different tolerances could possibly account for the discrepancy. If your problem is "numerically unstable" (predisposed to causing ugly rounding error problems), it could be that one solver is better at handling numerical instability than the other one, or that parameter settings relating to numerical stability account for the different in results. I suggest that you take the alleged optimal solution, plug it into the model fed to the other solver (for instance, by setting the upper and lower bound of each variable to its "optimal" value), then ask the second solver to diagnose the source of infeasibility (which constraints are violated). You can then decide for yourself whether the constraint violations are small enough for you to tolerate.

Both feasible, neither optimal, different results.


Nothing remarkable here. Anything goes in this case, so long as neither incumbent solution spells out "Harvard" or "Michigan" in ASCII. (No need for obscenity just because the problem was not solved to optimality.)

6 comments:

  1. There are infinitely many anecdotes to tell about this topic, e.g.:

    - A solver declaring a program both feasible and infeasible at the same time.
    - LP solvers declaring a linear program optimal while the objective increases again when you recall the optimize-function.
    - Solvers confusing infeasibility and unboundedness.

    If one really relies on correct results, an exact sover (for MIP: scip-ex; for LP: QSopt_ex, polymake, ...) has to be used (caution: slow!).

    Best regards,
    Thomas

    ReplyDelete
    Replies
    1. Thomas: Have you seen a solver actually declare an infeasible problem to be unbounded (or vice versa)? CPLEX has an "InfeasibleOrUnbounded" status, which is confusing to the user, but CPLEX itself is not confused. It determines that the dual is infeasible, which means the primal is either infeasible or unbounded, and then stops without attempting to figure out which state the primal is in.

      Delete
    2. Paul,

      the dual infeasibility ("InfeasibleOrUnbounded") is not what I was talking about. I should have pointed this out. Thank you for doing so. I have seen dual infeasibility only very rarely, but of course, it can happen. (One should also point out that dual infeasibility cannot happen if all variables are bounded.)

      Concering your question:
      If I remember correctly, a while ago I had an "unbounded" linear program where it was difficult to decide whether it was feasible or not. Unfortunately, I do not remember the facts.

      On the other hand, it should be easy to construct such a problem. Just take an unbounded problem, add a slight infeasibility und see what the solver does. I would expect that it depends on whether one uses the primal or dual simplex algorithm. And it will also depend on whether one uses a presolver.

      Best regards,
      Thomas

      Delete
  2. Thomas,

    Thanks for the clarification. I must disagree, though, with the statement that dual infeasibility cannot occur if all primal variables are bounded. It is possible, at least in pathological cases, that primal and dual are both infeasible. (I have an example stashed in some lecture notes.) If both are infeasible, adding bounds to the primal variables will not change that. Commonly, though, infeasible duals come paired with unbounded primals, and you are correct that bounding the primal variables rules that case out.

    Cheers,
    Paul

    ReplyDelete
    Replies
    1. Paul,

      I think you are wrong here. If a problem is bounded, it should be possible to do dual feasibility correction (DFC) until it becomes dual feasible. In fact any basis (i.e. a subset of colums that belongs to an invertable matrix) should be dual feasible.

      I agree that a problem can be primal and dual infeasible, but adding these bounds should add additional variables to the dual making it feasible.

      I have no proof at hand, but I think details can be found in Achim Koberstein's dissertation.

      Best regards,
      Thomas

      Delete
    2. Thomas,

      Oops, you are right. Bounding primal variables obviously does not make the primal feasible, but it does create a trivial feasible solution to the dual (with all constraint multipliers zero and only the multipliers for some of the primal bounds nonnegative). One more reason that all models should contain bounds on all variables absent an explicit reason not to.

      Cheers,
      Paul

      Delete

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 OR-Exchange.