tag:blogger.com,1999:blog-8781383461061929571.comments2017-03-28T18:22:01.564-04:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1381125tag:blogger.com,1999:blog-8781383461061929571.post-20375793958431515612017-03-28T18:22:01.564-04:002017-03-28T18:22:01.564-04:00For the "one-tree" (callback) approach, ...For the "one-tree" (callback) approach, CPLEX maintains the correct lower bound. There is nothing for you to do in that regard.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-67108066105768333522017-03-25T22:32:11.497-04:002017-03-25T22:32:11.497-04:00Thank you Prof. Rubin,
Your response helped me and...Thank you Prof. Rubin,<br />Your response helped me and my prof think deeper on it and realize the idea that we are solving only 1 Master problem and hence we can't solve it to optimality before any iteration(it would be optimal only at the last stage ). The unexplored branch and bound tree is saved when callbacks are called.<br /><br />So, for a Minimization MILP,<br />how do we update the lowerbound obtained from the problem(upperbound is from dual sub problem):<br />by the solution values of the un-fathomed non-integer leaves of the solution tree(of master problem) which have the best bound when the callback is called? Loy Lobohttp://www.blogger.com/profile/17872532835246125851noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-43307543318518002772017-03-24T13:36:57.485-04:002017-03-24T13:36:57.485-04:00Sorry, I"ve never used Gurobi, JuMP or Julia,...Sorry, I"ve never used Gurobi, JuMP or Julia, so I have no idea. I don't even know which callbacks Gurobi provides. Your phrase "optimal solution of the iteration" confuses me a bit. If you mean that only want to invoke the callback for an integer-feasible solution that is an optimal solution to the node LP, I would expect that to be standard behavior for the solver. (That's what happens with CPLEX for most integer-feasible solutions, excepting those found by heuristics.) If you mean you only want the callback invoked when the master problem has been solved to what the solver thinks is optimality, you shouldn't be using callbacks at all. The approach there is solve (normally) - test solution - generate cut and add to master - solve again (until a winner is found).Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-57930950687467043772017-03-24T00:29:09.546-04:002017-03-24T00:29:09.546-04:00Hi Professor Rubin,
I'm working on Bender'...Hi Professor Rubin,<br />I'm working on Bender's decomposition of a MILP on the Julia interface with JuMP package on a Gurobi solver. In the example here, the callback function of lazy constraints is called when the master problem reaches an integer feasible solution(of an iteration). However, the function should ideally be called only at an optimal solution of the iteration. Could you suggest the method to call the function at optimal solutions for each iteration of master problem model? Following is the description of the code:<br /><br />#loading of the solver and JuMP<br />loading of master Problem<br /><br />function addBendersCut(cb)<br />#subproblem loading and solving<br />#test for global optimum<br />#lazy constraints<br />end<br />addlazycallback(masterProblemModel,addBendersCut) <br />statusMP=solve(masterProblemModel)<br /><br /> <br /><br />Loy Lobonoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-28043707448110058732017-03-22T06:53:50.827-04:002017-03-22T06:53:50.827-04:00thank you very much.
thank you very much. <br />Kai Kühnelhttp://www.blogger.com/profile/06404122187342934132noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-52953446208469076142017-03-21T16:11:38.617-04:002017-03-21T16:11:38.617-04:00The error message is correct. What I said was that...The error message is correct. What I said was that the product of a binary variable and a continuous (or general integer) variable can be linearized ... by you. You apparently have not done so. CPLEX will not do it for you.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-2474715301695427162017-03-21T10:13:39.659-04:002017-03-21T10:13:39.659-04:00I have a MILP which has a not convex constraint. B...I have a MILP which has a not convex constraint. But as you said if one decision variable is binary there is no problem. But still this error appears : CPLEX Error 5002: q1 is not convex.<br /><br />{int} T= ...;<br />{int} J=...;<br /><br /> int f[T]=...;<br /> int r[T]=...;<br /> int d[J][T]=...;<br /><br /><br /> dvar boolean y[J][T];<br /> dvar boolean q[T];<br /> dvar int+ x[J][T];<br /> dvar int+ z[T0];<br /> dvar int+ theta[J][T];<br /><br />z[0] == 6; <br /><br /> forall (t in T)<br /> z[t] == z[t-1] + sum(j in J)(x[j][t] - d[j][t])*y[j][t] - r[t]*q[t] - f[t];Kai Kühnelhttp://www.blogger.com/profile/06404122187342934132noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-14811202685413810972017-03-19T15:20:26.067-04:002017-03-19T15:20:26.067-04:00Thanks for the kind words.
1. I don't have an...Thanks for the kind words.<br /><br />1. I don't have an "inside" knowledge about the implementation details, but judging from the solver log, my guess would be that they are using the one tree (callback) approach. The solver log shows repeated attempts to presolve at the start (I have no idea why it presolves more than once), but once it gets serious about iterating, adding cuts at the root node, there is no indication of further presolving, even after adding a Benders cut. If it were using the traditional approach, after adding a Benders cut I would expect to see a restart complete with presolving of the (new) root node.<br /><br />2. The proof for the one tree (callback) method is essentially the same as the proof for the original method. In broad terms (omitting some details about edge cases), assume that the integer variables are bounded and the problem is feasible. The master problem search tree has a finite number of nodes, so Benders will eventually stop. You just have to prove that it cannot stop with an infeasible solution (because that solution would have been cut off by a feasibility cut) or a suboptimal solution. Proving the latter is a bit more work, but not hard. It could only happen if a solution with an overly charitable value for the surrogate variable for the objective contribution of the subproblem were accepted, and that can't happen if the callback is doing its job (the surrogate variable would be tightened by optimality cuts).Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-51743743877517229722017-03-18T21:20:39.716-04:002017-03-18T21:20:39.716-04:00Thanks for posting such an impressive and helpful ...Thanks for posting such an impressive and helpful blog. I also have two questions. <br /><br />1. The first one is very related with your reply to Alexandre. Does CPLEX 12.7 develop the modern Bender decomposition with lazy constraints callback (just similar with your blog "Benders Decomposition Then and Now" six years ago), instead of the classic benders decomposition (solving the master problem from scratch). According to your experimental result, especially the second plot in this blog, the "manual" approach is similar to three CPLEX approaches with different parameter settings in terms of solution time. Maybe the difference is because of the stronger cuts generated by CPLEX itself, as said in your blog. I think it is most likely that CPLEX 12.7 is using lazy constraints callback to achieve its inbuilt benders decomposition.<br /><br />2. The second question is Why the lazy constraint callback is correct and provably to find the originally optimal results. I means that is it guaranteed that the modern Benders decomposition with callback must have the same result with the classic benders decomposition?<br /><br />ThanksYao Zhanghttp://curent.utk.edu/people/power-systems-students/zhang-yao/noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-49805278517075350782017-03-10T16:54:46.625-05:002017-03-10T16:54:46.625-05:00You're welcome. I'm a bit baffled that it&...You're welcome. I'm a bit baffled that it's still an issue, but relieved that at least the fix still works.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25031169270903074332017-03-09T22:02:56.480-05:002017-03-09T22:02:56.480-05:002017 and this is still a working fix. Thank you.2017 and this is still a working fix. Thank you.Aaronhttp://www.blogger.com/profile/08405714085143720518noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25628854685148393452017-03-08T03:09:42.365-05:002017-03-08T03:09:42.365-05:00Many thanks for spreading the word about the great...Many thanks for spreading the word about the great work our MSU students are doing in the area of microfinance. Also, thanks for joining our KIVA team! Go Green! Go White! Paulette StenzelMariposahttp://www.blogger.com/profile/09246611208853497520noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-10255873194619175442017-03-01T02:51:13.834-05:002017-03-01T02:51:13.834-05:00Thank you very much Paul.Thank you very much Paul.Georgenoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-4767654166761547022017-02-23T11:58:50.027-05:002017-02-23T11:58:50.027-05:00Yes. If $L=0$, it can be done with additional cons...Yes. If $L=0$, it can be done with additional constraints but no new variables. if $L>0$, you'll need more binary variables (to distinguish between $w_i>0$ and $w_i<0$. See this post: https://orinanobworld.blogspot.com/2012/07/modeling-absolute-values.html.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-14555771521013569542017-02-22T15:53:38.165-05:002017-02-22T15:53:38.165-05:00Hi Paul,
I have a mixed integer quadratic problem...Hi Paul,<br /><br />I have a mixed integer quadratic problem where i need to minimize the following function:<br /><br />F(w) = 0.5*w'*H*w - w'f<br />s.t. L*v <= abs(w) <= U*v<br /><br />v: Nx1 binary variable<br />w: Nx1 continuous variable<br />L: lower bound<br />U: upper bound<br />H: NxN positive semidefinite covariance matrix<br />f: Nx1 vector of expected returns<br /><br />Is there a way to remove the absolute value from the constraint? Georgenoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-11091024576671352872017-02-16T13:53:05.950-05:002017-02-16T13:53:05.950-05:00Per an IBM source: it is not available in CPLEX 12...Per an IBM source: it is not available in CPLEX 12.7, but is scheduled for addition in a future release (likely the next one).Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-61714800443862758382017-02-10T02:33:43.105-05:002017-02-10T02:33:43.105-05:00Thanks for the quick reply. Indeed, it would be in...Thanks for the quick reply. Indeed, it would be interesting to have it in the future!Martimnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-83746852798064976492017-02-09T17:46:40.933-05:002017-02-09T17:46:40.933-05:00I'm not sure I'm understanding the questio...I'm not sure I'm understanding the question. If you mean that you are generating all the cuts yourself via lazy constraint callback (not using the new feature to have CPLEX generate any Benders cuts) and want to make them a permanent part of the master problem, you just have to store them in an array (with global scope) while also adding them in the callback, and then, after the solution has ended and you've recorded the final solution, add them to the master problem as you would with any other constraints. I'm not sure why you would want to do that.<br /><br />If you're saying that you want to have CPLEX generate Benders cuts and also generate your own Benders cuts, I'm not sure about the answer. Automated Benders is applied to the full model, not to a restricted master problem, so I don't see a way to do it (nor do I see a reason to).Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55439748169742666182017-02-09T17:41:02.674-05:002017-02-09T17:41:02.674-05:00Martim: I'm fairly certain (though not complet...Martim: I'm fairly certain (though not completely positive) that it doesn't exist (yet). I raised the question with a contact at IBM. Maybe we'll see it in a future version.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-22529634253042215812017-02-09T13:50:13.673-05:002017-02-09T13:50:13.673-05:00Prof Rubin,
How do we implement a benders decompo...Prof Rubin,<br /><br />How do we implement a benders decomposition when we want to add constraints into the master problem itself via callbacks apart from the Benders cut being added via a lazy callback?<br /><br />Thanks <br />Kaarthikhttp://www.blogger.com/profile/13446248381360135437noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-59005113050438512972017-02-09T05:04:28.488-05:002017-02-09T05:04:28.488-05:00I was wondering: Is there any way to get from Cple...I was wondering: Is there any way to get from Cplex the number of Benders cuts that were generated? Can't seem to find that option.Martim Joyce-Moniznoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-54619619877028229132017-02-02T17:07:43.039-05:002017-02-02T17:07:43.039-05:00Yes, you can "chain" max operations as y...Yes, you can "chain" max operations as you described, adding one binary variable for each $z_j$. You can equivalently start with one binary variable for each original variable ($w_a$ corresponding to $a$, $w_b$ corresponding to $b$, ...) with the constraint $w_a + w_b + ... = 1$ (exactly one variable is picked to be maximal), and similar upper bound constraints as before (where the original $w$ would now be $w_y$ and $1-w$ would be $w_x$). The lower bounds $L_a$ etc. would be as before, while the upper bounds would change so that, for example, $U_y$ in the first upper limit constraint would be replaced by the largest upper bound of any variable other than $x$, while $U_x$ would be replaced by the largest upper bound of any variable other than $y$. Either approach should work.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-4674733848024277432017-02-02T12:40:53.506-05:002017-02-02T12:40:53.506-05:00Very useful !
It seems to work for several variab...Very useful !<br /><br />It seems to work for several variables :<br /><br />z0=max(a,b)<br />z1=max(z0,c)<br />z2=max(z1,d)<br />....<br /><br />a,b,c have same bounds<br /><br />Isn't it ?<br /><br />RegardsFabrice Clementhttp://www.blogger.com/profile/17569878090717475070noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-40543365793239870952017-02-02T12:39:36.717-05:002017-02-02T12:39:36.717-05:00This comment has been removed by the author.Fabrice Clementhttp://www.blogger.com/profile/17569878090717475070noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-67440206908377573972017-01-19T00:37:08.536-05:002017-01-19T00:37:08.536-05:00Oops. Yes, that's right. Thanks for your comme...Oops. Yes, that's right. Thanks for your comment. I fixed that, and now I don't have the error anymore. <br /><br />Obviously, the solutions of the duals of suproblems must be positive. However, Cplex thinks zero is optimal! Now I need to spend time to figure out the issue.<br />Diako Baloochhttp://www.blogger.com/profile/12706547087077901507noreply@blogger.com