tag:blogger.com,1999:blog-8781383461061929571.comments2024-08-14T10:49:03.690-04:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1827125tag:blogger.com,1999:blog-8781383461061929571.post-55672289923649066192024-07-29T18:56:14.538-04:002024-07-29T18:56:14.538-04:00Thanks. I do not know of such a parameter (and to ...Thanks. I do not know of such a parameter (and to be honest I have never tried setting a starting solution for CPO). According to the documentation (https://www.ibm.com/docs/en/icos/20.1.0?topic=c-starting-point-in-cp-optimizer), you can only set a starting solution when using a restart or multipoint search strategy. There are several parameters (fail limit, growth factor, dynamic probing) that apply to restart searches. They would presumably apply to how CPO moves from the initial start to a feasible, although maybe not exactly what you have in mind.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-43150624166127518572024-07-29T16:14:08.419-04:002024-07-29T16:14:08.419-04:00Dear Professor Paul
Very useful post. Is there so...Dear Professor Paul<br /><br />Very useful post. Is there something equivalent to MIP.Limits.RepairTries in the case of using CP Optimizer?<br /><br />Thank you.<br />Francisco Y.Administradorhttps://www.blogger.com/profile/15005443739729392034noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-68283377342832933072024-05-03T11:47:53.451-04:002024-05-03T11:47:53.451-04:00I can't rule out what you are saying, but the ...I can't rule out what you are saying, but the playground part may be key here. If we're talking about a Pareto distribution for batting ability, then the vast majority of the kids on the playground would fit into the category I was in, which the late Tommy Lasorda accurately characterized as "couldn't hit water falling out of a boat". My recollection, however, is that the bulk of the kids (at least in gym class) were so-so, not good enough to make the school team but also not flailing away like me. So while I agree with the 20% (ish) quota for serious jocks, I'm skeptical that the density function of the other 80% would look like a Pareto density.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3745170903094691632024-05-03T08:01:38.647-04:002024-05-03T08:01:38.647-04:00Apologies in advance for any naivety and tardiness...Apologies in advance for any naivety and tardiness (asynchronous communication is quirky). I wonder if both distributions may be in play in the batting average example. I imagine that the population of batters come from the 20% group of a Pareto distribution of the all candidates (those of us in the 80% on the playground knew who the 20% were). The skill set of that 20% is perhaps a Gaussian distribution albeit one that is actively being culled with by the baseball farm system (tiered leagues) with lower performers being culled out of the system and higher performers being promoted (lather, rinse, repeat). All the populations will have been manipulated to some extent - even the baseball players vs non-baseball players, it is dependent on unarticulated assumptions.Steve G.noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-15942819630219221332024-03-12T12:09:44.910-04:002024-03-12T12:09:44.910-04:00Glad it worked out for you.Glad it worked out for you.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-91594695605756650712024-03-12T11:57:57.235-04:002024-03-12T11:57:57.235-04:00This is really useful! I had a problem where both ...This is really useful! I had a problem where both my menu and task bars were frozen and I couldn't switch between windows and this solved itAnonymousnoreply@blogger.comtag: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.com