tag:blogger.com,1999:blog-8781383461061929571.comments2019-09-17T11:07:02.120-04:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1669125tag:blogger.com,1999:blog-8781383461061929571.post-33929313028456355592019-09-17T11:07:02.120-04:002019-09-17T11:07:02.120-04:00I suspect it's a bug in the way you initialize...I suspect it's a bug in the way you initialize your callback. Unfortunately, I can't say what that would be. The comment section of a blog is not conducive for debugging software.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77540990262907342362019-09-17T04:17:53.542-04:002019-09-17T04:17:53.542-04:00Professor Rubin,
First I used the original callbc...Professor Rubin,<br /><br />First I used the original callbcak version of the code for my problem and it works fine. Then, I also coded the geveric callback version. But it has some problems.<br /><br />For some reason the optimality cuts are not being added (master problem obj. function does not increase from zero).<br /><br />It starts with: "$$$ Thread up occurred (thread 0/8) with no subproblem in place."<br /><br />Then every time master problem is solved: "$$$ A candidate was supplied (thread 0/8) with a subproblem already in place." <br />The optimality cut is reported but seems not to be added. Master problem's obj func value stays at zero. This goes on for a few iterations.<br /><br />Finally it ends with:<br />$$$ Thread up occurred (thread 3/8) with no subproblem in place.<br />$$$ Thread up occurred (thread 2/8) with no subproblem in place.<br />$$$ Thread up occurred (thread 1/8) with no subproblem in place.<br />$$$ Thread up occurred (thread 7/8) with no subproblem in place.<br />$$$ Thread up occurred (thread 6/8) with no subproblem in place.<br />$$$ Thread up occurred (thread 5/8) with no subproblem in place.<br />$$$ Thread up occurred (thread 4/8) with no subproblem in place.<br /><br />And an error window is opened that says: "Java(TM) SE Binary Platform has stopped working"<br /><br />Do you have any suggestions as to what the problem could be?<br /><br />Thank you.Vedat Bayramhttps://www.blogger.com/profile/16762259980382204540noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-28261528694094709732019-09-09T10:50:38.645-04:002019-09-09T10:50:38.645-04:00A ratio of binary variables is not something that ...A ratio of binary variables is not something that occurs "naturally" in models, by which I mean that you are probably using the wrong approach to capture whatever you intend. There are three possibilities. If the ratio $z=x/y$ must exist, you need to fix $y$ at 1 and set $z=x$. The second is that $z=x$ when $y=1$ and $z$ is unrestricted when $y=0$, i.e. $y=1\implies z=x$. The third is that you are trying to say $z=x$ when $y=1$ and $z$ is restricted in some other way when $y=0$ (for instance, $z=0$ when $y=0$). So, assuming the first option is not correct, you should look at the constraint $y=1\implies z=x$ and then consider whether you need an additional constraint on $z$ when $y=0$.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-38616459290690192612019-09-09T08:08:28.676-04:002019-09-09T08:08:28.676-04:00Dear Paul,
Many thanks for your post.
I will li...Dear Paul,<br /><br />Many thanks for your post. <br /><br />I will like to ask if there's a way out for this situation. I have two binary variables dividing each other, in this form: x(i,j,k)/y(l,m), where i, j, k and l, m are the respective indices of x and y. I know that if y(l,m) = 0, then the result will be indeterminate, and the result will be x(i,j,k) if y(l,m) = 1. So this is my question: is there a way to linearize this division of binary variables, just as you explained for the multiplication case. Knowing fully well that I don't know the exact value of any of these variables (whether 0 or 1) before solving.<br /><br />Thank you Sir. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-8213828721582216372019-09-07T10:44:54.975-04:002019-09-07T10:44:54.975-04:00CPLEX can detect a potential incumbent solution vi...CPLEX can detect a potential incumbent solution via heuristics, even at nodes with fractional solutions. In both the the "legacy" and "generic" callback systems, lazy constraint callbacks are definitely triggered in those cases, and I would assume that would be true in automatic Benders as well. So I'm fairly sure Benders cuts can be added at nodes with fractional solutions. The only way I can think of to avoid that would be to turn off all heuristics.<br />Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-36344680418836914852019-09-07T07:16:54.106-04:002019-09-07T07:16:54.106-04:00Dear Prof. Rubin,
Could you please let me know if...Dear Prof. Rubin,<br /><br />Could you please let me know if Cplex' Automatic Benders adds Benders cuts only at integer nodes of the Branch&Bound tree, or also at fractional nodes?<br /><br />Is there a way to control the nodes (integer versus fractioanl) where to add Benders cuts?<br /><br />Regards,<br /><br />Sachinsachin Jayaswalhttps://www.blogger.com/profile/04657771560757276728noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88921185292220425242019-06-24T09:42:16.216-04:002019-06-24T09:42:16.216-04:00Vedat: No, that is not an option. You can, of cour...Vedat: No, that is not an option. You can, of course, still do your own Benders decomposition using a callback.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-90799227670410054152019-06-24T04:19:58.359-04:002019-06-24T04:19:58.359-04:00Dear Professor Paul,
Is it possible to use any of...Dear Professor Paul,<br /><br />Is it possible to use any of the new Benders framework options (annotated, workers, automatic), if lets say we are solving the subproblems by employing column generation?<br /><br />Thanks.Vedat Bayramhttps://www.blogger.com/profile/16762259980382204540noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-37855756551163528192019-06-20T10:15:51.651-04:002019-06-20T10:15:51.651-04:00I know what you mean about Xpress. CPLEX has a Pyt...I know what you mean about Xpress. CPLEX has a Python API (not as complete as the C/C++/Java APIs, I think, but enough for a lot of work). It currently has no API for R. There are third-party R packages that will let you compose and solve a model, but I don't think any of them support callbacks.<br /><br />R does have a bunch of ML packages (not that I've ever used them). I think the "typical" user doing statistics, ML or whatever will be fine in either R or Python, and I would find needing to code in both a bit confusing. ("Why didn't that work? Oh wait, that's R syntax, and I'm in Python now.")Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-41730760434045892132019-06-20T03:09:47.934-04:002019-06-20T03:09:47.934-04:00Thanks for the link, Paul. It's surprisingly f...Thanks for the link, Paul. It's surprisingly fair and objective. I feel more at home in Python, simply because I have been more exposed to it. Also, since I am closer to the ML community than to the statistics community, I feel like a lot of packages are in fact available in Python. Case in point: the company I work for has Xpress, which to date does not have an interface to R ASAIK.Richard Oberdieckhttps://www.blogger.com/profile/03386871665462162276noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-85953155506914190912019-05-29T13:50:16.353-04:002019-05-29T13:50:16.353-04:00Calling cplex.addLazyConstraint() (rather than jus...Calling cplex.addLazyConstraint() (rather than just addLazyConstraint()) means that you are trying to modify the model itself. Modifying the model while a solve is in progress is illegal and likely causes the crash. Each callback class has it's own add methods, which add the cuts/lazy constraints to the solver without modifying the original model. So if you want to add a lazy constraint from a user cut callback (and you have a lazy constraint callback already attached), you can just use the add() or addLocal() method in the user cut callback. You do not need to signal that it is a lazy constraint rather than a user cut.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55730686388697512922019-05-29T11:55:05.382-04:002019-05-29T11:55:05.382-04:00Hi Mr. Rubin. Thank you for this helpful blog, it ...Hi Mr. Rubin. Thank you for this helpful blog, it is a pleasure to have experts share their knowledge for the broad audience. You refer to the legality of adding lazy constraint from a user cut callback. However, when I call cplex.addlazyconstraint(...), cplex crashes. Do you have any recommendation on how to add a lazy constraint from a user cut callback? Thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-40881117240895194542019-05-20T09:00:36.890-04:002019-05-20T09:00:36.890-04:00Well, that's a bit unsettling at minimum. Give...Well, that's a bit unsettling at minimum. Given my experience with other M$ software in the past, though, I can't say I'm shocked. I guess it could be worse. A long, long time ago I was using a pseudorandom number generator ... can't recall in what language ... and someone published a report that it cycled. I tested, and sure enough it cycled (after 100 or so observations, I think).<br />Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-60582339347812432722019-05-20T04:39:06.451-04:002019-05-20T04:39:06.451-04:00Fun fact: the random number generator in .NET prod...Fun fact: the random number generator in .NET produces more odd numbers than even. So just relying on that might skew your simulation results:<br />https://github.com/dotnet/corefx/issues/23298Richard Oberdieckhttps://www.blogger.com/profile/03386871665462162276noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-23756300048420314562019-05-14T09:39:15.147-04:002019-05-14T09:39:15.147-04:00Thanks for the link. CPLEX also has a "determ...Thanks for the link. CPLEX also has a "deterministic parallel search mode" that can be set via a parameter (along with parameters for making various time limits deterministic). I don't think I've ever tried the "deterministic parallel search mode", mainly because my desire for consistency is usually dwarfed by my desire for speed. It would be interesting to know whether results from either CPLEX or Xpress were 100% reproducible with the right settings (assuming same problem inputs, same hardware etc.).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-53520848621645343612019-05-14T09:27:03.267-04:002019-05-14T09:27:03.267-04:00FICO Xpress MIP solver has some guarantees on the ...FICO Xpress MIP solver has some guarantees on the reproducibility of a solution path:<br /><br />https://community.fico.com/s/blog-post/a5Q8000000082YvEAI/fico1154Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-85429461614089448832019-04-30T13:34:05.138-04:002019-04-30T13:34:05.138-04:00Thanks for the reference! It's interesting, an...Thanks for the reference! It's interesting, and might prove helpful to an acquaintance who is working on a real(ish)-world unconstrained MOCO. Now I just have to find time to read it. :-)Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-70213396829109124032019-04-30T13:28:01.286-04:002019-04-30T13:28:01.286-04:00Thanks, Gert-Jaap. That discussion is interesting,...Thanks, Gert-Jaap. That discussion is interesting, and it suggests another possibility to me. Again, we start with a global variable storing the objective value of the best integer-feasible solution so far. I'll also assume that the objective function contains a single variable, say minimize z. (This is to reduce dual degeneracy caused by the trick I'm going to suggest.) Each time the the global objective value changes, set a boolean flag for each thread. Each time a lazy constraint callback, the callback checks the flag corresponding to its thread. If it sees the flag is set, it clears the flag and adds a lazy constraint of the form z <= latest incumbent value. That will not only prevent repetitive generation of cuts at a node that should be pruned, it may also allow faster pruning of other nodes.<br /><br />I thought I would also mention that the business about cloning in that discussion only applies to legacy callbacks. Generic callbacks are not cloned by CPLEX, which is one reason that they are more tempermental about thread safety.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-86700444001044405372019-04-30T11:06:25.226-04:002019-04-30T11:06:25.226-04:00Dear Professor,
Thanks a lot for your helpful blog...Dear Professor,<br />Thanks a lot for your helpful blogpost. It is a very clear introduction to the new setup of CPLEX callbacks. <br />I also liked the last comment you made, that different threads can find suboptimal feasible solutions, because of a lack of communication between the threads (which in my view is fine because this would also slow down the solving process). However, in some of the projects that I've done, this issue was present as well and consumed a lot of time. I've asked IBM and there is an easy way around this, if you don't care about deterministic results, which might be interesting: https://www.ibm.com/developerworks/community/forums/html/topic?id=e72f622a-b899-4e96-a789-254587a39c7d&ps=25<br /><br />Best,<br />Gert-JaapGert-Jaaphttps://www.blogger.com/profile/08452235302203809872noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-66593006679433078762019-04-30T05:35:43.804-04:002019-04-30T05:35:43.804-04:00Nice post. You might be interested in the work of ...Nice post. You might be interested in the work of Schulze, Klamroth, and Stiglmayr on unconstrained MOCO-problems. If you want a reprensentation of the Pareto front and can live with a set composed of only the extreme-supported solutions, you can have it in polynomial time. https://link.springer.com/article/10.1007/s10898-019-00745-6 Unknownhttps://www.blogger.com/profile/02239605959360493928noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-56659440997235475742019-03-12T23:20:59.458-04:002019-03-12T23:20:59.458-04:00You're welcome, Hugh. Please do let me know an...You're welcome, Hugh. Please do let me know any suggestions for changes.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-22674996710949867932019-03-12T20:44:38.908-04:002019-03-12T20:44:38.908-04:00Thanks Paul!
Thanks Paul!<br />Hugh Medalhttps://www.blogger.com/profile/03468597595207233576noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-54945029675191252842019-03-04T14:59:51.397-05:002019-03-04T14:59:51.397-05:00I'm guessing that the $R_{ik}$ are parameters,...I'm guessing that the $R_{ik}$ are parameters, not variables, and that what you mean by overall reliability (to be maximized) is the product of those $R_{ik}$ for which $x_{ik} = 1$. In other words, $Rel=\prod_{i,k:x_{ik}=1}R_{ik}$. You can write this as $Rel=\prod_{i,k}R_{ik}^{x_{ik}}$, which looks even less linear but is a step in the right direction. Now take logs: $\log Rel=\sum_{i,k}\left(\log R_{ik}\right)x_{ik}$. Maximizing $\log Rel$ will maximize $Rel$, and you have a linear objective function.<br />Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-45692424291511462482019-03-04T14:48:49.281-05:002019-03-04T14:48:49.281-05:00Dear Paul Sir,
Can you please help me?
I am new to...Dear Paul Sir,<br />Can you please help me?<br />I am new to the CPLEX. I want to assign N jobs on M machines so as to maximize overall reliability. I face difficulty in implementing multiplication equation.<br />Overall reliability is calculated by following equation:<br />Rel = ∏ R(i,k) <br />where i=(1 to N) and k=(1 to M)<br />and R(i,k) - it is reliability of task i on processor k<br /><br />I am using Rel as float objective function which I have to maximize and binary decision variable x(i,k) which is 1 if job i is assigned to machine k, otherwise 0.<br />I have some other constraints which take care that no two jobs will overlap on the same machine. I am comfortable in using them. But I am unable to do multiplication in the constraint as,<br />R(i,k) * x(i,k) >= Rel; //where i=(1 to N) and k=(1 to M)<br /><br />Also, another concern is that if x(i,k) = 0 then it should not make overall reliability as zero.<br /><br />Rel and R(i,k) are float in the range of 0 to 1. <br /><br />Please help me. Thank you and appreciate your work, dedication for this blog. <br />Unknownhttps://www.blogger.com/profile/02640734944568632776noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55915223590454082002019-03-03T10:56:49.677-05:002019-03-03T10:56:49.677-05:00If $x$ is binary, $x^k = x$. If $x$ is continuous ...If $x$ is binary, $x^k = x$. If $x$ is continuous (and, presumably, $y$ is binary), then you are dealing with a nonlinear inequality constraint, which will make your problem harder to solve. You can still use what I wrote above, but my $y$ is your $x^k$, my $x$ is your $y$, and the bounds $L$ and $U$ apply to $x^k$.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.com