tag:blogger.com,1999:blog-8781383461061929571.comments2023-12-01T18:24:59.883-05:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1821125tag:blogger.com,1999:blog-8781383461061929571.post-77549538577598481192023-11-29T21:35:56.283-05:002023-11-29T21:35:56.283-05:00"Almost anything (within reason) you want to ..."Almost anything (within reason) you want to do with data can be done in an R application ... if you can just find the correct libraries and functions. "<br /><br />This is absolutely true. But I feel like a lot of professionals don't get this.Shibaprasadhttps://ordinaryanalysis.substack.com/noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-11216595795691698112023-11-09T05:40:03.213-05:002023-11-09T05:40:03.213-05:00Thanks! I have worked out the problems with your h...Thanks! I have worked out the problems with your hints!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-90912590267886896872023-11-07T14:38:14.202-05:002023-11-07T14:38:14.202-05:00I suggest taking this to Operations Research Stack...I suggest taking this to Operations Research Stack Exchange. There's a link to it in the right margin.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-4415403946696859022023-11-07T12:54:40.314-05:002023-11-07T12:54:40.314-05:00Thanks Paul, I was working on this. In the origina...Thanks Paul, I was working on this. In the original post, I have x_1a to mean a binary variable x for item 1 to be assigned with box a. Also y_1A to mean the binary variable y for item 1 to be assigned onto flight A. For governance purpose, I have to introduce another binary variable p. e.g. p_aA to mean the policy for putting all items with group a onto flight A. where the policy is defined and given, so I can set p_aA = 1 to tell group_a is assigned to flight A, also p_aB=0 as the policy to forbid group_a onto flight B (possibly p_cA = 1 for group_c can be given to flight A also). Then my constraints and objectives can have the product of three binary (C_1 * x_1a * y_1A * p_aA + C_1 * x_1a * y_1C * p_aA + ... <= 800). C_1 * x_1a * y_1C * p_aA, this one is also funny as item 1 is assigned to group_a and a is valid for flight A but item 1 is assigned to flight C. Can you please help on some suggestions? Thanks in advance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-46392142763749626732023-11-04T10:42:38.323-04:002023-11-04T10:42:38.323-04:00You could minimize the range (maximum usage minus ...You could minimize the range (maximum usage minus minimum usage). To do that, introduce two new variables (call them x and y) with the constraints that every ration is greater than or equal to x and less than or equal to y, then set the objective to minimize y - x.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-20938007843353600682023-11-03T17:09:28.493-04:002023-11-03T17:09:28.493-04:00Thanks a lot! I will work on the constaints with y...Thanks a lot! I will work on the constaints with your suggestions. Meanwhile my objective functions are to balance the carrier loads in terms of percentage usage. <br />e.g. plane A will carry the total loads as W_A with capacity 800, then the usage is (W_A/800). Plane B carry W_B as the loads with the capacity 1000, then the usage is (W_B/1000), Similarly, Plane C usage is (W_C/600). My aim is to make (W_A/800) = (W_B/1000) = (W_C/600) as close as possible. My thinking is to use the ratio for each of them but that is not linear, or use absolute value for the two each other differences. Is there any simpler methods to define the objective functions? Thanks in advance from Tim.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-30146785251699868362023-11-02T14:59:47.830-04:002023-11-02T14:59:47.830-04:00Introduce a variable $z\in [0,1]$ for the product ...Introduce a variable $z\in [0,1]$ for the product of $x$ and $y.$ (I'll let you add the subscripts.) add the constraints $z \le x,$, $z \le y$ and $z \ge x + y - 1.$ If either $x$ or $y$ is 0, $z$ has to be 0 thanks to the first two constraints. If they are both 1, $z$ has to be 1 thanks to the third constraint. You can declare $z$ as either a binary or a continuous variable; it works the same either way. Which one leads to faster solution is an empirical question.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-44101770185010734612023-11-02T13:03:40.896-04:002023-11-02T13:03:40.896-04:00Hi Paul,
Thanks for the post and can I ask a ques...Hi Paul,<br /><br />Thanks for the post and can I ask a question?<br />I have many items with weight C and I want to put them into several boxes a, b, and c. then put the boxes onto different plane A or B. and the plane itself has carrier capacity.<br />If I have two binary variable as x and y. <br />when x_(1,a)=1 means to allocate item 1 to box a,<br />y_(1,A) means to allocate item 1 to flight A.<br />Only both x and y are 1, we will put the item into box and onto the plan. (We have to put the items into boxes before shipping with plane) <br />x will be either 0 or 1, so is y (0 or 1) as the decision binary variable.<br />C as the constants, e.g. weight of the item<br />One of the constraints is like,<br /><br />C_1 * x_1a * y_1A + C_2 * x_2a * y_2A + .... + C_n * y_na * y_nA <= 800 (here 800 the airplane weight capacity)<br />Similarly,<br />C_1 * x_1a * y_1B + C_2 * x_2a * y_2B + .... + C_n * y_na * y_nB <= 1000<br />How to linearise this one for xy? <br /><br />Thanks in advance,<br />TimAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-81892025713348103162023-09-10T09:08:08.196-04:002023-09-10T09:08:08.196-04:00I'm glad it helped.I'm glad it helped.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-91836420127637195512023-09-10T07:39:27.861-04:002023-09-10T07:39:27.861-04:00Thank you, this worked hereThank you, this worked hereAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-34400001088218043752023-04-04T03:18:01.096-04:002023-04-04T03:18:01.096-04:00I agree. If the lazy constraints in the cut table ...I agree. If the lazy constraints in the cut table were fully considered, CPLEX should never propose repeated master incumbent. By repeated I mean one that has already been checked by the subproblem(s).<br /><br />However, as suggested by the CPLEX documentation, the lazy constraints that are fed to CPLEX by the reject candidate method are not guaranteed to be used by CPLEX.<br /><br />I'm using Julia, and the package works with CPLEX by calling the C API. In the documentation on the routine `CPXcallbackrejectcandidate` [1], a warning says:<br /><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 />I know you are using Java. I guess the Java counterpart to <br /> `CPXcallbackrejectcandidate` is the `rejectCandidate` method that belongs to the `IloCplex.Callback.Context` class. In the description of the argument of the method [2], it says:<br /><br />"A set of constraints that cut off the candidate solution. This set can potentially be empty. This argument can also be `null`. If not `null` and not empty, then CPLEX can use these constraints to cut off further candidate solutions that CPLEX finds. (There is no guarantee that CPLEX does so, though.)"<br /><br />I'm afraid that your speculation on the "cut table" might be true. In fact, I did encounter repeated master incumbent when experiementing with a very simple MILP instance (2 binary variables and 1 continuous variable). Presolves and reductions are explicitly turned off. And the number of thread is set to 1. So I'm very suspicious about how the user generated lazy constraints are handled by CPLEX.<br /><br />[1] https://www.ibm.com/docs/en/icos/12.10.0?topic=c-cpxxcallbackrejectcandidate-cpxcallbackrejectcandidate<br /><br />[2] https://www.ibm.com/docs/api/v1/content/SSSA5P_12.10.0/ilog.odms.cplex.help/refjavacplex/html/ilog/cplex/IloCplex.Callback.Context.html#rejectCandidate(ilog.concert.IloRange[])Luyu Wangnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-13823895874474454802023-04-03T11:27:51.653-04:002023-04-03T11:27:51.653-04:00To the second point, I thought you meant that the ...To the second point, I thought you meant that the same cut was added more than once *within one call* to the callback. Generating the same cut within different subproblems, or during parallel-threaded subproblem solves, is certainly possible, but I would not worry about it. CPLEX should recognize that you are passing a cut it already knows and simply ignore the duplicates. Note that the cuts should not duplicate cuts that were generated earlier (prior to the most recent master problem iteration). If you are solving a Benders subproblem, it is because CPLEX identified what it thought was a possible master incumbent. If the subproblem finds an already known cut violated by the candidate solution, CPLEX should not have considered it a candidate (unless one of the factors, such as making the cut local or allowing the cut to expire) caused the original cut not to be considered.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-31774286863233407042023-04-02T23:15:48.439-04:002023-04-02T23:15:48.439-04:00Dear Prof. Rubin,
Thank you for the detailed com...Dear Prof. Rubin, <br /><br />Thank you for the detailed comment. <br /><br />I made up the 'empty cut table' point. It is viable only in the sense that it could be inferred from the premise. I did not check whether it is really achievable with either the legacy or the generic callback APIs. My apology for the confusion. I think your elaboration on the 'cut management' parameter in the legacy callback makes perfect sense.<br /><br />On the second point. I'm actually imagining solving a stochastic programming problem with multiple scenario subproblems by Benders. My vague guess is that some of the subproblems may, occasionally, return identical cuts on specific master problem solutions. Nevertheless, such occasions could be checked within the callback to prevent multiple identical cuts being fed back to CPLEX. So I agree that it should be acccounted as a coding issue.Luyu Wangnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-19625538941897459222023-04-02T12:11:56.582-04:002023-04-02T12:11:56.582-04:00If a cut repeats, why would the cut table be empty...If a cut repeats, why would the cut table be empty the second time the cut was generated? Presumably it would have been added to the table the first time ... with one qualification. When using legacy callbacks, there is an optional "cut management" parameter that can be used to tell CPLEX whether to retain the cut no matter what or whether the solver is free to drop the cut if it appears "ineffective" after a while. I don't recall if that parameter is available in generic callbacks. So with the right setting a lazy constraint might be added to the table but then disappear later before being rediscovered. I forgot to mention that above. Other than expiration, I don't see how the cut table could be empty the second time the cut is generated. Regarding the second point, if the callback identifies identical cuts, I would consider that a coding issue. In the post, I tacitly assume that the callback will not identify the same constraint multiple times *within the same invocation*. As for the premise that all cuts in the table will be tested, I would like to believe that, but I'm not sure it's true. The callback documentation says that if you add lazy constraints "... then CPLEX can use these constraints to cut off further candidate solutions that CPLEX finds. (There is no guarantee that CPLEX does so, though.)"Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-21149974743669826132023-04-02T05:42:47.826-04:002023-04-02T05:42:47.826-04:00Dear Prof. Rubin,
First of all, many thanks to yo...Dear Prof. Rubin,<br /><br />First of all, many thanks to your blog post series on callback-based Benders implementations in CPLEX. I really learned a lot.<br /><br />Regarding the third explanation (cut table), I think it is only possible under two cases, at least for the lazy constraints, with the premise that all cuts in the cut table will be tested:<br />1. when the cut table is empty;<br />2. when the callback identifies multiple cuts and some of them are identical.<br /><br />If the premise holds, then no integer-feasible solutions cut off by lazy constraints in the cut table should ever be proposed as a candidate. So a repeated cut indicates either an empty cut table, or a newly invoked callback returning repeated cuts.<br /><br />Do you think the above reasoning is correct?<br /><br />LuyuLuyu Wangnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-49748755699001523072023-03-04T09:48:56.768-05:002023-03-04T09:48:56.768-05:00Thanks for the kind words.Thanks for the kind words.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-16610691921545712182023-03-04T04:54:15.280-05:002023-03-04T04:54:15.280-05:00Greetings of the day, As a learner, I can readily ...Greetings of the day, As a learner, I can readily understand the idea: of "Reproducibility and Java Collections." It highlighted the importance of reproducible research in computational science and discussed the challenges of unintentional randomness in multithreaded code and Java collections. The post provides useful insights for researchers to avoid these tripwires and ensure the deterministic behavior of their programs, and it was clear and neat. I appreciate you for giving me the information!Vibinhttps://www.blogger.com/profile/08715691762579225907noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-41890361091602799442023-02-03T20:56:24.207-05:002023-02-03T20:56:24.207-05:00I don't know how to interpret "doesn'...I don't know how to interpret "doesn't respond same". I think you are correct about automatic Benders.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-58402296958970473282023-02-03T18:25:23.147-05:002023-02-03T18:25:23.147-05:00Dear Prof. Rubin,
AFAIK, automated benders put in...Dear Prof. Rubin, <br />AFAIK, automated benders put integer varaibles in MP and other in SP(s). However, when I tried to have same conditions using WORKER strategy, it doesn't respond same, and I wondered why. Any ideas? <br />Bests Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-64944310271587198872023-01-28T22:32:54.044-05:002023-01-28T22:32:54.044-05:00Sorry, but I don't believe there is any way to...Sorry, but I don't believe there is any way to get run time breakdowns for MP and SP, either on a per-call basis or even aggregate (total time in MP/SP over the duration of the run).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-32717178708303512092023-01-28T21:29:16.167-05:002023-01-28T21:29:16.167-05:00Dr. Rubin, many thanks for your usefull blog. Is t...Dr. Rubin, many thanks for your usefull blog. Is there any specific command in CPLEX to report the run time spent solving MP and SP at each itteration?(Lets say we don't use any callbacks, so MP should've been solved every itteration.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-36971580560785302982023-01-21T22:58:32.070-05:002023-01-21T22:58:32.070-05:00Annotations are not used with lazy constraint call...Annotations are not used with lazy constraint callbacks (or any other kind of callback). If you click the Benders link in the labels section (bottom right area of every post here) you will get a list of posts I've done involving Benders. Some of them describe the use of callbacks, and most have links to Java code.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-41212369087877865392023-01-21T19:53:23.943-05:002023-01-21T19:53:23.943-05:00Hello again Prof Rubin,
I'm confused about us...Hello again Prof Rubin, <br />I'm confused about using Lazy Constraint Callback (LCC) in CPLEX Benders Strategy. As far as I understand, I should add LCCs using LasyConstraintCallBack; however, I have no idea how should I annotate LCCs so CPLEX be able to consider them. Am I even in right direction? <br />Thanks for your time in advance. Valanoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-45366245582570294542023-01-21T13:54:19.485-05:002023-01-21T13:54:19.485-05:00I am not sure, but I suspect that when IBM added a...I am not sure, but I suspect that when IBM added annotations to CPLEX they added capabilities beyond what is used for Benders decomposition (or anything else at the moment). In other words, they put in "plumbing" for future possible uses. I'm not aware of any current use for long annotations of constraints or objective functions, nor any use whatsoever for the DoubleAnnotation class that they also added.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-87537779214345349852023-01-21T12:36:17.998-05:002023-01-21T12:36:17.998-05:00Dr. Rubin: Thanks a lot for help. I just forgot to...Dr. Rubin: Thanks a lot for help. I just forgot to ask one last question. In IBM documentation, its been mentioned that we can annotate all parts of model including constraints (First paragraph of: https://www.ibm.com/docs/en/cofz/12.10.0?topic=algorithm-annotating-model). I was wondering if you can explain a little bit about annotating constraints. <br />Anonymousnoreply@blogger.com