tag:blogger.com,1999:blog-8781383461061929571.post4909052274563281858..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: Big M and Integrality TolerancePaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-8781383461061929571.post-12531400242039557142018-05-08T11:57:52.131-04:002018-05-08T11:57:52.131-04:00By "adequately" I meant reasonable run t...By "adequately" I meant reasonable run time (with reasonable memory requirements). As for your question, sorry, but no. I haven't touched C++ in a decade or two (or more), and when I was last cursed with using it all I knew were the usual primitive data types.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-10157336500561648562018-05-08T11:52:24.996-04:002018-05-08T11:52:24.996-04:00I think the problem is not adequacy but runtime. I...I think the problem is not adequacy but runtime. If the whole solver is based on exact data types and all operations are performed without tolerances and the code itself is correct, then the results should be fine.<br /><br />Another question: Do you know of some "general" irrational C++ data type similar to the rational mpq_class from GMP? With polymake's field extension, one might already be able to solve some irrational problems. But I have to admit that I don't know how general this data type really is.<br /><br />By the way: If somebody has some numerically troublesome MIP instances of moderate size (a few dozens of rows and columns), I would be very happy if he/she could provide a copy as (exact) LP file.<br /><br />Best regards,<br />ThomasThomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-72016011911344150102018-05-08T11:41:50.373-04:002018-05-08T11:41:50.373-04:00Well, if you are doing a model for the government ...Well, if you are doing a model for the government (any government), I suspect you are stuck with "irrational data". ;-) There are certainly problems which come "naturally" with rational (if not integer) coefficients, and for those an exact solver would make good sense (provided it performed adequately).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-86828367276080461672018-05-08T11:19:06.270-04:002018-05-08T11:19:06.270-04:00You are right, data has to be accurate. Concerning...You are right, data has to be accurate. Concerning my solver, I have written an LP file reader that can read arbitraty large floats and also fractions, e.g. 1234/5678.<br /><br />At least, an exact solver will (if it ever terminates) lead to results that solve the given problem exactly. If the problem is given inexactly, then of course, an exact solution is not really helpful. Using exact arithmetic makes sense if you want to prove something or need exact results to exact data. In any other case, one should use fast inexact solvers.<br /><br />My solver can in principle use any exact C++ data type. For all my tests, I use GMP rationals (mpq_class), but polymake uses an extension to that so that up to some degree, irrational data can be used. But in my opinion, irrational data only makes sense for pure linear programs, as some of the IP theory is based on rational numbers. Especially, it might be difficult to determine if some MIP is infeasible or unbounded.<br /><br />Best regards,<br />ThomasThomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47895326765558469582018-05-08T09:07:41.411-04:002018-05-08T09:07:41.411-04:00I've seen some discussions of using exact arit...I've seen some discussions of using exact arithmetic, typically assuming that the coefficients are integer (or at least rational). Of course, every coefficient is "rational" when you type it (since you only type a few decimal places), but it's unclear to me whether using exact arithmetic with approximate coefficients (and no rounding tolerance) leads to the same, better or worse solutions compared to what you get with double precision arithmetic.<br /><br />Thanks for offering to help readers with your contribution to polymake! I remember hearing something about an exact version of SCIP but did not pay close attention (and did not realize it never came to fruition).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-71402338677647003522018-05-08T01:55:48.158-04:002018-05-08T01:55:48.158-04:00You should mention that it is possible to solve MI...You should mention that it is possible to solve MIPs in exact arithmetic. It is not very fast (and often it almost takes an infinite amount of time or memory), but for some cases, it might be a viable solution.<br /><br />Some time ago, there were several very promising talks about an exact version of SCIP using iterative refinement, but unfortunately, it seems to have disappeared.<br /><br />Myself, I played around with exact arithmetic a while ago. I coded a LP-/MIP-solver that is completely based on exact data types like the GNU GMP. It can solve some problems and has partly been added to polymake (the integer part only partly in the latest development branch). If somebody ever reads this post and wants to give it a try, just drop me an email or contact me through the polymake forum. I'll be happy to share the code and give instructions how to use it.<br /><br />Best regards,<br />ThomasThomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.com