tag:blogger.com,1999:blog-8781383461061929571.comments2021-10-26T11:40:37.160-04:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1754125tag:blogger.com,1999:blog-8781383461061929571.post-88819629114380302012021-10-26T11:40:37.160-04:002021-10-26T11:40:37.160-04:00First, thanks for the kind words. I am not at this...First, thanks for the kind words. I am not at this year's INFORMS national meeting, but if you spot me at a future meeting, please feel free to say 'hi'.<br /><br />As to your question, this gets into some technical stuff that I'm not fully qualified to answer because (a) I don't know all the details of how solvers work (much as I don't know exactly how an internal combustion engine works, but still manage to drive my car) and (b) it involves some details that I'm pretty sure IBM considers trade secrets. That said, I think it is at least in part a question of how CPLEX handles preprocessing. The problem CPLEX is solving is different from the one you fed it. When the callback is invoked, CPLEX essentially translates the solution it found to fit your original model, and when you add new lazy constraints it tries to translate those to fit the model it is actually solving. Apparently the latter step is not guaranteed to succeed.<br /><br />The good news is that, should it fail to enforce the lazy constraints and land on another candidate solution which violates them, the callback will again be invoked, and you will have the opportunity to "rediscover" those constraints. So there should be no danger of getting a final solution that is infeasible; the only danger is that the solution process may be inefficient due to unnecessary repetition.<br /><br />I don't think I've ever checked whether a lazy constraint callback (legacy or generic) is forced to rediscover the same constraints, but my feeling is that it is at worst a rare occurrence. If for some reason you think it is happening frequently in one of your problems, and assuming the effort involved in generating the lazy constraints is nontrivial, a possible workaround is to store your lazy constraints in user memory. When the callback is invoked in the candidate context, you can start by evaluating all your stored lazy constraints to see if any are violated. If so, just reject the candidate. If not, go ahead and do the computations to see if the candidate is feasible or if a new violated lazy constraint can be found.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88229218784227414532021-10-26T08:53:09.878-04:002021-10-26T08:53:09.878-04:00Dear Prof. Rubin,
This is an excellent blog that I...Dear Prof. Rubin,<br />This is an excellent blog that I follow for some time. (In fact, once I saw you at INFORMS AM passing by.)<br /><br />I understand the difference between lazy constraints and user cuts.<br />However, in CPLEX 20.1, I got a little bit confused with the generic callbacks: generic callbacks: https://www.ibm.com/docs/en/icos/20.1.0?topic=callbacks-what-can-you-do-generic-callback.<br />The example xbendersatsp2.c uses CPXcallbackrejectcandidate to add the cuts. However, in the description of CPXcallbackrejectcandidate it mentions:<br />"There is no guarantee that CPLEX will use the constraints that you specify. CPLEX will try to do so, but for technical reasons, it is not always possible to use the constraints. You can thus not assume that in subsequent callback invocations the candidate solutions satisfy the constraints you specified here."<br /><br />This statement goes against my idea of lazy constraints, which are used to accept/reject a new incumbent after begin added to the B&C.<br /><br />Somehow, it seems that he constraints added through CPXcallbackrejectcandidate eliminate the current integer solution but may not be used after.<br /><br />So, using CPXcallbackrejectcandidate we can end with a solution that does not respect the constraints added by that function?<br />What is the impact of this procedure in the Benders decomposition using one master problem?<br />On one hand, every time you get an integer solution you validate it with CPXcallbackrejectcandidate. On the other hand, you want the constraints added through that function to guide to feasible integer solutions.<br /><br />Can you please comment on these issues?<br /><br />Many thanks,<br />Ricardo Lima<br /> <br />Ricardo Limahttps://www.blogger.com/profile/10963241044596397107noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-71100881465074378532021-07-13T11:33:40.558-04:002021-07-13T11:33:40.558-04:00You can use bisection (which may be faster than a ...You can use bisection (which may be faster than a fixed step approach) to find the lower bound *if* you have a feasible value you can use as the upper limit of the search interval. You cannot use bisection is you are starting with an interval where both endpoints are infeasible (because, after checking the midpoint, you would have no idea which half interval to keep). So you need a feasible value of $q_1$ before you do anything else. I suppose you could randomly generate values of $q_1$ in the initial interval until you got a feasible one, then use bisection (twice) to get feasible lower and upper limits.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47740923163274501132021-07-12T19:36:10.897-04:002021-07-12T19:36:10.897-04:00Thank you for the detailed explanation. Overall me...Thank you for the detailed explanation. Overall method is clear to me. I would like to clarify one point regarding the interval of uncertainty. <br /><br />In the R code, I note that you assume a step size of 0.1 and keep increasing the value of q1 by this amount until you find a feasible value. That code calls findQ2() function which in turn calls findX(). To find the upper bound, you use bisection method with a bracket of [q1min,100] to find a root for q1. <br /><br />I do not understand why different methods are used for lower and upper bounds. Can the bisection method be used to find the lower bound as well for q1? <br /> Marryhttps://stackexchange.com/users/20573714/marrynoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6540808923071281852021-07-08T20:07:23.681-04:002021-07-08T20:07:23.681-04:00Hi,
(1) I start out by setting upper limits of 10...Hi,<br /><br />(1) I start out by setting upper limits of 100 for $q_1$ and $q_2$, snatched out of thin air. In practice, the context of the model (what $q_1$ and $q_2$ stand for) would hopefully let you set reasonable upper bounds. To get an initial lower bound for $q_1$, I find the maximum value of the left side of (1). In the R code, I assume the $p_i$ are nonnegative, in which case the left side is maxed out when all $x_i=1$. I then solve (1) to get a value for $q_1$, which is the smallest possible choice for $q_1$. Neither the lower nor upper bound is automatically feasible, so I do a line search up from the lower bound and a separate line search down from the upper bound to get the lowest and highest values of $q_1$ than are feasible.<br /><br />(2) The objective function for golden section is $q_1 + q_2$, the original objective function.<br /><br />(3) At each step of the golden section search, we get a new candidate value for $q_1$. I call the findQ2() function to find the corresponding value of $q_2$. That function in turn calls findX(), which solves an LP to get $x$. So there is an LP solution at each step of the GS search.<br /><br />I hope that clarifies things.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77481053532991317202021-07-08T19:31:24.429-04:002021-07-08T19:31:24.429-04:00I happens to be the one who asked the question on ...I happens to be the one who asked the question on OR StackExchange. I didn't realise that you have written a blog here. I think you are being modest when you say "low-tech" solution. To me it looks like a very elegant solution. Using your assumption for β, I get the same answer with Couenne solver. I see that you have given your R code as well but I don’t understand R. I can follow the code up to the point you solve the LP to find x, and then you find a lower bound for q1. If I may ask some questions on the method:<br />(1) What bracketing interval you assume to find feasible values for q1 using line search when setting the (feasible) lower bound and upper bound? <br />(2) What is the objective function for the golden search? Is it given by LHS – RHS of (1) that you minimize?<br />(3) Are you iteratively solving the LP based on candidate solutions for q1 and q2 until you hit the minimum based on Golden Search?<br />Marryhttps://stackexchange.com/users/20573714/marrynoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-63135801973053046222021-07-04T16:24:34.761-04:002021-07-04T16:24:34.761-04:00I'm curious myself about why the GA is not com...I'm curious myself about why the GA is not competitive (at least on small problems). It likely has something to do with the way the solution is encoded. The encoding you chose is the obvious one, and really about the only one I can see. I vaguely recall reading something, back in the early days of GAs, that emphasized the importance of an encoding that captured the right information in the right way. It may be that, with this encoding, crossover does not work well because gluing together the first half of a good solution and the second half of a good solution too often produces a poor solution (due to the min difference dropping as a result of the placement of the last few points in the first part and the first few points in the second part, regardless of how well the rest of the points are spaced).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89485487252119269632021-07-04T15:24:11.593-04:002021-07-04T15:24:11.593-04:00Thanks for this. I am afraid I updated my blog ent...Thanks for this. I am afraid I updated my blog entry and this now shows your more efficient, and also more elegant sorted objective. But, indeed: I admit that my first attempt was a double loop over all possible combinations of 2 points. Another, unrelated question I am still pondering: why is ga not working very well on this problem? Can we predict this or do we just have to try? Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-23541453620441477442021-04-07T05:32:04.818-04:002021-04-07T05:32:04.818-04:00Dear Paul,
Thanks for the comments. It is more cl...Dear Paul,<br /><br />Thanks for the comments. It is more clear to me now. I will try to test my code considering your comments.<br /><br />Regarding my code and its error when I include user cut callbacks, as I said I put the benders, feasibility and optimality, cuts in the user cut callback. May I ask you in your opinions, is there any chance from theory point of view that putting benders cuts inside the user cut callback may cause this error? Or the code itself has some problem? <br /><br />The reason to ask this is that when I look at the benders sample file of Cplex (Ilobendersatsp.cpp), I can't notice any difference in the way of coding to deal with user cut compared to the lazy constraints. The only difference is that at the beginning of the macro function of the user cut the following command line is added:<br /><br />if ( !isAfterCutLoop() )<br /> return;<br /> <br />The rest of the code is exactly the same when it comes to deal with the lay constraints. <br /><br />Best regards,<br />Alain Alainnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-54727801463173200992021-04-06T09:07:58.241-04:002021-04-06T09:07:58.241-04:00Alain,
I'm glad you find the blog useful. Reg...Alain,<br /><br />I'm glad you find the blog useful. Regarding your first question, let me start by saying that I would use both callbacks with different cuts in each (Benders cuts in the lazy constraint callback, bound-tightening cuts in the user cut callback) if I had a recipe for generating bound tightening cuts. Typically, though, I do not know any special way to tighten bounds. CPLEX is good at generating the common types of cuts without my help.<br /><br />I once did an experiment in which I added the Benders cuts in a lazy constraint callback, queued them within my code, and then added them again in a user cut callback. The reasoning was that the lazy constraints were not being used to tighten node bounds. I thought that by adding duplicates of them as user cuts, progress on the bound would be faster. It was not. That's just one experiment, so I can't rule out the value of doing that in some other case, but I'm not optimistic about it in general.<br /><br />On to your second question. Any time you add a user cut, CPLEX will (hopefully) update the solution to the LP relaxation at that node and will then invoke the callback again at the same node, in case you want to add more cuts. This goes on until the user cut callback exits without adding a cut, which tells CPLEX it is time to move on. So you should check your code to make sure that it is working with the updated LP solution after the cut is added for the first time. Assuming it is, you might check whether the updated LP solution looks to CPLEX to be satisfying the new cut to within tolerances but looks to your code not to be satisfying the new cut (due to a difference in tolerances). For instance, if you test for something being zero or being nonnegative, you might need to modify the test to being within epsilon of zero or being greater or equal to -epsilon.<br />Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-21912604907937231692021-04-06T06:45:43.171-04:002021-04-06T06:45:43.171-04:00Dear Prof. Rubin,
I would like to first thank you...Dear Prof. Rubin,<br /><br />I would like to first thank your for creating this blog and taking the time to answer the comments. I personally learn a lot going through your blog and also reading the comments.<br /><br />I have read at one of your comments, that you mentioned you use only Lazy constraints, not user cut, when it comes to implement benders decomposition. May I ask you is there a particular reason?<br /><br />My second question which is related to the first question is about using User cut within the the framework of benders decomposition. Within my code, I basically use exactly the same code for the user cut that I use for the lazy constraint. But, it seems that the same cut will be added infinitely at a node when the user cut is called. I mean sounds it is fallen at a loop. But, when I ignore the user cut and I only use the lazy constraint, the code works perfectly and it finds the optimal solution. I would like to know what could be the reason? <br /><br />Best,<br />Alain Alainnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-56379505280405025762021-04-05T11:46:27.441-04:002021-04-05T11:46:27.441-04:00Thanks for sharing this! I notice your mods have &...Thanks for sharing this! I notice your mods have "_dark" in them. Are they for a dark theme?Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-54805859515230136932021-04-04T20:53:55.849-04:002021-04-04T20:53:55.849-04:00Appreciate this!
I found this after being frustra...Appreciate this!<br /><br />I found this after being frustrated with the default rainbow parens colors, so I was able to update them to be more colorblind friendly.<br /><br />Something I toyed with previously myself was to have the bracket pair blink with:<br /><br />.ace_bracket {<br /> margin: 0 !important;<br /> border: 0 !important;<br /> background-color: rgba(127, 127, 127, 0.8);<br /> animation: blinker 1s ease infinite;<br />}<br /><br />@keyframes blinker {<br /> 50% {<br /> opacity: 0;<br /> }<br />}<br /><br />in my custom theme.<br /><br />I extended what you've done here by playing with other attributes for the ace_paren_color_# style, specifically the font-size attribute. Though I found if you do so, adjusting the letter-spacing and vertical-align is also necessary or the cursor can get out of alignment with the text after too many nested parens.<br /><br />Here are my colorblind friendly rainbow parens for in case anyone else is interested (colors come from: https://www.nature.com/articles/nmeth.1618),<br /><br />.editor_dark .ace_paren_color_0 {<br /> color: #FFFFFF;<br />}<br /><br />.editor_dark .ace_paren_color_1 {<br /> color: #E69F00;<br /> font-size: 90%;<br /> letter-spacing: +0.1em;<br /> vertical-align: -1%;<br />}<br /><br />.editor_dark .ace_paren_color_2 {<br /> color: #56B4E9;<br /> font-size: 80%;<br /> letter-spacing: +0.12em;<br /> vertical-align: -2%;<br />}<br /><br />.editor_dark .ace_paren_color_3 {<br /> color: #009E73;<br /> font-size: 110%;<br /> letter-spacing: -0.06em;<br /> vertical-align: top;<br />}<br /><br />.editor_dark .ace_paren_color_4 {<br /> color: #F0E442;<br /> font-size: 95%;<br /> letter-spacing: +0.05em;<br /> vertical-align: -6%;<br />}<br /><br />.editor_dark .ace_paren_color_5 {<br /> color: #0072B2;<br /> font-size: 90%;<br /> letter-spacing: +0.1em;<br /> vertical-align: -5%;<br />}<br /><br />.editor_dark .ace_paren_color_6 {<br /> color: #D55E00;<br /> font-size: 80%;<br /> letter-spacing: +0.12em;<br /> vertical-align: -4.5%;<br />}<br />elmstedthttps://www.blogger.com/profile/07361232779186464927noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-67259447426679143672021-04-01T11:10:36.081-04:002021-04-01T11:10:36.081-04:00Hi Mahya,
In what follows, anything relating to C...Hi Mahya,<br /><br />In what follows, anything relating to CPLEX functions will be answered in terms of the Java API, but something similar will apply to other APIs.<br /><br />"What is global and local lazy/user cut constraints?" Global cuts are cuts that apply to the entire search tree. Local cuts only apply to the node at which they are added and its descendants (i.e., the subtree rooted at the node where they are added).<br /><br />"When we add a lazy constraint at a node using add() does it count as a global lazy constraint and it will kept and called at the next nodes of the tree?" With legacy callbacks, add() adds a global constraint/cut and addLocal() adds a local constraint/cut. With generic callbacks, addUserCut() has a boolean argument to signal whether the user cut is local or global; separate methods (rejectCandidate() and rejectCandidateLocal()) are used to add global/local lazy constraints.<br /><br />"You mention that in order to avoid keep calling the same cuts, we should exit the callback without attempting to add anything. May I ask you what is the command line in CPLEX for doing this?" There is no command. Your callback is executing code in a function. Just return from the function without adding anything. In most APIs, this can be done either by calling a return statement or just by reaching the end of the function code.<br /><br />"Is there a way to print out the cut added as lazy or user cut at a node?" This is a bit language-specific, but yes. In Java, you are adding an instance of class IloRange. You can just pass it as an argument to a print statement. CPLEX automatically overrides the default toString() method to produce a human-readable string. To make the constraint more readable, be sure to assign meaningful name strings to your variables, either in the variable constructors or using the IloNumVar.setName() method (or its equivalent in your favorite API).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-37503832062540850822021-04-01T07:05:22.929-04:002021-04-01T07:05:22.929-04:00Dear Prof. Rubin,
I am a beginner at both using L...Dear Prof. Rubin,<br /><br />I am a beginner at both using Lazy constraints and benders decomposition. So please pardon me if my questions sounds quite simple.<br />May I ask you:<br />-What is global and local lazy/user cut constraints?<br />- When we add a lazy constraint at a node using add() does it count as a global lazy constraint and it will kept and called at the next nodes of the tree?<br />- you mention that in order to avoid keep calling the same cuts, we should exit the callback without attempting to add anything. May I ask you what is the command line in CPLEX for doing this? <br />-is there a way to print out the cut added as lazy or user cut at a node?<br /><br />Best regards,<br />Mahyanoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-9219025455167480312021-02-20T09:59:45.406-05:002021-02-20T09:59:45.406-05:00Sorry, if there is a proof that BGFS converges on ...Sorry, if there is a proof that BGFS converges on (convex) pw-linear functions, I don't know of it. That does not mean much, as I have not messed with nonlinear programming in the last 30 years or so. If you have not already done so, you might ask on OR Stack Exchange or Mathematics Stack Exchange.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-31113026048178497032021-02-20T06:35:19.042-05:002021-02-20T06:35:19.042-05:00Thanks, I know want finite differences are and how...Thanks, I know want finite differences are and how to get an exact subgradient for LR() if necessary ;)<br /><br />I rephrase my question: Are there any proofs that bfgs converges to an optimal solution on piecewise linear functions/lagrangian relaxations? If so my life would become easier...<br />Good and free bfgs implementations are much easier to find than libraries for convex non-smmooth optimization (afaik Antonio Frangioni's ndosolver is more or less the only one). Of course you can always write a quick&dirty subgradient method that may or may not work well enough...<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-21673692298223880882021-02-19T11:55:20.541-05:002021-02-19T11:55:20.541-05:00However, these can slow down fiber WiFi broadband ...However, these can slow down fiber WiFi broadband and the computer generally, and in a number of cases may be using your allocated bandwidth to either download or upload additional data. <a href="https://ip-192-168-0-1.com/" rel="nofollow">192.168.2.1</a><br /><br /><br /><br />soccerjanice74https://www.blogger.com/profile/07943932485778679539noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-68992873032841270922021-02-19T09:21:00.800-05:002021-02-19T09:21:00.800-05:00It seems your comment got cut off, unfortunately. ...It seems your comment got cut off, unfortunately. Anyway, I was just exploring, seeing which methods seemed to work (or not). With BFGS and the optim() function, I chose the option to approximate gradients via finite difference. If you think about using gradient descent with $f(x)=|x|$ in one dimension, finite difference estimates of the gradient will be +/-1 when you are away from $x=0$, but near $x=0$ the slope estimates (assuming they are computed over a small interval centered at the current point) will be between -1 and +1, and nearly zero as you get close to $x=0$.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-73129976077537778412021-02-19T03:08:11.096-05:002021-02-19T03:08:11.096-05:00Can you elaborate on how to use BFGS for piecewise...Can you elaborate on how to use BFGS for piecewise linear functions? I always got the impression that BFGS requires a sufficiently smooth objective function. With piecewise linear I don't see how a termination rule that relies on "norm of the gradient sufficiently small" can work reliably on a piecewise linear function where even at the optimal solution we might get a subgradient != 0.<br /><br />Or are you using BFGS in a heuristic fashion?<br />Of course one could use BFGS als Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-47520627970031298792021-01-31T17:36:23.066-05:002021-01-31T17:36:23.066-05:00Thanks for pointing that out. It's fixed now.Thanks for pointing that out. It's fixed now.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-22424583056002302232021-01-31T17:24:40.276-05:002021-01-31T17:24:40.276-05:00Small typo in (2). Pretty sure that the index unde...Small typo in (2). Pretty sure that the index under the 3rd summation should be i, not n. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-92213811030731600572021-01-29T12:54:18.067-05:002021-01-29T12:54:18.067-05:00I agree. It's always comforting to be able to ...I agree. It's always comforting to be able to confirm results from new code, either by matching to known results on test problems or by matching to results from other models/algorithms where the test problem true solutions are not known. That was especially true for me in this case, because there was some index conversion involved in going from problem data to my visualization of the network to the algs4 inputs and outputs. Index conversions are a fertile ground for bugs.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-65528646069991850212021-01-29T12:50:02.064-05:002021-01-29T12:50:02.064-05:00As the setup for this model is a little bit more i...As the setup for this model is a little bit more involved for the network model -- so more chances for bugs, the MIP model is still a good debugging tool and confidence builder.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-60963397844543941992021-01-29T09:06:13.955-05:002021-01-29T09:06:13.955-05:00I'm inclined to agree, although painful experi...I'm inclined to agree, although painful experience has made me cautious about using the words "always" or "never" in the context of MIPs.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.com