tag:blogger.com,1999:blog-8781383461061929571.comments2018-04-22T19:45:10.768-04:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1544125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-61546854121039184502017-12-19T14:29:00.775-05:002017-12-19T14:29:00.775-05:00In general, the subproblem is still an LP (with an...In general, the subproblem is still an LP (with an objective function that is the constant 0). Feasibility cuts (primal subproblem infeasible, dual unbounded) are unchanged, and there are no optimality cuts.<br /><br />There are some cases where people (myself included) will extend Benders decomposition, using a feasibility-only subproblem that is not an LP (and maybe not a mathematical program of any kind). Typically, in cases like this, the master problem has binary variables. Again, you only get feasibility cuts, not optimality cuts. How you generate them depends on the specific nature of the subproblem.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-61299956950953560182017-12-19T14:00:22.914-05:002017-12-19T14:00:22.914-05:00Professor Rubin,
Thank you very much for your det...Professor Rubin,<br /><br />Thank you very much for your detailed and illuminating examples of Benders Decomposition. I have gone through your posts and code in detail. Both resources have greatly increased my understanding of the decomposition technique. <br /><br />I do have one question on the material: what happens if the cost vector c (in the notation from your 2012 post) is all zeros? That is, what happens if the continuous variables do not have a cost and the subproblem is a feasibility problem rather than an LP? At first, I thought that maybe it would be okay because the dual still has an objective, but now I am not so sure. Would you only have the option of using a combinatorial benders approach, or are there more alternatives? Unknownhttps://www.blogger.com/profile/17155754130484947798noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-39488301643150434302017-12-13T09:30:19.236-05:002017-12-13T09:30:19.236-05:00:-):-)Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-81332003289021193252017-12-13T09:29:42.374-05:002017-12-13T09:29:42.374-05:00If the expression is a linear combination of decis...If the expression is a linear combination of decision variables, everything here applies. Just distribute multiplication by the binary variable across the expression. Otherwise, it's almost certainly not quadratic. It might or might not be convex, depending on the specifics of the expression.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-14988144189524637202017-12-13T01:20:21.149-05:002017-12-13T01:20:21.149-05:00you saved my life!!!!
Thank you!!!you saved my life!!!!<br />Thank you!!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-11721554975153658362017-12-13T00:29:03.344-05:002017-12-13T00:29:03.344-05:00Dear Paul,
Hope you doing great. I have a questio...Dear Paul,<br /><br />Hope you doing great. I have a question, as per your article, multiplication of continuous and binary variables renders the problem to be quadratic. In my problem, continuous variable is an expression(not decision variable), the binary variable is decision variable. What do we call this kind of problem? Is it still quadratic and non-convex?<br />Thanks,<br />Mohan Mohan Lalhttps://www.blogger.com/profile/04018479790889820141noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-659592139171985622017-11-22T10:46:12.244-05:002017-11-22T10:46:12.244-05:00No, I don't assume $y$ and $xy$ both appear in...No, I don't assume $y$ and $xy$ both appear in the objective; I don't assume anything. In general, $y$ can appear in the _constraints_ by itself, in which case your approach would make a solution containing $x=0$ and $y=17$ infeasible, when in point of fact it might be feasible in the original problem. Example: $y$ is the cargo volume of a truck, $x$ is an indicator whether the driver is new (1) or not (0), and the objective totals cargoes assigned to new drivers (sums $xy$). Your approach would prevent experienced drivers from carrying cargo.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88596611385052146512017-11-22T04:42:46.195-05:002017-11-22T04:42:46.195-05:00Thank you Paul for you response.
I totaly agree w...Thank you Paul for you response.<br /><br />I totaly agree with your second comment. <br /><br />Regarding your first comment i want to ask the following. I think the product will be the same in both solutions.<br /><br />If x = 0 then y = 0 (in my solution) = x*y = z <br /><br />If x = 1 then y = x*y = z<br />Am i correct? <br /><br />But i understand the reasoning behind your second comment. In my problem i have only the product x*y in the objective function. I think that what you say applies when you want to deal both with the product x*y and y in the objective function.<br />Anonymousnoreply@blogger.com