tag:blogger.com,1999:blog-8781383461061929571.comments2019-07-15T09:19:48.459-04:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1663125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-42582243709369059462019-03-03T03:08:07.239-05:002019-03-03T03:08:07.239-05:00Hello Paul
you are explaining the problem very goo...Hello Paul<br />you are explaining the problem very good. This helps me a lot so thank you.<br /><br />But how can I handle the same Problem but a Little Change:<br />Z=x^k(y) for k is a real numberAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-24374839404420965442019-02-23T15:52:33.487-05:002019-02-23T15:52:33.487-05:00I don't know about "work great", but...I don't know about "work great", but I'll show results in the next post that suggest (but do not definitively prove) that it might "work well enough".<br /><br />I'm not sure about the best way to present a Pareto frontier myself. I did some pairwise plots of criteria, but plotting all $\binom{M}{2}$ pairwise plots might cause catatonia in the decision makers. I haven't tried this myself, but one possibility is to present selected pairwise plots ("selected" meaning comparisons in which the DM expresses an interest), and link them so that mousing over a point in one plot highlights the same solution in the other plots. It might or might not be effective as a decision aid, and in any case it's pretty decent eye candy. :-)Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-27118157642173809252019-02-23T15:41:58.355-05:002019-02-23T15:41:58.355-05:00I've often wondered about this algorithm to ge...I've often wondered about this algorithm to generate the Pareto front. Seems too trivial to work great, but it is too easy to try.<br /><br />On the other hand, does it really make sense to present a Pareto front if M is larger than maybe 5?pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6395735025228436772019-02-22T19:54:45.324-05:002019-02-22T19:54:45.324-05:00Nejat,
You did not indicate whether you are using...Nejat,<br /><br />You did not indicate whether you are using "solve" or "populate" to generate solutions. (The solution pool would be used with either one.) I believe that CPLEX works differently depending on which you use. To get all the solutions, I would use "populate". Even then, several parameters set limits that can cause CPLEX to stop before all optimal solutions are found. To be sure to find them all, you can keep calling populate until it comes back with an empty node log (nothing more to do). This assumes that you set the pool size limit high enough to hold all the optimal solutions.<br /><br />I did not understand what you meant about "triangle constraints", and I really do not know whether using a user cut callback at the beginning but then turning it off after X minutes would be helpful. (By the way, the second phase would still be branch-and-cut, since CPLEX will generate cuts even if you do not.) Setting the objective value as a constraint is unlikely to help, and done the wrong way can slow the solver. One possibility to help with memory is to set parameters that let CPLEX swap parts of the node tree out to disk. Another, if you have many constraints, is to make some of the constraints lazy constraints. (This may slow progress on the bound, but may help conserve RAM.) Finally, note that using parallel threads will massively increase RAM consumption, so you can always try cutting back on the number of threads used (again, at the cost of speed).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-57584018546850407962019-02-22T12:32:15.580-05:002019-02-22T12:32:15.580-05:00Hi Dr. Rubin,
Thank you very much for this post an...Hi Dr. Rubin,<br />Thank you very much for this post and your blog. First of all, I am quite newbie in OR. I have a partitioning problem where I need to find all optimal solutions. By following your post and the IBM manual (I set 'SolnPoolAGap' to 0.5), I was able to find many optimal solutions. Based on this, I would like to ask 2 questions:<br />1) Can we say for sure that we get all optimal solutions?<br />2) I ran into some memory problem for some instances, please note that the memory (RAM) I use is quite large: 256 gb. So, I am thinking an alternative way which consumes less memory when enumerating all optimal solutions. I have two ideas (but, I do not know if it is feasible):<br /> *) Using cutting plane approach. Hence, we do not add all triangle constraints, it might help us gain memory usage. However, I am not sure how to implement this. If I first generate user cuts within X minutes (Branch&Cut), and then I solve the same instance with generated tight user cuts (Branch&Bound), this would be a good idea?<br /> *) I can (efficiently) solve the problem for one optimal solution, and get the objective function value. Then, use this objective function value as constraint, and solve the same instance again but for all optimal solution.<br /><br />I am open to all your suggestions. Thanks in advance.<br /><br />NejatAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-78254288350532028702019-02-10T21:50:06.235-05:002019-02-10T21:50:06.235-05:00Thanks. This problem is belong to Bilinear problem...Thanks. This problem is belong to Bilinear problem. Maybe i should refer to more papers about that. ORAndYouhttps://www.blogger.com/profile/04268693961187233051noreply@blogger.com