tag:blogger.com,1999:blog-8781383461061929571.comments2018-06-05T14:54:52.315-04:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1552125tag:blogger.com,1999:blog-8781383461061929571.post-50453387125846574932018-05-15T15:25:11.836-04:002018-05-15T15:25:11.836-04:00You know, it never occurred to me to do that. That...You know, it never occurred to me to do that. That's definitely much simpler, although fitting it without line wrapping might get tricky in some cases.<br /><br />It's also reassuring to know that I'm not the only one who couldn't find the equivalent of underbraces for the side margins. :-)Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-48761237067302990782018-05-15T15:21:46.851-04:002018-05-15T15:21:46.851-04:00I've been looking for this, but had a similar ...I've been looking for this, but had a similar experience to yours. So I just transposed the matrix and used underbraces.pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.comtag: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 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 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 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.comtag:blogger.com,1999:blog-8781383461061929571.post-27233962139778436642018-04-22T19:45:10.768-04:002018-04-22T19:45:10.768-04:00No. The "data = NULL" in the existing co...No. The "data = NULL" in the existing code declares a data argument and gives it the default value NULL. If you invoke the function without specifying the data argument, it expects the model variables to be globally defined. If you pass in a data frame in the data argument, it looks for the model variables in that data frame. This is exactly how the lm() function works.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-32787721326697110112018-04-22T19:40:19.229-04:002018-04-22T19:40:19.229-04:00Do you need to modify the function at all? Do you ...Do you need to modify the function at all? Do you remove the data = NULL?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-85040773050896212602018-04-20T16:13:51.367-04:002018-04-20T16:13:51.367-04:00You just use the optional "data" argumen...You just use the optional "data" argument to specify the data frame. So if your data frame is in the variable "whatever", you just call stepwise(..., data = whatever).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-12263828661383637212018-04-20T13:13:43.200-04:002018-04-20T13:13:43.200-04:00I am trouble integrating my own data frame. How do...I am trouble integrating my own data frame. How do I modify the function arguments with a data from generated within the script?<br /><br />Thank you!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-18215818134701197902018-04-13T17:38:49.893-04:002018-04-13T17:38:49.893-04:00"Big M" models refer to models where M a..."Big M" models refer to models where M appears in constraints; your case is a bit different. You are dealing with a multiobjective model.<br /><br />If I understand you correctly, you'll trade *any* amount (no matter how large) of extra cleaning time to avoid *any* amount (no matter how small) of kilometers of dirtiness? If that's the case, you have what are known as "preemptive priorities".<br /><br />It seems to me that, in the event the threshold is exceeded, it must be exceeded by at least the distance between the two closest stops. So you can try weighting the objective function such that a solution with the maximum possible cleaning time and zero excess kilometers is better than a solution with zero (or the minimum possible) cleaning time and excess kilometers equal to the minimum segment length between stops. As long as the coefficients are not too far apart in magnitude, I think that will work. (If you wind up with too many orders of magnitude difference in the coefficients, rounding problems may occur.)Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-50194859241790374832018-04-13T08:54:07.471-04:002018-04-13T08:54:07.471-04:00Hi Paul. Thanks for a great post.
I have a proble...Hi Paul. Thanks for a great post.<br /><br />I have a problem regarding optimization of cleaning scheduling plans for trains. The objective is to minimize time spend cleaning while trying to keep the kilometers of dirtiness below a threshold. Trains accumulate kilometers of dirtiness from stop to stop and this threshold gets exceeded sometimes due to lack of time on each step (model accounts for this using a slack variable u_s counting the number of exceeded kilometers of dirtiness). In my model, I want to make sure it always prioritizes to keep the train below the threshhold, hence punishing the model if it exceeds the threshhold, even if it results in longer cleaning times. The secondary object is to minimizing the time spend cleaning, resulting in the following objective function:<br />sum(TimeCleaning * x_s) + M*sum(u_s)<br />Where TimeCleaning is a constant in minutes, x_s denotes if cleaning takes place at stop s [binary] and u_s is a continues that counts the exceed kilometers of dirtiness at stop s.<br />Do you have any idea how I choose the value of M to make to the threshhold is exceeded at least as possible? I have considered changing u_s to be binary. If we consider a train over a full day the maximum amount of time that can be used for cleaning would be M = 24*60 = 1440 minutes.<br />However the important metric for this project is not if it exceeeds the threshhold, but rather how much it exceeds threshhold, and I can't really find any litterature on using Big M with continues variables. <br /><br />Thanks!Henrik Jørgensenhttps://www.blogger.com/profile/01414111135799433057noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-43044079111708267062018-02-27T13:40:17.226-05:002018-02-27T13:40:17.226-05:00Yes, the format/derivation of the cuts is the same...Yes, the format/derivation of the cuts is the same, and no, there is no danger that cuts derived from a feasible but suboptimal solution to the current master will cut off the optimal solution. The proof of validity of either type of cut does not depend on the proposed incumbent being optimal (in the current master) or not.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-402903013307478642018-02-27T04:51:48.994-05:002018-02-27T04:51:48.994-05:00Dear Prof. Rubin,
I really like your articles, wh...Dear Prof. Rubin,<br /><br />I really like your articles, which helped me a lot in understanding how the modern BD with callbacks works. However, I still got a little doubt. <br /><br />My question is, will the cuts (both feasibility and optimality) used in the "old" BD and in the "modern" way with callbacks be in the same format? Should we somehow alter the cuts in order to use them in the modern approach with single B&C tree? To be specific, in the modern BD with callbacks, if we generate the same-format cuts for only a feasible master solution, is it possible that these cuts can somehow cut out the optimal solution in the single B&C tree?<br /><br />Thanks a lot for your articles and looking forward to your reply.<br /><br />Best regards!GP Songhttps://www.blogger.com/profile/17689795047216679947noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-38983895588808477272018-02-20T22:36:19.075-05:002018-02-20T22:36:19.075-05:00Ah, but is there any proof that it doesn't (pa...Ah, but is there any proof that it doesn't (particularly if we extend "mother" in a way I will not explicitly type)?Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-46909522438196859822018-02-20T22:32:06.183-05:002018-02-20T22:32:06.183-05:00According to Chvatal’s Linear Peogramming (1983), ...According to Chvatal’s Linear Peogramming (1983), “There is no evidence to support the belief that the ‘big M’ stands for ‘big mother.’”Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-4844084985582065982018-01-18T17:31:39.335-05:002018-01-18T17:31:39.335-05:00Fair enough. That particular situation results in ...Fair enough. That particular situation results in an integer hull with no relative interior, so I suspect that a point in the relative interior of the LP hull is the best you're likely to do. I think the real question, though, is whether you're likely to get a valid "core point" with problems "in the wild", rather than with edge cases.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25452448886748619772018-01-18T16:47:32.783-05:002018-01-18T16:47:32.783-05:00It’s easy to come up with problems whose integer h...It’s easy to come up with problems whose integer hull is a single point, but a very large and rich LP hull.Phttps://www.blogger.com/profile/10458441676290777808noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-45002223454030284942018-01-18T16:15:16.562-05:002018-01-18T16:15:16.562-05:00Is there a particular reason you think it is not l...Is there a particular reason you think it is not likely, at least with the starting solution (or maybe an intermediate solution) of an interior point method? The final solution (before cross-over) is likely to be near the boundary.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-84119444565256626992018-01-18T07:04:53.025-05:002018-01-18T07:04:53.025-05:00> but is more likely than not inside the relati...> but is more likely than not inside the relative interior<br /><br />I don’t think that is true at all. Of course, there may be classes of (easy) problem for which it is true.Phttps://www.blogger.com/profile/10458441676290777808noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-72232624931309736072018-01-17T20:12:38.974-05:002018-01-17T20:12:38.974-05:00I'd just set the objective function to 0.
Depe...I'd just set the objective function to 0.<br />Depending on the type of IPM it may not provide a feasible solution until the very end.pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-51729408742299102832018-01-17T19:07:19.410-05:002018-01-17T19:07:19.410-05:00Interesting idea. I don't normally use interio...Interesting idea. I don't normally use interior-point solvers, and to be honest I don't know off-hand how they get started. You wouldn't really need to _solve_ the LP relaxation with an IP solver: the first feasible point would be in the relative interior (of the LP hull). You definitely would not want to go so far as to invoke crossover, but pretty much any feasible solution short of crossover might be a candidate.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-32280303057271945322018-01-17T19:01:35.139-05:002018-01-17T19:01:35.139-05:00How about solving the LP relaxation with an interi...How about solving the LP relaxation with an interior-point method? I know this can be outside of the integer hull, but is more likely than not inside the relative interior. pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.com