tag:blogger.com,1999:blog-8781383461061929571.comments2017-05-21T13:29:17.489-04:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1406125tag: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.comtag:blogger.com,1999:blog-8781383461061929571.post-38021720943028023142017-05-03T15:07:21.596-04:002017-05-03T15:07:21.596-04:00I agree, assuming that the lower and upper bounds ...I agree, assuming that the lower and upper bounds on the stage 2 variables are independent of the stage 1 variables (which I assume is the case). When someone derives a dual solution to generate the cut, they need the dual variables for the primal variable bounds to get the constant term correct; but CPLEX takes care of that for you in the return value of the dualFarkas function.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88490974831965058122017-05-02T10:06:20.942-04:002017-05-02T10:06:20.942-04:00Hi Professor Rubin,
I'm applying benders deco...Hi Professor Rubin, <br />I'm applying benders decomposition in Xpress-Ive for a crew scheduling problem. I have lots of consecutive constraints hold binary and integer variables. Due to the structure of constraints;<br />1) I have always getting feasibility cut<br />2) I'm using bigm method to getray from dual sub problem. Ive tried using C++ but getray function didn't work for my case.<br />3) I'm trying to use call backs. <br />I wonder that with callback do I need to stop solving master problem for every integer feasible solution found and solve dual with the feasible one rather than waiting for optimal solution of master problem. <br />Thanks for this great blog, it's been so good for knowledge. <br /><br />Regardssedaaağhttp://www.blogger.com/profile/13093884063740789376noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-68246680763879407032017-05-01T07:25:44.965-04:002017-05-01T07:25:44.965-04:00I think it depends on the purpose whether one need...I think it depends on the purpose whether one needs the full dual ray. <br />My goal is not the proof of infeasibility, but to add Benders feasibility cuts to a two-stage stochastic MIP problem.<br />Here the infeasible problems stem from one original scenario problem with the first-stage variables fixed to values f.<br />When CPLEX mipopt indicates infeasibility for one of these and dualopt applied to the relaxed problem gives LP-infeasibility, too, dualfarkas yields dual weights to constraints (ray) and a violation (viol) of the weighted sum inequality with the best-feasible values of the remaining variables. <br />In my case I read an arbitrary model file, so for the construction of y'A I have to use getcolumn for the first-stage variables to compute their coefficients by the scalar product with the weights from the ray argument of dualfarkas. This results in a vector w of coefficients for the first-stage variables.<br />lhs = w'f gives the value in that point.<br />If I'm not wrong <br />w'x >= lhs+viol<br />yields a valid inequality.Ralf Gollmerhttps://www.uni-due.de/mathematik/agschultz/ralf.phpnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-73878506177830198522017-04-29T12:15:09.312-04:002017-04-29T12:15:09.312-04:00Sorry, the command line entry was truncated becaus...Sorry, the command line entry was truncated because I forgot to escape angle brackets. I'll try again.<br /><br />java -Djava.libraryath=<path to CPLEX binary> -cp <path to compiled jar>/BendersExample2.jar:<path to CPLEX jar> bendersexample/Demo<br />Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-74645617497103587682017-04-29T12:11:39.847-04:002017-04-29T12:11:39.847-04:00Hi,
Sorry, but I've never used IntelliJ. With...Hi,<br /><br />Sorry, but I've never used IntelliJ. With Java IDEs, there's typically a project or run setting that lets you specify the main class. Also, there may be an option to select the Demo class in the IDE and, either from a main menu or a context menu, ask IntelliJ to run that class.<br /><br />Not finding the JAR file initially is correct: the repository does not have one. It's source only. If you created the JAR file in IntelliJ, and if IntelliJ could not find the main method, that would explain why the JAR you created appeared not to have one.<br /><br />You might try the following from a terminal:<br /> java -Djava.library.path= -cp BendersExample2.jar: bendersexample2.Demo<br /><br />The first path leads to the directory containing the CPLEX binary files (which have extension .so on Linux; I'm not sure if that's the same on a Mac). The second path leads to the directory containing the JAR file you created, and the third leads to the directory containing cplex.jar.<br />Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-18927321344762441812017-04-28T20:13:02.367-04:002017-04-28T20:13:02.367-04:00Thanks for all the Benders posts. I learn a lot fr...Thanks for all the Benders posts. I learn a lot from you.<br /><br />I dont know whether it is my fault or not. But, because INTELLIJ IDEA (IDE) does not find MAIN METHOD (even if i properly show the DEMO.CLASS to the IDE to spot the method) i can not run your code via INTELLIJ IDEA.<br /><br />And, I try run it via MAC TERMINAL but i couldnt find the .jar file. So i created one, but it could not also spot the MAIN method via the .jar file. (even if i told where the method is)<br /><br />I know that your code has no flaws. Could you tell me what are the possibly reasons for the problem.<br /><br />Thanks. Sincerely.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-75887396636892295062017-04-19T18:14:39.102-04:002017-04-19T18:14:39.102-04:00https://orinanobworld.blogspot.com/2013/07/integer...https://orinanobworld.blogspot.com/2013/07/integer-variables-and-quadratic-terms.htmlPaul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-53606147325181035402017-04-19T18:10:44.911-04:002017-04-19T18:10:44.911-04:00I don't know what a "linear decision vari...I don't know what a "linear decision variable" is, but if you mean that $x$ and $y$ are both continuous, then you cannot linearize the expression.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-89216601840926626532017-04-18T10:07:04.557-04:002017-04-18T10:07:04.557-04:00Hi Paul,
If x is integer-valued and y is real-val...Hi Paul,<br /><br />If x is integer-valued and y is real-valued how can i deal with their product?<br /><br />ThanksAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-59913714155838672952017-04-17T13:09:03.703-04:002017-04-17T13:09:03.703-04:00to be exact,
i am solving a mathematical model:
...to be exact,<br />i am solving a mathematical model:<br /><br /><br />subject to<br />y[i][k][n] = x[i][k][n] + sum(x[i][j][n]*y[j][k][n])HChun Wonghttp://www.blogger.com/profile/13671839788803814665noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-43927272817837311362017-04-17T13:04:08.345-04:002017-04-17T13:04:08.345-04:00i have two linear decision variable
i would like t...i have two linear decision variable<br />i would like to know how to linearize<br />x[i][j][n] * y[j][k][n] Unknownhttp://www.blogger.com/profile/13671839788803814665noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-56181746614312615072017-04-11T13:16:37.246-04:002017-04-11T13:16:37.246-04:00Sorry, I have no clue what you are asking.Sorry, I have no clue what you are asking.Paul Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.com