tag:blogger.com,1999:blog-8781383461061929571.comments2018-01-18T17:31:39.335-05:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1534125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-72951312172451732212017-11-21T08:13:28.555-05:002017-11-21T08:13:28.555-05:00You are missing the product $xy$, which was the st...You are missing the product $xy$, which was the starting point for the post. Also, what happens if, in the original model, it is legitimate (perhaps optimal) for $y$ to be nonzero while $x = 0$?Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6110813627731213732017-11-21T05:34:49.595-05:002017-11-21T05:34:49.595-05:00Hi Paul
If we remove the variable and the constra...Hi Paul<br /><br />If we remove the variable and the constraints regarding the 'z' variable and add the following constraint<br /><br />x*L <= y <= x*U<br /><br />and deal with the 'y' variable in the objective function I think we end up with the same solution<br /><br />If x = 0 then y = 0 just like your solution where z = 0<br /><br />If x = 1 then L <= y <= U just like your solution where z = y and L <= z <= U<br /><br />What am I missing? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-5246764025694782912017-11-18T17:49:04.589-05:002017-11-18T17:49:04.589-05:00This is not entirely surprising.This is not entirely surprising.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-43502241059379266172017-11-17T09:47:57.366-05:002017-11-17T09:47:57.366-05:00You are correct, but with combinatorial Benders cu...You are correct, but with combinatorial Benders cuts (where, say, x = 1 turns on a constraint in the subproblem and x = 0 turns it off), you typically do not want to include all the binary variables. The CBC cut would be $\sum_{i \in S} x_i \le |S| - 1$ where $\hat{x}$ is the candidate master solution and $S = \{i : \hat{x}_i = 1\}$.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-51382474191066993562017-11-17T05:19:34.530-05:002017-11-17T05:19:34.530-05:00Hi Paul, my objective function of master problem o...Hi Paul, my objective function of master problem only includes the binary variables in master problem. In this case, the subproblem will only generate feasibility cuts. According to what you said, i can have a cut like sum(x) + sum(1-x)<=|S|-1, |S|is the cardinality of the set of all the variables x. And in this case, S is not an IIS, but the set of x. Am i right? eddienoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-39182572325132052592017-11-15T21:26:48.616-05:002017-11-15T21:26:48.616-05:00Thank's for the answer sir.
I mean in "h...Thank's for the answer sir. <br />I mean in "high value difference" is the diffrence between old value and modified value have a big gap. If i have an old value with 5 km and modifed value with 2.9 km the difference is 2.1 km. <br /><br />Sulistyo ChandriantoSulistyo Chandriantohttps://www.blogger.com/profile/16571614966240196445noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-30978768933595769872017-11-15T15:54:20.641-05:002017-11-15T15:54:20.641-05:00Yes, the time indices have absolutely nothing to d...Yes, the time indices have absolutely nothing to do with whether you can linearize.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-90252535909762547792017-11-15T15:51:53.788-05:002017-11-15T15:51:53.788-05:00If by "high value difference" you mean t...If by "high value difference" you mean that the total distance of the optimal solution using the new distances is considerably less than that of the solution the old distances, that is not necessarily a surprise. If the new solution is worse, that would mean something went wrong. Your modified distances are always no longer than the original distances.<br /><br />Floyd-Warshall would be my first choice, unless the network was large enough that I needed something faster to get computation time down.<br /><br />One thing to keep in mind is that travel distance and travel time are not always strongly correlated. The shortest distance route might take you on roads that are heavily congested or that have large numbers of traffic lights. I mention this because I know that the Google map application estimates both distance and time. I don't know whether the Google maps API lets you download times as well as distances.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-45226208479570436092017-11-15T07:56:48.936-05:002017-11-15T07:56:48.936-05:00Hi Paul!
I have a query related to linearization o...Hi Paul!<br />I have a query related to linearization of product of continuous and binary variable at different times.<br /><br />My original constraint before linearization looks like this;<br /><br />for t = 1:T-1<br />X(t+1) = X(t) - X(t)*b(t+1)<br />end<br /><br />In above equation, X(t) is continuous and b(t+1) is binary. So to linearize the product, we let A = X(t)*b(t+1).<br />Note that X(t) is the value of continuous variable at time (t) and b(t+1) is the value at time (t+1). <br />My question is can we linearize the product of this kind of continuous and binary variables whose values are not of the same time interval?<br /><br />Thanks,<br />Mohan Mohan Lalhttps://www.blogger.com/profile/04018479790889820141noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-68460319715229284932017-11-14T13:59:16.694-05:002017-11-14T13:59:16.694-05:00Assuming the master problem integer variables are ...Assuming the master problem integer variables are binary, if your MIP subproblem is infeasible, you can still use the no-good cut (at least one binary variable from the master must flip value). If the subproblem is feasible but the objective value is worse than what the master solution predicted, you're somewhat screwed. There's a version of the no-good cut for optimality cuts, but it's pretty weak. Basically, for a min problem it says the master surrogate variable is at least the subproblem optimal value if no master variable changes, and at least $-\infty$ if one or more master variables do change.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.com