tag:blogger.com,1999:blog-8781383461061929571.comments2019-11-18T09:11:05.169-05:00OR in an OB WorldPaul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger1690125tag:blogger.com,1999:blog-8781383461061929571.post-2957167503220959692019-11-18T01:03:03.341-05:002019-11-18T01:03:03.341-05:00Thanks a lot for the help, Prof. Rubin. Your expla...Thanks a lot for the help, Prof. Rubin. Your explanation helped to fix the issue. A related question: is there a way to check if the desired decomposition has really been followed? For example, in case I use FULL decomposition strategy, can I see how CPLEX chose to decompose a MIP? I saw the content of ".ann" file, but not sure whether the "values" entries represent the subproblem numbers. <br />Also, as we now have the option of providing an annotation file to CPLEX as an input, how can one generate the xml structure for a large scale instance?<br />Any pointer?<br /><br />Regards<br />Jyotirmoy.Jyotirmoy Dalalhttps://www.blogger.com/profile/15052065796456541043noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-79582318986648515582019-11-14T13:37:46.026-05:002019-11-14T13:37:46.026-05:00I'm pretty sure your Java code does not do wha...I'm pretty sure your Java code does not do what you think it does. What happens if you get rid of the innermost loop (looping over x3), move the outermost loop (looping over s) to innermost, and inside the "for (int s=0, ...)" loop change the middle argument of setAnnotations to x3[s]?Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-83613511847063473802019-11-13T23:49:36.019-05:002019-11-13T23:49:36.019-05:00Dear Prof. Rubin,
I am trying to learn working wi...Dear Prof. Rubin,<br /><br />I am trying to learn working with this new way of Benders implementation through Annotation. I tried to follow your code example. Can you please illustrate any change needed in code if my subproblem is separable over scenarios (indexed by 's')? I tried to annotate my second stage 4-indexed flow variable x[i][j][t][s] as follows:<br /><br />code snippet 1:<br /> x = new IloNumVar[num_source][num_destination][num_period][num_scenario]; <br />for(int i = 0; i<num_source; i++)<br />for (int j = 0; j < num_destination; j++)<br />for (int t = 0; t < num_period; t++) <br />for (int s = 0; s < num_scenario; s++) <br /> x[i][j][t][s] = cplex.numVar(0.0, 1, "X("+i+")("+j+")("+t+")("+s+")");<br /><br />code snippet 2:<br /> for(int s = 0; s <num_scenario; s++) {<br /> for (IloNumVar[][][] x1 : x) {<br /> for (IloNumVar[][] x2 : x1) {<br /> for (IloNumVar x3[] : x2) {<br /> for (IloNumVar x4 : x3) {<br /> wholeModel.setAnnotation(benders, x4, (s+1));<br /> }}<br /> }<br /> }<br /><br />However cplex threw an error, stating that the decomposition is wrong. Am I doing a syntax error somewhere? I want to set x[i][j][t][0] for subproblem 1, x[i][j][t][1] for subproblem 2 etc until num_scenario.<br /><br />Thanks in advance for your time.<br /><br />Jyotirmoy Dalal<br />Unknownhttps://www.blogger.com/profile/15052065796456541043noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3186724490326061152019-10-17T11:43:55.043-04:002019-10-17T11:43:55.043-04:00Sorry, I have only a vague idea what your notation...Sorry, I have only a vague idea what your notation means, and no idea why you are multiplying B by r. I suggest you check how you are formulating your Benders cuts (in particular, the r*B part). If that provides no answers, you might try Gurobi's help forum. (I assume they have one.)Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-61199779938096764762019-10-17T11:39:27.526-04:002019-10-17T11:39:27.526-04:00You create a binary indicator variable for each po...You create a binary indicator variable for each possible starting point of a sequence. If the variable is 1, you'll have a sequence (say, ABC) start there. If the indicator is zero, the solver is free to do something else at that point (such as run A by itself). To force at least a certain number of sequences, you sum the indicators and constrain that sum to be at least the required number of sequences.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-49591218165733598992019-10-17T10:58:11.295-04:002019-10-17T10:58:11.295-04:00Thank you Paul.
If I understand correctly, these ...Thank you Paul.<br /><br />If I understand correctly, these constraints will force Promotion A to always be followed by Promotion B and Promotion C? <br />I would like to have it such that Promotion A can run standalone. But there will be at least n number of the sequence (Promo A, Promo B, Promo C). Let me know if I am missing something.<br /><br />Really appreciate your help.Unknownhttps://www.blogger.com/profile/11244275979307915085noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-65449926762968580192019-10-17T06:17:54.485-04:002019-10-17T06:17:54.485-04:00Dear Prof. Rubin,
I am working on a Benders Decomp...Dear Prof. Rubin,<br />I am working on a Benders Decomposition with Gurobi, and I would like to add feasiblity cuts to master problem. I use farkas dual to generate feasiblity cuts, which is similar in CPLEX.<br /><br /><br />The primal sub-problem is minimziation. I added " 0 >= r * (B-Dy)" to the master<br />probelm, where "r" is obtained by fakas dual. But I cannot get the right solution.<br />When I added " 0 >= (-1) * r * (B-Dy)", then the solution is right. Do you konw the reason for this?<br /><br />Sometimes, r * (B-Dy) is possible positvie or negative, it's uncertain. Unknownhttps://www.blogger.com/profile/02247939467927398055noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-90345818362703329752019-10-15T15:41:47.021-04:002019-10-15T15:41:47.021-04:00My impression is the proportions are estimated fro...My impression is the proportions are estimated from sample data, so I don't know if they are initially rationals or not. As provided, they are floats, so we do not have integer numerators and denominators. We could truncate the decimals and get rational approximations, of course.<br /><br />For now, I think I'll stick with what we have and keep my fingers crossed. :-)Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89446772186667827302019-10-15T15:02:37.856-04:002019-10-15T15:02:37.856-04:00So if I understand correctly, these "partly p...So if I understand correctly, these "partly proportions" are in principle known as rationals, but only represented as floating point numbers?<br /><br />That would mean, you have numerator and denominator as integers which could be exactly given to Mathematica, Maple or similar.<br /><br />I don't know whether this is a viable approach, but at least, one could check some previous results for correctness.Thomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-12262248735801748172019-10-15T14:03:32.596-04:002019-10-15T14:03:32.596-04:00Yes, you can use an indicator to signal that a seq...Yes, you can use an indicator to signal that a sequence of binary variables must all be 1. See "Modeling an On/Off Span" (https://orinanobworld.blogspot.com/2014/04/modeling-onoff-span.html).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-31763148646171271912019-10-15T13:27:12.188-04:002019-10-15T13:27:12.188-04:00The research project involves traffic flows in a r...The research project involves traffic flows in a road network. The floating point data is partly proportions of traffic exiting a given node on various arcs, but there are also a lot of rows with just zeros and ones (cover constraints, more or less). We don't need exact basis vectors for the null space, but we do need the correct number of basis vectors, and "exact" determination of singular v. nonsingular matrices.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89522752521078969542019-10-15T12:45:17.331-04:002019-10-15T12:45:17.331-04:00Paul,
can you elaborate a little on the research ...Paul,<br /><br />can you elaborate a little on the research project that you are working on? Maybe, there is some other approach. Where does your floating point data come from? Do you need exact solutions, or are "almost" correct floating point solutions also ok?Thomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-28462847468342317862019-10-15T11:53:23.416-04:002019-10-15T11:53:23.416-04:00Thomas,
I appreciate the suggestions. I probably ...Thomas,<br /><br />I appreciate the suggestions. I probably could rationalize the matrices without too much loss of validity, but offhand I don't know if that would increase or decrease the frequency of numerical issues (dubious rank calculations). Solving a MIP to get a null space vector, besides requiring an exact MIP solver I don't have, would unfortunately blow up the run times for the program past what could be tolerated. If necessary, I may pass the null space calculations to R, since the QR and SVD methods in R seem a bit more reliable than those in EJML or Apache Commons (although I might be wrong about that).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-31788106300564470692019-10-15T11:39:47.933-04:002019-10-15T11:39:47.933-04:00In Mathematica, this should be possible using Rati...In Mathematica, this should be possible using Rationalize https://reference.wolfram.com/language/ref/Rationalize.html . In the past, I used Maple, I never really used Mathematica, so I have no further details about this.<br /><br />When I wrote my own exact-arithmetic MIP solver (in C++, using GMP), I wrote my own code to deal with floating point numbers in lp-files. I read them digit by digit and did some trivial arithmetic. It can read arbitrary long floating point numbers or fractions. So if you can somehow represent your problem as MIP, it would be easy to solve it in exact arithmetic.Thomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89544555746527331752019-10-15T10:35:16.826-04:002019-10-15T10:35:16.826-04:00Hi Paul,
Thank you for your post!
My model is a ...Hi Paul,<br /><br />Thank you for your post!<br /><br />My model is a scheduling problem where I am trying to output a weekly promotion calendar which maximizes profit subject to constraints. Each promotion type is represented by a binary variable where 1 indicates that promotion will be run and 0 if not. <br /><br />I have constraints which require promotions to be run in a particular order (eg: Promotion A needs to be followed by Promotion B greater than n number of times) and have represented this using the general formulation:<br /><br />Introducing indicator variables z(n), which indicate A(n) followed by B(n) where z = 1 => A*B = 1 (i.e. both A and B = 1)<br /><br /><br />L < 0 < U<br />z <= U*A<br />z >= L*A<br />z <= B - L*(1-A)<br />z >= B - U*(1-A)<br /><br />sum(z(n)) >= number of promotions required<br /><br />Is there a general way to linearize conditions of length i, where;<br /><br />z = 1 => A*B*C...i = 1<br />Unknownhttps://www.blogger.com/profile/11244275979307915085noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6485677770277253432019-10-11T09:27:35.007-04:002019-10-11T09:27:35.007-04:00Thanks for the suggestion, Thomas. I could try thi...Thanks for the suggestion, Thomas. I could try this with one test case, but unfortunately the problem needs to be solved thousands of times (with different matrices) during the solution of a MIP model. I don't know if it is possible (and practical) to link to either of them from Java. Also, the matrix has double precision (non-integer) coefficients. Does Mathematica do "exact" arithmetic on doubles?Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-48063701046472350092019-10-10T23:35:21.914-04:002019-10-10T23:35:21.914-04:00I would try to use some software that works in exa...I would try to use some software that works in exact arithmetic like Mathematica or Maple. If they are able to solve the problem in finite time, I guess, you can trust the results.Thomas Opferhttps://www.blogger.com/profile/01379302702721609320noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-36607329673175846822019-10-10T05:32:17.680-04:002019-10-10T05:32:17.680-04:00Thank for the article. I'm facing this problem...Thank for the article. I'm facing this problem in my program. To complex. Hazzzqlenamhttps://www.blogger.com/profile/08920961629458345921noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-19630918371835618692019-10-01T23:39:06.243-04:002019-10-01T23:39:06.243-04:00Thank you so much.I think I find the problem due t...Thank you so much.I think I find the problem due to your help.Koalagogohttps://www.blogger.com/profile/01068808383821136402noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3558140144962745232019-09-30T11:20:35.717-04:002019-09-30T11:20:35.717-04:00At each node, CPLEX will call the user cut callbac...At each node, CPLEX will call the user cut callback repeatedly until the callback returns without adding a cut. When it sees that no cut was added, it moves on. As far as I know, if the callback returns the same cut it added on the previous call, CPLEX will call it again. So the way to stop further calls at a node is to exit the callback without attempting to add anything.<br /><br />I don't know of any way to force CPLEX to limit the number of times the callback is called at a given node. It should be possible to do that within your code. There's a method you can call to get the ID number of the node at which the call is occurring. So you can count the number of times a given ID number has shown up, and when it exceeds your limit you can return with no new cut and CPLEX will move on.<br /><br />To your last point, I believe that CPLEX will recognize that a cut has repeated and not add a duplicate copy. I'm not sure why it doesn't stop in that case. I'm also surprised that your callback would keep generating the same cut. I think CPLEX updates the node solution between calls to the callback, so the next call should be with a node solution that satisfies the most recent cut. You might want to check your cut generating code.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77201254560542378802019-09-30T11:12:36.204-04:002019-09-30T11:12:36.204-04:00Thanks so much for your sharing, it really helps m...Thanks so much for your sharing, it really helps me a lot.when I tried to use Java to call CPLEX and use callback functions to solve a VRP problem with branch-and-cut ,some problems emerged.I took out the subtour elimination constraint from the original problem, and used it as usercut and lazyconstraint .When I only used it as a lazyconstraint,the algorithm worked out very well, but when I used it as both usercut and lazyconstraint Java program couldn't stop, it kept calling usercutCallback at node0 and wouldn't make branch. I really don't know what the problem is.<br /> Does cplex loop calling usercutCallback at each non-integer node until no usercut are violated, and then make branch? If so, can I set the maximum number of calls at each node? Maybe just one time is ok.<br /> Another problem is why it kept generating the same cut. I think when cut A has been already added,even if I generate A again in the next loop, it should have been satisfied so that no usercut is violated and the loop should be stopped.Unknownhttps://www.blogger.com/profile/01068808383821136402noreply@blogger.comtag: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.com