tag:blogger.com,1999:blog-8781383461061929571.comments2022-11-21T10:32:10.720-05:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1806125tag:blogger.com,1999:blog-8781383461061929571.post-1270396578964606922022-10-11T09:25:38.544-04:002022-10-11T09:25:38.544-04:00It is a bit subtle. The first time it bit me, it t...It is a bit subtle. The first time it bit me, it took me a while to figure out what was going on.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25199583135683367272022-10-11T01:26:54.901-04:002022-10-11T01:26:54.901-04:00This is interesting. I never knew about this and h...This is interesting. I never knew about this and have had faced similar errors before. Usually gets solved when you make some random changes and just thought CPLEX is buggy. ravi_radanhttps://www.blogger.com/profile/09339336586742034282noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88315591584248714072022-09-28T03:52:49.499-04:002022-09-28T03:52:49.499-04:00I implemented this...unfortunately, it is not perf...I implemented this...unfortunately, it is not performing well...worse than the previous one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25977225894329316792022-09-23T18:19:30.947-04:002022-09-23T18:19:30.947-04:00Yes actually it was the CPLEX annotation file give...Yes actually it was the CPLEX annotation file given by cplex.writeBendersAnnotation ommited probably for some not accepted characters. It was supposed to look something like this CPLEXAnnotation name='cpxBendersPartition' type='long' default='0'<br /> object type='1'<br /> anno name='y_0_0_0' index='0' value='1'<br /> anno name='y_0_0_1' index='1' value='2'<br /> anno name='y_0_0_2' index='2' value='3' etc.<br /><br />Ok sure thank you so much for your swift replies. They have been very helpful. <br />Best regards.IBZhttps://www.blogger.com/profile/14106328583331182373noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-58112900435054524782022-09-23T15:03:31.091-04:002022-09-23T15:03:31.091-04:00There is a large gap in your comment above, which ...There is a large gap in your comment above, which makes me wonder if perhaps something was inadvertently omitted. In any case, a detailed question like this is better suited to a Q&A forum. I would suggest either the IBM Data Science Community forum or Operations Research Stack Exchange. The links to those are in the right margin of the blog (under "Places to Ask Questions").Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-12858677479510251852022-09-23T14:40:54.827-04:002022-09-23T14:40:54.827-04:00Thank you Professor for your reply. Indeed my rhs ...Thank you Professor for your reply. Indeed my rhs HashMap didn't have the correct constraints (I should probably stop coding after work hours). Thank you for precious guidance.<br /><br />However professor, I am having difficulties understanding an issue. <br /><br />For some problems, both STANDARD MIP and MANUALbenders give the same result, however when I use CPLEX automatic benders regardless of the strategy (FULL, WORKERS, or USERS),<br />CPLEX raise this warning BENDERS WARNING: no sub-problems left, and the problems become infeasible. <br /><br />The annotation file below shows that only some variables have the same value.<br /><br />CPLEXAnnotation name='cpxBendersPartition' type='long' default='0'<br />object type='1'<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />I am wondering my CPLEX annotate the same variables which are continuous and should be in the same sub-problem, to different sub-problems, or am I missing something? <br />Even when use the strategy USER and annotate the variables like this cplex.setAnnotation(benders, y, 1) for every variable I have the same issue. <br /><br />Thank you for your time and help. It is greatly appreciated.<br />Best regards. IBZhttps://www.blogger.com/profile/14106328583331182373noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-31168686267868358802022-09-22T11:16:33.729-04:002022-09-22T11:16:33.729-04:00All three sets will have the same score (2) *for t...All three sets will have the same score (2) *for that user*. If any of those sets are compatible with other unsatisfied users, they will have scores for those users as well. For each set compatible with the current user, you look at that set's score for other users, compute a min or average, and select the set whose min or average is smallest.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6269190487379834192022-09-22T04:53:48.362-04:002022-09-22T04:53:48.362-04:00I think for all the compatible remaining resource ...I think for all the compatible remaining resource set, the score will be the same. 'if set S is compatible with user U and U has three options left (including S)', then all three sets will have same score, right? Would you please elaborate on this?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-71485276981399676682022-09-22T02:07:42.550-04:002022-09-22T02:07:42.550-04:00But the score for all compatible resource sets wil...But the score for all compatible resource sets will be equal for a given user. Previously, for the user that is to be served now, we used to find the set that has minimum number of conflicts. Since we are not doing as you mentioned in your reply, how come we have different scores for the compliant/remaining resource sets of the user to be served?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-38115552865053661722022-09-21T17:23:33.150-04:002022-09-21T17:23:33.150-04:00Did you take into account the order of the returne...Did you take into account the order of the returned array entries? The reason for the first argument to dualFarkas() (an initially empty array of constraints) is that CPLEX does not return the dual values (second argument) in the same order that you specified the constraints in the original model. So you need to use the first argument to figure out which dual value goes with which constraint.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-27181088943809282052022-09-21T15:24:45.536-04:002022-09-21T15:24:45.536-04:00Thank you professor for your prompt reply. Actuall...Thank you professor for your prompt reply. Actually, I had an error in the number of constraints N. After getting it right, indeed both the constraints array and the coefficient double array were filled.<br /><br />However, after adding the feasibility cut (the sumproduct of the coefficients and the rhs of the constraints is = 263529.0 :( ) making the master problem infeasible, although the original problem was solved using usual MIP model.<br /><br />What could have caused the issue in the sub-problem ? Thank you in advance for your time and help.<br /><br />Best regards.<br /><br /><br /><br />IBZhttps://www.blogger.com/profile/14106328583331182373noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-38819748526215665192022-09-21T14:04:00.444-04:002022-09-21T14:04:00.444-04:00I'm not sure. You might try keeping track, for...I'm not sure. You might try keeping track, for each pair of unsatisfied user and compatible remaining resource set, how many options the user has other than that set. For instance, if set S is compatible with user U and U has three options left (including S), the "score" for that pair would be 2 (U has two options left if S goes away). After picking the next user to serve, scan that user's remaining options and choose the one for which either the minimum or average score (excluding the score for the chosen user) is largest, indicating that consuming that resource would do less damage to other users' prospects ... maybe.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-30494619072181892782022-09-21T13:51:20.817-04:002022-09-21T13:51:20.817-04:00Sorry, I'm having trouble understanding your q...Sorry, I'm having trouble understanding your question. Yes, the constraints[] array is initially filled with nulls. The integer N must be the number of constraints in the subproblem. After you pass constraints[] as an argument to IloCplex.dualFarkas() (along with a double array of the same dimension), it should be filled with the constraints from the subproblem. Is it not?Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-58076973321268028202022-09-21T13:23:07.347-04:002022-09-21T13:23:07.347-04:00Dear Professor Paul,
Thank you so much for this ...Dear Professor Paul, <br /><br />Thank you so much for this impressive blog, going through it I learned a lot. I am trying to implemented benders manually going through your code (Manuelbenders). My sub-problem becomes is feasibility problem since no costs are associated with the continuous var, <br />hence an objective function of constant 0 and only constrains to be satisfied given the fixed integer variables from the master problem. <br /><br />After solving the sub-problem , in the first iteration the sub is infeasible I tried to get the Farkas certificate, hence I did as you suggested:<br /> <br />IloConstraint[] constraints = new IloConstraint[N]; however constraints is filled with null and obviously java.lang.NullPointerException is raised. The log shows following information:<br /><br />Iteration log . . .<br />Iteration: 1 Dual objective = 0.000000<br />CPXPARAM_Preprocessing_Presolve 0<br />CPXPARAM_LPMethod 2<br />CPLEX status: Infeasible<br />is Primal feasible: false <br />is Dual feasible: true <br /><br />Is it because my dual is feasible ? If yes how to resolve this issue? <br />Thank you so much in advance. IBZhttps://www.blogger.com/profile/14106328583331182373noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-17629760759121571422022-09-21T12:24:46.113-04:002022-09-21T12:24:46.113-04:00I implemented this conflict heuristic method, i.e....I implemented this conflict heuristic method, i.e., user first and selecting the best resource set. Unfortunately, this is performing little worse than the another solution my fellow friend has. Is there a way to improve this performance of this solution?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-56369351366810312482022-07-21T10:30:09.587-04:002022-07-21T10:30:09.587-04:00This depends on the solver you are using. As descr...This depends on the solver you are using. As described in the post, with CPLEX (and perhaps some other solvers) you can use a callback to stop the search if it finds a solution that you know is optimal. (I'm assuming here that you somehow know that 50 is the optimal objective value, as opposed to knowing that it will be no more than 50.) <br /><br />Another possibility is that your solver may have a parameter (UpperObjStop in CPLEX for max problems) that tells it to stop as soon as it gets a solution with objective value at or above some threshold. If you know your optimal objective value will be at most 50 (but possibly less), you could try setting a cutoff of 49, or 49.5, or whatever you think is reasonable.<br /><br />Neither of those fixes the best bound and gap. The only ways I know to reduce the best bound are to come up with a tighter formulation (always desirable, but easier said than done) or tell the solver to use best bound search (always selecting the node with the highest bound). The latter is definitely *not* guaranteed to help, and it might actually hinder progress on the gap. The gap depends on both the upper bound and the lower bound (best known solution), and forcing the solver to concentrate on the upper bound may result in it taking longer to improve the lower bound.<br /><br />Tightening the formulation is your best bet, *if* you can do it.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77485133348286549222022-07-21T05:18:18.405-04:002022-07-21T05:18:18.405-04:00Hi Paul, nice post.
For some reason my best bound...Hi Paul, nice post.<br /><br />For some reason my best bound is extremely large, and even though I know that my optimal solution's max is 50, the bestbound is around 5000, making the optimality gap to be around 99%. So the solver never stops, as the number of active nodes gets bigger and bigger. In this case, how would you handle the fact that I know that my solution should be under 50? <br /><br />Thanks a lot.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3610731616281321402022-05-30T17:35:13.382-04:002022-05-30T17:35:13.382-04:00The optimal solution to the MIP model will pack th...The optimal solution to the MIP model will pack the maximum possible number of users, so there is no way a heuristic solution can do better.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-56606250805889163032022-05-30T14:06:51.612-04:002022-05-30T14:06:51.612-04:00No, by performing better I meant packing more user...No, by performing better I meant packing more users.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-60104163817832752462022-05-30T10:44:30.319-04:002022-05-30T10:44:30.319-04:00I assume by "perform better" you mean ge...I assume by "perform better" you mean get the same answer faster or get a better (but not necessarily optimal) answer in the same amount of time. This of course depends on the MIP solver used. Commercial solvers have the advantage of being coded (and continually improved) by professionals, and they usually contain heuristics of their own. Also, commercial solvers typically use parallel threading by default. Some heuristics are more amenable to parallel threads than others, and for amateurs it can be tricky to code parallel threads safely. There's also the setup time for a MIP model to consider. So, bottom line, sometimes heuristics get good solutions sooner than MIP solvers and sometimes not. There is no general rule that "heuristic X is always faster than a MIP solver" or "heuristic Y is always slower than a MIP solver".Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-1045011928109931842022-05-30T07:19:14.141-04:002022-05-30T07:19:14.141-04:00Can any heuristic perform better than the MIP solu...Can any heuristic perform better than the MIP solution?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-79814318711614953082022-05-26T22:31:31.465-04:002022-05-26T22:31:31.465-04:00You are correct that there is no guarantee all res...You are correct that there is no guarantee all resources can be used (or all users can be satisfied). The key is in how the updates are done at each step. You want to continue allocating resource sets until no legal allocations are left. In the update loop, I delete not just the resource set and user that were just paired, but any unmatched users for whom no allocation is possible and any resource set that cannot be allocated to any remaining user. So as long as a resource set remains, there must also be at least one user to whom it can be allocated.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-83868746572981485052022-05-26T19:40:23.081-04:002022-05-26T19:40:23.081-04:00Thanks a lot. The ConflictHeuristic is iterative a...Thanks a lot. The ConflictHeuristic is iterative and the condition you have is 'while (!users.isEmpty())', i.e., iterate until no resource sets are left. But there is no guarantee that you have 100% resource utilisation or 100% user packing depending on number of resource sets and users and their demands. Then it seems to be a never ending loop! <br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-46433267370722904652022-05-25T20:03:51.115-04:002022-05-25T20:03:51.115-04:00Java uses class inheritance. The ConflictHeuristic...Java uses class inheritance. The ConflictHeuristic and UserHeuristic classes extend (are descended from) the parent Heuristic class, which contains code common to both heuristics ... including the map declarations and, in the constructor, the code to initialize them.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-41556037884945092252022-05-25T19:49:28.095-04:002022-05-25T19:49:28.095-04:00Interesting Problem. I am not a java user, thus tr...Interesting Problem. I am not a java user, thus trying to transform this script into python/Matlab. Specially interested in ConflictHeuristic solution. In this script, it seems that the Maps such as users, resources, and conflicts are not defined anywhere. For example, you have (i) for (int u : users.get(set)), (ii) double x = resources.get(u).size() and (iii)for (Entry> e : conflicts.entrySet())Anonymousnoreply@blogger.com