tag:blogger.com,1999:blog-8781383461061929571.comments2017-12-13T09:30:19.236-05:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1525125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-53357964408209293692017-11-14T13:54:32.974-05:002017-11-14T13:54:32.974-05:00Sorry, your question is off topic.Sorry, your question is off topic.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-48461423330675456582017-11-14T13:49:30.706-05:002017-11-14T13:49:30.706-05:00I have no idea.I have no idea.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88802166224927826832017-11-13T22:56:09.655-05:002017-11-13T22:56:09.655-05:00Hello, what if the asymmetric distance matrix is g...Hello, what if the asymmetric distance matrix is generated in google map and the matrix not satisfy triangle inequality. I already check which node that violate the triangle inequlaity and I update the side that violate tiangle inequality like Floyd-Warshall algorithm (sum of antohter two side). <br /><br />But i'm not sure wether by changing the distance will affect on algorithm cause sometime the new value of distance have high value diffrence with the old value. Is my method to fix the triangle inequality in distance matrix valid ?.<br /><br />Currently I'm developing a program in C#.NET for delivery to customers using CW saving algorithm by Altinel and Oncan. I'm in computer science program so my OR knowledge limited.<br /><br />Sory if I vioalate the Ground rule for comments.<br /><br />Sulistyo Chandrianto,<br />Thank YouSulistyo Chandriantohttps://www.blogger.com/profile/16571614966240196445noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-91592003799393198842017-11-13T20:28:38.772-05:002017-11-13T20:28:38.772-05:00Dear Rubin,
I hope you are doing great. Can you pl...Dear Rubin,<br />I hope you are doing great. Can you please help me in approximating following equation<br /><br />A/B = C<br />All A,B & C are variables <br />Bounds are as follow<br /> 0<=A=<50<br /> 0<=B=<50<br /> 0<=C=<1Rufihttps://www.blogger.com/profile/08205387292541214111noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-21708240580884471192017-11-13T09:11:15.548-05:002017-11-13T09:11:15.548-05:00That's exactly the cut i want. What's more...That's exactly the cut i want. What's more, i'd like to let you know that i put one integer variable in master problem, and another integer variable plus one real variable in sub-problem. In this case, we can't get the dual value for the constraint infeasible, because there is a integer variable in my sub-problem. I have been getting stuck at this point for a long time... Any ideas?Pauleddienoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-83749196678439276902017-11-12T23:26:04.758-05:002017-11-12T23:26:04.758-05:00Thanks for reply! One more last question, how do w...Thanks for reply! One more last question, how do we define this constraint using "CVX"?Mohan Lalhttps://www.blogger.com/profile/04018479790889820141noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-5177058354762780182017-11-12T13:37:44.587-05:002017-11-12T13:37:44.587-05:00Your latest version of the constraint would be &qu...Your latest version of the constraint would be "if b = 1 then SOC_min_SW <=SOC(t) <= SOC_max_SW".Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-42798880237000641692017-11-10T18:11:59.597-05:002017-11-10T18:11:59.597-05:00Just looked, and I can't find any code that us...Just looked, and I can't find any code that uses CBC directly. I have some code where combinatorial cuts are being used, but they're being generated so indirectly (and there's so much other stuff going on, obscuring the CBC aspect) that at this point it would take a couple of hours for me to explain it to anyone (if I could).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-87988002419796994592017-11-10T17:39:35.871-05:002017-11-10T17:39:35.871-05:00Sorry, you're right that a CBC cut as done by ...Sorry, you're right that a CBC cut as done by Codato and Fischetti is a type of "no good" cut (having the form you indicated. I was thinking of a different way to generate a feasibility cut using their approach of excluding constraints where the binary variable has value 0. You're a bit off target thinking "the infeasibility of constraint is caused with its associated binary variable". It's not one constraint that is infeasible; it's the collection.<br /><br />I'll see if I have relevant code I can share, and if so will contact you via email. If I do, it will be Java code (using CPLEX).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.com