Here's a topic that arises repeatedly on the CPLEX support forums: the differences between an LP/MIP model built "internally" using CPLEX Concert technology, the same model written to a file using CPLEX's SAV format (and then read back in, or solved using the interactive solver), and the same model written to a file using CPLEX's industry-not-quite-standard LP format. Since I can never find links to previous discussions when I need them, I'll put a quick summary here. I suspect it applies to other solvers that support both binary and text file formats; I know it applies to CPLEX.
Many factors influence the sequence of pivots a solver does on an LP model and the sequence of nodes it grinds through in a MIP model. If you solve the same model two different ways, using the same or different software, you should end up with the same optimal objective value (to within rounding); that's the definition of "optimal". If you don't, either you've found a bug in the software or, more likely, your problem is mathematically ill-conditioned. Even if the problem is well-conditioned, and you get the same objective value both places, you may not get the same optimal solution. You should if the solution is unique; but if there are multiple optima, you may get one optimal solution one time and a different one the next time.
This is true even if you use the same program (for instance, CPLEX) both times. Small, seemingly innocuous things such as the order in which variable or constraints are entered, or the compiler used to compile the respective CPLEX versions, can make a difference. (Different C/C++ compilers may have different floating point algorithms encoded.)
The bigger (to me) issue, though, is that if you dump the model to a file and solve the file with the interactive solver, you are not solving the same model. You are solving what is hopefully a close (enough) replicate of the original model. The binary output format (SAV for CPLEX) will generally be closer to the original model than the text (LP or MPS for CPLEX) format will be. I'm not an expert on SAV file format, so I'll say that it is possible the SAV file is an exact duplicate. That requires not only full fidelity in representation of coefficients but also that the internal model you get by reading and processing the SAV file has all variables and constraints specified in exactly the same order that they appeared in the internal model from which the SAV file was created. I'm not sure that's true, but I'm not sure it isn't.
What I am sure of is that the text version is not in general a full-fidelity copy. Not only do we have the same questions about preservation of order, but we have the rounding problems incurred by converting a double precision binary number to a text representation and then back to a double precision binary value. If your model is well-conditioned, hopefully the differences are small enough not to affect the optimal solution. It may still affect the solution process. Suppose that you have an LP model with some degeneracy (which is not a sign of ill-conditioning). Degeneracy means a tie occurs occasionally when selecting pivot rows. At least it's a tie in theory; in practice, tiny rounding errors may serve to break the tie, and those rounding errors may well be different in the original version and the not-quite-perfect clone you get by saving a text version of the model and then reading it in. So the solver working on the original model pivots in one row, the solver working on the model from the text file pivots in a different row, and the solution time and possibly the solution itself can change.
The first immediate take-away from this is that if you want to compare the solution your code gets to the solution the interactive solver gets, use the binary file format. If you also want to visually check the model, save it as both binary and text files (and feed the binary file to the interactive solver). Don't rely on the text file to replicate solver behavior.
The second take-away is to modulate your expectations. In a just and orderly universe, solving the same model with the same software, on two different platforms and regardless of how you passed it between the software copies, would produce the same solution. A just and orderly universe, however, would not contain politicians. So accept that differences may arise.
Wednesday, September 22, 2010
8 comments:
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.
Subscribe to:
Post Comments (Atom)
I don't think all the vendors have a binary format, but it's generally a good investment for support, since you otherwise might (and in many cases will) end up not being able to reproduce the faulty run a customer had. I don't know how much is included in cplex's sav format. If you think about it, it,s more complicated than expected, because you also have to deal with hotstarts i.e serialize LU and other internal structures cleverly stored by the optimizer between runs. So my experience is that you choose a level of deepness, that captures "most" of the randomness you see from the optimizer taking different paths. I have had several cases, where not serializing the LU made it impossible for me to reproduce the customers run. Which clearly is a support drawback.
ReplyDeleteInteresting point. I hadn't thought about including hot start information in the SAV file. You're absolutely right, though, that failure to include an initial basis (when one is used) makes it tough to replicate behavior. At the same time, including the hot start means that if I export a SAV file today and again tomorrow, with no changes to my code in between (but having run it twice on one day and once on the other day), I might end up exporting different SAV files while thinking they would be the same.
ReplyDeleteOne more reason I'm happy not to be working in tech support (and sympathetic to those who are). :-)
The two runs should produce the same binary file, given your code and the optimizer is deterministic. Serializing hot start data structures doesn't change that. The problem with serializing is the maintainability, you got to make sure it is always up to date, sounds easy but can get complicated between major releases.
ReplyDeleteOne point I wanted to raise - you are equating 'binary' and 'full precision' here. The two are linked in CPLEX (through the SAV format), but this isn't a technical requirement. We chose to use MPS format (a text format) as our full precision format in Gurobi. In both the CPLEX SAV format and our MPS format, you get the exact same model, down to the last bit, when you write the model to a file and then read it back in.
ReplyDelete@Ed I can sure understand the reasons for choosing a text file with full precision, so you get the exact same model data. As said I don't know what is included in cplex sav format, but I was expecting more than just model data, though I might be mistaken. Anyways I think it's important to have some internal information stored to better reproduce customer runs.
ReplyDelete@Ed: It's been quite a while since I took my last numerical analysis class (back then the limit on arithmetic precision was the number of beads on the abacus), but as I recall there is generally a loss of precision (truncation error) when converting between numerical bases, since a fraction expressed in finitely many numerals in one base may require infinitely many numerals in another base. Quite likely the model built through an API already contains some truncations (builder likely uses decimals, computer representation is binary), and it probably is miniscule compared to fuzziness in some of the parameter values. Nonetheless, the model exported in text format using decimal notation will probably deviate slightly from the internal binary representation of the model, due to truncation error. In terms of the optimal solution, the difference is probably well below the radar -- but in terms of replicating the exact sequence of pivots in a degenerate LP, or possibly the exact sequence of nodes in a MIP search, can we be sure that flipping the last bit in the mantissa of some of the coefficients has no effect on the algorithm's decisions?
ReplyDeleteI landed on this blog post today while trying to answer the same question. And Paul's September 23 post is correct about different numerical bases (not the plural of basis for the simplex method) lose precision with different numbers (e.g. 1/3 cannot be stored exactly in the base 2 arithmetic used on most of today's computers). And yes, it is possible that just losing the last bit of the mantissa can be enough to break a tie in the algorithm's decision, leading to alternate optimal bases (the simplex kind), which in turn leads to alternate branching selections when solving MIPs, and then all sorts of performance variability. This is one reason I recommend that whenever you can replace fractions involving simple ratios of integers during the model formulation step with integers, do so. For example, instead of representing 1/3x + 2/3y = 1 with decimal representations of 1/3 that result in a loss of precision around the 16th decimal place in a base 2 representation, multiply the constraint by 3 to get
ReplyDeletex + 2y = 3, and now all your data is in terms of sums of powers of 2 and represented precisely.
Given that I'm writing on a thread that is almost 10 years old, it may seem like nothing has changed, but that is not really the case. Progress has been made in understanding performance variability in mixed integer programming (e.g. see http://www.or.deis.unibo.it/andrea/Lodi-MIC2011-nopause.pdf). CPLEX now has a runseeds command that allows you to assess the level of variability in your MIP model. Also since 2010, I have written a detailed paper on the numerical aspects of LP and MIP solver that can be found on the INFORMS web site here: https://pubsonline.informs.org/doi/10.1287/educ.2014.0130. And if you don't have the patience for a lengthy paper on numerical epsilons and other nitty gritty details, you can try accessing a shorter powerpoint version here: http://yetanothermathprogrammingconsultant.blogspot.com/2015/03/mip-links.html
Ed: Thanks for the links. I agree with your point about expressing constraints with integers rather than fractions (or their decimal equivalents) where practical.
Delete