tag:blogger.com,1999:blog-8781383461061929571.comments2017-11-18T17:49:04.589-05:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1517125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-87314206833498929042017-11-10T05:25:46.572-05:002017-11-10T05:25:46.572-05:00The form of CBC is: sum(x) + sum(1-x)>=1. I don...The form of CBC is: sum(x) + sum(1-x)>=1. I don't see the constant term.<br />In fact, in the first paper proposing CBC, the author didn't mention about this aspect(maybe i missed something...). In order to find the detail about the implementation, i read a lot of papers employing this technique, but i still couldn't find it. Do you know any paper or technique documents publishing details about this algorithm? Or have you had any experience in implementing this algorithm? If so, could you please share your code or the procedure of the algorithm with me? <br />My mail: eddie.westlife@gmail.com<br />I really appreciate your help, it means a lot for our beginners in this field.eddienoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-84351126794021916252017-11-09T17:14:05.502-05:002017-11-09T17:14:05.502-05:00I think *reading* global variables is not a proble...I think *reading* global variables is not a problem. You're right, though, that writing global variables is a crash waiting to happen.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-45921466173528336592017-11-09T14:39:25.584-05:002017-11-09T14:39:25.584-05:00Another common reason that routines aren't thr...Another common reason that routines aren't thread safe is that they use global variables (which is shared data.) Brian Borchershttps://www.blogger.com/profile/18216044824246034466noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-82029204404868661122017-11-08T02:42:58.614-05:002017-11-08T02:42:58.614-05:00Sorry I missed a b in the last eq:
SOC_min_SW*b &l...Sorry I missed a b in the last eq:<br />SOC_min_SW*b <=SOC(t)*b <= SOC_max_SW*bMohan Lalhttps://www.blogger.com/profile/04018479790889820141noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77872567807355154972017-11-07T23:19:13.263-05:002017-11-07T23:19:13.263-05:00Thanks for your reply. I got you point but still s...Thanks for your reply. I got you point but still some confusion..<br />So in that case if CPLEX allows using binary variable in the formulation then my problem should look something like this;<br />If b = 0<br />then<br />SOC(t+1) = SOC(t) + P(t), where:{SOC_min <= SOC(t) <= SOC_max}<br />otherwise<br />SOC(t+1) = SOC_inc(t+1)<br />Does above logic make sense in CPLEX? If yes then how do I include the bellow constraint to the problem;<br />SOC_min_SW*b <=SOC(t) <= SOC_max_SW*b this constraint means, b can only be equal to 1, if this constraint is satisfied.<br />How does the combination of above if--then.. and this constraint will look like in CPLEX?<br /> Mohan Lalhttps://www.blogger.com/profile/04018479790889820141noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-11080249341389997232017-11-07T11:37:37.846-05:002017-11-07T11:37:37.846-05:00The right-hand sides of those constraints are mult...The right-hand sides of those constraints are multiplied by the dual values, summed up, and contribute to the constant term in the CBC cut.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-44151355178539790992017-11-07T11:35:21.174-05:002017-11-07T11:35:21.174-05:001. Yes. Linearize each term separately. Suppose th...1. Yes. Linearize each term separately. Suppose that we let z = SOC(t) * (1-b). Use the formula in the post (with SOC(t) replacing y and 1-b replacing x). If b = 1 (x = 0), the first two constraints force z = 0 and it does not matter what L and U are (so long as 0 is feasible in the third and fourth constraints). So you will most likely be safe using the bounds on SOC(t) when b = 0.<br /><br />2. I can't speak for other solvers, but CPLEX now does have indicator constraints (if ... then ...). In the Java API, look for IloModeler.ifThen().<br /><br />3. Sorry, I forgot what very little I knew about Lyapunov optimization some 40 or so years ago (lack of use).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77991074513406199782017-11-07T08:29:59.388-05:002017-11-07T08:29:59.388-05:00Dear Prof Rubin,
As to the constraints not tied to...Dear Prof Rubin,<br />As to the constraints not tied to binary variables, if we include them into IIS, how could we generate CBC which is related to binary variables? For me, the infeasibility of constraint is caused with its associated binary variable. That's the reason why we want to generate a cut by changing the value of the binary variable to avoid this kind of infeasibility. If we include a constraint which has nothing to do with binary variable, how could we generate a CBC cut for this constraint?eddienoreply@blogger.com