tag:blogger.com,1999:blog-8781383461061929571.comments2017-02-16T13:53:05.950-05:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1367125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-23531139743906218582017-01-18T19:06:28.497-05:002017-01-18T19:06:28.497-05:00You appear to clear your subproblem model right be...You appear to clear your subproblem model right before exiting the routine. Are you sure that doesn't delete stuff you need for the next subproblem?Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77705302504074091322017-01-18T19:02:48.808-05:002017-01-18T19:02:48.808-05:00Thanks for your comment. Since any subproblem_i i...Thanks for your comment. Since any subproblem_i is feasible, I expect that be true always. So I thought a test is not required. Just to mention, this is my GenCut:<br /><br />void GenCut(const IloVar2Dim X, const IloNum2Dim Xsol, IloInt i_, IloCplex Cplx_subp, const IloNumVarArray U, const IloNumVarArray W,IloObjective SubObj, IloExpr cutLhs, IloNum& cutRhs)<br />{<br /> IloInt k ,j, nN2 = N*N;<br /> IloModel SubpMod = Cplx_subp.getModel();<br /><br /> SubpMod.remove(SubObj);<br /> IloExpr objExpr= SubObj.getExpr();<br /> objExpr.clear();<br /><br /> for(j=0;j < N; j++) {<br /> objExpr += W[ i_ * N + j];<br /> for (k = 0; k < N ; k++ ){<br /> objExpr -= Xsol[i_][k] * U[i_ * nN2 + j*N + k];<br /> } <br /> }<br /><br /> SubObj.setExpr(objExpr);<br /> SubpMod.add(SubObj);<br /> objExpr.end();<br /> <br /> Cplx_subp.solve();<br /><br /> cutRhs = 0;<br /> for(j=0; j< N ; j++)<br /> cutRhs +=Cplx_subp.getValue(W[i_ * N + j]);<br /> IloNum valCutLhs=0;<br /> <br /> cutLhs.clear();<br /> for (j = 0; j < N; j++ )<br /> for (k = 0; k < N; k++ )<br /> cutLhs += X[ i_ ][k] * Cplx_subp.getValue(U[i_ * nN2 + j*N + k]) ; <br /><br /> Cplx_subp.clear(); <br />} // END GenCut<br /><br />I will post it on CPLEX Forum.<br /><br />Thanks.Diako Baloochhttp://www.blogger.com/profile/12706547087077901507noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6488438609104562652017-01-18T13:31:47.959-05:002017-01-18T13:31:47.959-05:00Diako,
Your approach seems correct: loop through ...Diako,<br /><br />Your approach seems correct: loop through the subproblems and add a cut for each one *if* a cut can be generated. (I don't see any test in your loop that GenCut actually produces a cut on subproblem i.)<br /><br />If the problem is not a null argument due to GenCut not finding a cut, then I suggest taking your question to the CPLEX user forum. There's a link to the IBM forums in the right margin, near the top; from there, you can drill down to the CPLEX forum. The comments section of a blog is ill-suited for debugging.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-35890743944173655262017-01-18T01:40:29.285-05:002017-01-18T01:40:29.285-05:00Hi Paul,
Thanks for sharing your thoughts on Bende...Hi Paul,<br />Thanks for sharing your thoughts on Benders Decompostion. <br /><br />I am trying to use Benders Decompostion for my problem, in which the subproblem can be decomposed to N smaller problems, solvable in parallel. In fact the subproblem has N^3 varaibles and N^3 constraints. And the matrix of constraints is only independent blocks (not L shaped). The subproblem can be decomposed into N problems, each N^2 variables and N^2 constraints. I want to use IloLazyConstraintsCallback to add these different N cuts. Part of my code in IloLazyConstraintsCallback is:<br />for ( i=0 ; i < N; i++){<br /> GenCut(X, Xsol, i , cplx_subp, U, sub_Obj , cutLhs, cutRhs); <br /> add(cutLhs+ eta[i] >= cutRhs); <br /> }<br /><br />However Cplex throws an error in second iteration of the loop when calls GenCut. I am not sure how IloLazyConstraintsCallback works, whether it is smart enough to decompose the subproblem into N problems, or not. Do you have any suggestion how one can get this done? I appreciate any thought.<br /><br />Regards,<br /><br />DiakoDiako Baloochhttp://www.blogger.com/profile/12706547087077901507noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-40571997300224933002016-12-22T16:48:36.194-05:002016-12-22T16:48:36.194-05:00If you repeat enough times, I think it should.If you repeat enough times, I think it should.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25850748183979087282016-12-22T14:36:38.501-05:002016-12-22T14:36:38.501-05:00For clarification, I'm talking about enumerati...For clarification, I'm talking about enumerating configurations of a subset of the variables (regardless of the value of the rest). cladelpinonoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47093164838879319632016-12-22T13:34:25.592-05:002016-12-22T13:34:25.592-05:00What makes you think that? I looked at one of Matt...What makes you think that? I looked at one of Matteo Fischetti's papers (referenced in Andrea Tramontani's slide show from INFORMS 2016), and it appears that Fischetti et al. use a one-tree approach with the "optimal" solution mentioned by Tramontani being the optimal solution to the node LP (not to the master MIP). I have to admit, though, that I just skimmed Matteo's paper. I'll need to read it more carefully later.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-70762086537017029302016-12-22T07:25:39.287-05:002016-12-22T07:25:39.287-05:00What about adding "cuts" via the diversi...What about adding "cuts" via the diversity filter, repeatedly calling populate ? <br /><br />1. Populate without filter (probably to a fixed number limit)<br />2. From this pool get the *different* "supports" for the interesting variable subset. <br />3. Add a diversity filter over the variable subset with this supports<br />4. Repeat<br /><br />Would this work ?cladelpinonoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47455741397319157742016-12-20T14:35:44.448-05:002016-12-20T14:35:44.448-05:00And it appears they implemented Bender's using...And it appears they implemented Bender's using the traditional (as opposed to the single-tree) approach. Maybe in future versions they also add the possibility of using the single-tree.<br />Alexandre Floriohttp://www.blogger.com/profile/11545307166178046828noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-83432546899191659452016-12-19T19:15:24.087-05:002016-12-19T19:15:24.087-05:00Dejene,
Yes, you can linearize each product. In t...Dejene,<br /><br />Yes, you can linearize each product. In this particular case, though, it may not be the most efficient approach. A piecewise linear expression can be expressed as a Type 2 Special Ordered Set (SOS2). See the portion of https://orinanobworld.blogspot.com/2010/10/piecewise-linear-functions-in-math.html devoted to SOS2. Many solvers have explicit SOS2 support, and in fact some (including CPLEX) have explicit support for piecewise linear functions.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-13892244921936087122016-12-19T18:51:28.858-05:002016-12-19T18:51:28.858-05:00Reposted
Dear Paul,
How I may linearize the foll...Reposted <br />Dear Paul,<br /><br />How I may linearize the following with the above concept.<br /><br />z=b1d1+...+bndn<br /><br />where bi are binary variables and di's are real variables. It is possible to compute upper bound and lower boud for each product.<br /><br />To give further explanation on the problem, the di's are line segments to approximate a convex curve. The line segments can be represented by di=mix+c, I want to select one of these line segments based on the value of x which is a function of some decision variable. The selected segment is used to evaluate the value of di which is used in a constraint for my optimization. I approached the problem by introducing a binary variable to select a given segment which is set to 1 when it is selected and set to 0 otherwise. This means I have an expression d=b1d1+...+bndn; b1+b2+..+bn=1;<br />Dejene Boruhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-40507847452264582412016-12-19T18:40:27.917-05:002016-12-19T18:40:27.917-05:00This comment has been removed by the author.Dejene Boruhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-69661353173912373372016-12-19T18:30:10.217-05:002016-12-19T18:30:10.217-05:00Sorry for typo on your name PaulSorry for typo on your name PaulDejene Boruhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-70858492418222798132016-12-19T17:38:40.720-05:002016-12-19T17:38:40.720-05:00... waiting for "Raul" to answer ...... waiting for "Raul" to answer ...Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-74232654105165318372016-12-19T17:29:50.361-05:002016-12-19T17:29:50.361-05:00This comment has been removed by the author.Unknownhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.com