tag:blogger.com,1999:blog-8781383461061929571.comments2017-06-19T08:22:03.521-04:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1418125tag:blogger.com,1999:blog-8781383461061929571.post-4498725988084242812017-06-19T07:32:01.611-04:002017-06-19T07:32:01.611-04:00This comment has been removed by a blog administrator.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-52727876786060466822017-06-02T14:24:15.228-04:002017-06-02T14:24:15.228-04:00Jess: First, just to be clear, let me emphasize th...Jess: First, just to be clear, let me emphasize that heuristic solutions generated by CPLEX _are_ checked against lazy constraints; it's only heuristic solutions generated by you in a heuristic callback that are not checked (at least, as of the last I heard -- this might be subject to change).<br /><br />If I understand the question correctly, this is what I would do. Since it's Benders, I assume you have a lazy constraint callback (LCC). If I generated a candidate solution in a heuristic callback (HC), before adding it (using setSolution in the Java API) I would first run it through the cut generator in the LCC. If the cut generator returned a feasibility cut, I would queue that somewhere in program memory; the next time the LCC was called, it would check the queue and add any cuts it found there (emptying the queue in the process). If the cut generator agreed that the integer part of the heuristic solution was okay but generated an optimality cut because the value of the surrogate real variable (the SP contribution to the overall objective) was too charitable, I would substitute the value of that variable that the cut generator came up with and inject that solution (but not queue the optimality cut). This applies at all nodes, including the root.<br /><br />One thing people tend to forget is that there is nothing stopping various callbacks from communicating with each other through program global memory.<br />Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-16731995611993067222017-06-02T03:14:54.884-04:002017-06-02T03:14:54.884-04:00Thanks for this helpful post. You mentioned that h...Thanks for this helpful post. You mentioned that heuristic solutions won't be checked over the pool of Lazy constraints since they are expected to be feasible. However, in Benders implementation, the cuts added using a heuristic solution can define a lower bound for artificial variables, and so the branch and bound. In other words, by a heuristic solution for integer MP (master problem), we might not have a solution for real variables of SP (subproblem). To give stronger lower bound in the root node, we may solve SP for the given heuristic solution, generate and add related cuts to MP. If it is not done by lazy call back, how can we add them to MP in the root node? <br /><br />Thanks.Jess Whitehttp://www.blogger.com/profile/03010114755480388342noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-23368327480038380802017-06-01T02:27:29.274-04:002017-06-01T02:27:29.274-04:00it has solved the problem, thank you so much!it has solved the problem, thank you so much!Azat Ibrakovhttp://www.blogger.com/profile/17242073897985315722noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-10151964743373735322017-05-31T14:43:28.580-04:002017-05-31T14:43:28.580-04:00Thanks for pointing that chapter out, Samik! I rea...Thanks for pointing that chapter out, Samik! I really liked the XPRESS book back when I used it (I shudder to think how long ago), and it's good to know that it's still out there.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-26511964732741724202017-05-31T05:19:17.421-04:002017-05-31T05:19:17.421-04:00Another reference I have used in the past is Ch 3 ...Another reference I have used in the past is Ch 3 of the XPRESS LP/MIP book, available at: http://www.maths.ed.ac.uk/hall/Xpress/FICO_Docs/Xpress-booka4.pdfSamik Raychaudhurihttp://www.blogger.com/profile/08575567213510734030noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-50866280283182346942017-05-30T10:27:23.709-04:002017-05-30T10:27:23.709-04:00Nice. Thanks.Nice. Thanks.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-55800585824476971192017-05-30T10:19:12.973-04:002017-05-30T10:19:12.973-04:00Table 1 here:
http://cepac.cheme.cmu.edu/pasilectu...Table 1 here:<br />http://cepac.cheme.cmu.edu/pasilectures/grossmann/RamanRellogicCACE.pdfRob Pratthttp://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77609405024131389902017-05-30T10:03:49.987-04:002017-05-30T10:03:49.987-04:00Rob: I agree. In fact, I was thinking that there w...Rob: I agree. In fact, I was thinking that there was probably a "cheat sheet" somewhere that showed conversion of basic logical expressions (conjunction, disjunction, negation, implication) into constraints on binary variables. You wouldn't happen to have a link to one, would you?Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-84992930616813724652017-05-30T09:58:28.769-04:002017-05-30T09:58:28.769-04:00Another useful exercise is to derive this constrai...Another useful exercise is to derive this constraint by rewriting the logical implication \(x \wedge y \rightarrow z\) in conjunctive normal form.Rob Pratthttp://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-66590452551362832472017-05-27T15:13:10.588-04:002017-05-27T15:13:10.588-04:00You're welcome.You're welcome.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-80791807937636457772017-05-27T15:08:37.148-04:002017-05-27T15:08:37.148-04:00Sir,thank you so much.
linux mint 18.1Sir,thank you so much.<br />linux mint 18.1Ahttp://www.blogger.com/profile/14848641934145565367noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-20979554724148364752017-05-21T13:29:17.489-04:002017-05-21T13:29:17.489-04:00It doesn't make sense to me. A single SOS2 pro...It doesn't make sense to me. A single SOS2 produces a piecewise linear function of a single variable. Your expression maps $\{0,1\}^N\rightarrow\Re$.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88038154112805177312017-05-21T11:52:25.807-04:002017-05-21T11:52:25.807-04:00b_i=a_i*v_i; a_i's are real constants and v_i&...b_i=a_i*v_i; a_i's are real constants and v_i's are binary decision variables. In addition 0<=(SUM(b_i))^C1 <=1.0. I am thinking to piece-wise linearize the expression z=(SUM(b_i))^C1 using SOS2 and substitute z in the original expression. I don't if that makes sense.Dejene Boruhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-41521011511879398752017-05-21T10:27:44.046-04:002017-05-21T10:27:44.046-04:00Sorry, no; I don't work with Python.Sorry, no; I don't work with Python.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-37770739187674000762017-05-21T10:26:37.195-04:002017-05-21T10:26:37.195-04:00If b_i is the product of a binary variable and a r...If b_i is the product of a binary variable and a real variable, no, you cannot linearize it. If it is the product of a binary variable and a real constant, then you can linearize for small N (by tabulating all possible values of the sum, which is impractical unless N is fairly small).Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-69622870180334232052017-05-21T08:10:37.573-04:002017-05-21T08:10:37.573-04:00Sorry b_i's are the product of binary and real...Sorry b_i's are the product of binary and real number. Dejene Boruhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-22607898166460319412017-05-21T07:36:27.874-04:002017-05-21T07:36:27.874-04:00Hi Paul,
Is it possible to piece wise linearize th...Hi Paul,<br />Is it possible to piece wise linearize the following expression <br /><br />(SUM(b_i))^C1+C2*N; i=1,2,..N, b_i's are real numbers <br /><br />Thanks,<br /><br /><br />Dejene Boruhttp://www.blogger.com/profile/07141426235880358655noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-12532783998061638002017-05-21T04:25:54.912-04:002017-05-21T04:25:54.912-04:00Thank you so much for the prompt replies, could yo...Thank you so much for the prompt replies, could you recommend any python module (that provides an interface to a solver) which could allow handling of SOS2 ?Unknownhttp://www.blogger.com/profile/00914610718786575201noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-520028242700216912017-05-18T17:33:44.235-04:002017-05-18T17:33:44.235-04:00Just found out that there is no mailing list for C...Just found out that there is no mailing list for CyLP. The issue tracker on the project's GitHub page serves that role.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-33752856395207013562017-05-18T17:08:25.835-04:002017-05-18T17:08:25.835-04:00I don't use either CBC or CyLP, so I'm afr...I don't use either CBC or CyLP, so I'm afraid I cannot point you directly to a tutorial or example code. There is a mailing list for CBC, though, which you can access from a link in the bottom of their project page (https://projects.coin-or.org/Cbc). The archives don't have a search feature, but Google can help you out. For instance, you could try the search query "sos2 site:https://list.coin-or.org/pipermail/cbc/".Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-53391028650887344362017-05-18T15:57:11.254-04:002017-05-18T15:57:11.254-04:00Hi,
Is there any possible link or tutorial that hi...Hi,<br />Is there any possible link or tutorial that highlights how to use SOS2 with CBC or CyLP?joy1993http://www.blogger.com/profile/17486082254935918727noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-35144531101549563982017-05-11T09:22:56.405-04:002017-05-11T09:22:56.405-04:00The closest you can come is an approximation. Look...The closest you can come is an approximation. Look up "McCormick linearization".Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-79360157548912969992017-05-10T22:39:46.889-04:002017-05-10T22:39:46.889-04:00Hi Paul,
If I have a two continuous variables X*...Hi Paul, <br /><br />If I have a two continuous variables X*y=z and I want to linearize them IS there any easy way to do that similar to using big M as if I have a binary and a continuous variable ? <br /><br />Appreciate your help in advance e Talalhttp://www.blogger.com/profile/00244954498298322009noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-26178143606432047782017-05-03T15:16:25.908-04:002017-05-03T15:16:25.908-04:00It's been quite a few years since I used Xpres...It's been quite a few years since I used Xpress, and I've forgotten what callbacks they support. If they have something equivalent to CPLEX's lazy constraint callback, then using it does not stop the solver when an integer-feasible candidate is found, it just pauses the solver.<br /><br />Do you need to do this as opposed to solving to optimality, adding a constraint and repeating (the "traditional" way)? No, it's your choice. I think the traditional method is sometimes more efficient. (I suspect that occurs when the master problem is "easy" to solve and the subproblem is "hard".) My subjective, anecdotal, unsupported by rigorous analysis opinion is that the callback ("one tree") method is _usually_ more efficient, and so I default to using it.<br /><br />You mentioned a "big M" method (in the subproblem?). If you are struggling to improve performance, you might consider using "combinatorial Benders cuts" in lieu of the big M method. Again, sometimes it's faster, sometimes not, depending on how tight your values for M are.<br /><br />Lastly, you're very welcome. Thanks for the kind words. :-)Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.com