tag:blogger.com,1999:blog-8781383461061929571.comments2018-12-28T17:56:18.253-05:00OR in an OB WorldPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger1634125tag:blogger.com,1999:blog-8781383461061929571.post-24728148975036571562018-12-16T14:36:40.293-05:002018-12-16T14:36:40.293-05:00That seems like a good idea on the surface, but I ...That seems like a good idea on the surface, but I just tried it, and for some reason it slowed down progress on the bound. Partly this was fewer nodes being investigated per minute (perhaps because the model gets bigger). Even at the same node count, though, the bound was weaker than without this. Beats me why.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-53492652761646438912018-12-16T14:14:44.231-05:002018-12-16T14:14:44.231-05:00You would maximize $b'x + \sum_{i=0}^N e^{W_i}...You would maximize $b'x + \sum_{i=0}^N e^{W_i} y_i$, which is linear in $x$ and $y$. Any integer linear programming solver that recognizes SOS2 constraints could be used.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-8671828338845244942018-12-15T20:02:20.315-05:002018-12-15T20:02:20.315-05:00Another option is to replace the inequality formul...Another option is to replace the inequality formulation of absolute value with the equality formulation: $p_i - p_j = d^+_{ij} - d^-_{ij}$, where $d^+$ and $d^-$ are nonnegative, and the objective is to minimize $\sum_{i < j} (f_{ij} + f_{ji}) (d^+_{ij} + d^-_{ij})$.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-22955879404753773992018-12-15T13:33:46.050-05:002018-12-15T13:33:46.050-05:00Hello Professor Rubin,
I am studying on probabili...Hello Professor Rubin, <br />I am studying on probabilistic chance constraints. My objective function is in the shape you mentioned here,<br /> <br />https://www.quora.com/How-can-I-solve-a-constrained-optimization-problem-where-the-objective-function-is-sum-of-a-linear-expression-and-an-exponential-of-linear-expression<br /><br />I understood additional constraint but I could not understand how I will modify the objective function ? How can I solve this problem ,with which solver ? <br /><br />Any help is appreciated <br /><br />Thank you so muchUnknownhttps://www.blogger.com/profile/10419863758087972465noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-73483943400274831342018-12-14T18:07:45.297-05:002018-12-14T18:07:45.297-05:00You are correct about item 1, and in fact in the M...You are correct about item 1, and in fact in the MIP2 model (discussed in the next post, which I'm actually working on right now) I did what you suggested second (enforce symmetry and let the presolver simplify things).<br /><br />Your second cut is interesting. I would not have expected it to help much, but it does make the lower bound tighter. Compared to my initial run, the cut gives a higher lower bound out of the gate. For the first couple of minutes or so, it slows down progress on the primal bound, but between three and four minutes in I get a better primal bound with the constraint than without. By the five minute mark, CPLEX is again nibbling at the lower bound, but at least the gap is smaller. I'm adding the cut as another command line option (with your name on it).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-27801042718081939362018-12-14T17:37:12.047-05:002018-12-14T17:37:12.047-05:00Two observations:
1. Because distance is symmetric...Two observations:<br />1. Because distance is symmetric, you can cut the problem size in half by using variables $d_{ij}$ with $i < j$ and then minimizing $\sum_{i < j} (f_{ij}+f_{ji}) d_{ij}$. Equivalently, enforce $d_{ij} = d_{ji}$ in your original formulation, and let the presolver do this for you.<br />2. Because $\sum_{k=1}^{n-1} k(n-k) = (n^3-n)/6$, where $n=26$, is the sum of distances between unordered pairs of positions, you can add a cut $\sum_{i < j} d_{ij} = 2925$.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-426576892342553622018-12-14T16:54:49.175-05:002018-12-14T16:54:49.175-05:00Sorry, I don't have a reference at hand. It...Sorry, I don't have a reference at hand. It's not to hard to prove mathematically, and I suspect it has been used as a homework assignment on more than one occasion. You may be able to find a version of it in the book "Model Building in Mathematical Programming" by H. P. Williams, but I'm not positive it's covered there.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-6170662551090385562018-12-14T12:51:08.837-05:002018-12-14T12:51:08.837-05:00Dear Dr. Rubin
Would you please provide a referenc...Dear Dr. Rubin<br />Would you please provide a reference for your claim? Especially I am looking to read more about the first statement.<br />Thank youUnknownhttps://www.blogger.com/profile/17645734031975767709noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3467198997962225632018-12-08T19:46:13.762-05:002018-12-08T19:46:13.762-05:00No, start solutions do not change the algorithm (p...No, start solutions do not change the algorithm (provided that either the starting solution is feasible or that it is tested in the subproblem and the subproblem is given a chance to reject it).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-88070093947696691232018-12-08T19:40:45.758-05:002018-12-08T19:40:45.758-05:00I am trying to implement BD with start solution an...I am trying to implement BD with start solution and regularization by simple adding a quadratic term to the objective function. When using however a start solution to initialize my master problem, the algorithm overestimates the final cost. Do you change the algorithm anyhow when using start solutions?Unknownhttps://www.blogger.com/profile/04542908134686208805noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-72934678260477134072018-11-28T01:53:43.709-05:002018-11-28T01:53:43.709-05:00Dear Paul, thanks a lot for your answer. It helps ...Dear Paul, thanks a lot for your answer. It helps me already so far, that it makes sure that I'm not missing out a simple solution. Let's see how I will go with this :)Unknownhttps://www.blogger.com/profile/00458522637477099164noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-10155991763437113102018-11-24T11:52:45.463-05:002018-11-24T11:52:45.463-05:00I'm not all that familiar with non-convex opti...I'm not all that familiar with non-convex optimization (I know enough to recognize it when I see it ... and run screaming in the opposite direction), but I don't think there's any way you can discretize the nonconvexity away.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-17446817765743753882018-11-23T03:41:17.780-05:002018-11-23T03:41:17.780-05:00Dear Paul,
Hopefully, I haven't missed the an...Dear Paul,<br /><br />Hopefully, I haven't missed the answer to my question somewhere in the post. My question is related to the case where all variables are continuous.<br /><br />I have a non-convex quadratic program of the form (c's are given positive numbers):<br /><br />min c_1*x_1 + c_2*x_2*x_4 - c_3*x_3*x_4<br />s.t. Ax <= b, <br /> x >= 0<br /><br />Due to the fact that the problem is not convex, I'm not able to solve it with a convex solver. Is there a way to transform the problem (e.g. linearise the objective function) to get a MIP formulation.<br /><br />Thanks a lot in advance!<br />Dirk <br /> Unknownhttps://www.blogger.com/profile/00458522637477099164noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-85619518408007235542018-11-20T14:12:43.451-05:002018-11-20T14:12:43.451-05:00You are very welcome. Glad it helped.You are very welcome. Glad it helped.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-42478835232028824932018-11-20T13:38:36.998-05:002018-11-20T13:38:36.998-05:00Dear pro. Rubin:
Thank you so much! Yes, i set th...Dear pro. Rubin:<br />Thank you so much! Yes, i set the replacement strategy to 1. You answer really helped me. Thank you again!<br />Best regards,<br />QingweiQingweihttps://www.blogger.com/profile/15014558290578669831noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-52412877820312153392018-11-19T13:56:12.581-05:002018-11-19T13:56:12.581-05:00Yes, you can increase the capacity between calls, ...Yes, you can increase the capacity between calls, at least with the interactive optimizer. I haven't tried it with any of the programming APIs, but I would expect it to work there too. The catch is that if the previous call to populate exhausted the search tree, or at least exhausted all feasible solutions, you may not pick up any more solutions with the second call.<br /><br />If you are using replacement strategy 1 (keep the 10 or 20 best solutions), bear in mind that on the second call CPLEX will *not* go back to parts of the tree it previously visited to find solutions that it previously ignored (as not better than the worst of the 10 solutions in the first pool), even if they might now qualify as one of the 20 best.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-68590685672933826362018-11-19T12:18:17.450-05:002018-11-19T12:18:17.450-05:00Hi Dr. Rubin,
I am trying to change the parameter ...Hi Dr. Rubin,<br />I am trying to change the parameter of solution capacity between successive calls of populate. But it seems only the capacity of the first populate is keeping (for example i populate 100 times, and the first capacity is set to 10. and then i set the capacity to 20 and call populate again. ) . Can i change the capacity parameter when calling multiple time of populate？Thank you Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-39003032678881945802018-11-15T13:52:04.299-05:002018-11-15T13:52:04.299-05:00OK, again thanks much. Very helpful and I learned ...OK, again thanks much. Very helpful and I learned something new :-)Unknownhttps://www.blogger.com/profile/05810668373168924861noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-41007459946052958332018-11-15T13:27:22.177-05:002018-11-15T13:27:22.177-05:00I've seen pw-linear functions of two arguments...I've seen pw-linear functions of two arguments, but not in a while, and I can't point to any examples.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-86142445191095733622018-11-15T13:09:52.732-05:002018-11-15T13:09:52.732-05:00Thanks Paul.
When I include temp2 (capital gains ...Thanks Paul.<br /><br />When I include temp2 (capital gains tax associated with taxable income) in the objective function the cgt constraint works as I want but it has the, for me, unintended side effect of causing the model to minimize income tax which is slightly different from maximizing spendable. The minimization gives unwanted transfers of money from 401k to investment account. All that does lower the taxes and increase the object function while slightly lowering spendable. <br /><br />I think I will try to convert the capital gains function from 2d to 3d and having piecewise linear plains to represent the function. Have you ever seen this done? know of any examples?<br /><br />Thanks Much,Unknownhttps://www.blogger.com/profile/05810668373168924861noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-39441738159246357132018-11-15T11:15:40.601-05:002018-11-15T11:15:40.601-05:00I assume that first constraint was supposed to be ...I assume that first constraint was supposed to be == or >= rather than <=; otherwise the model is unbounded. Assuming that, spendable increases as CG tax decreases, and your model lets you have zero CG tax by setting temp2 equal to temp1. I suspect you need to tie temp2 to income tax in a way that discourages padding temp2, but that is an accounting question and I am (blissfully!) ignorant of accounting.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-3992184703544826722018-11-14T19:26:40.935-05:002018-11-14T19:26:40.935-05:00Sorry for not being more clear. The object functio...Sorry for not being more clear. The object function I want is to maximize spendable dollars. Call this 'spendable.' Then I have another constraint that takes income sources with their various type of taxes and other expenses to define s. The model is to create a plan for using retirement funds optimally. So as it maximizes after tax spendable money the constraint defining s includes these income(s) minus their taxes. So, yes, the lower the tax the higher the spendable money. <br /><br />maximize spendable<br />s.t. <br />401k Withdrawal + Investment Account Withdrawal - Income tax - CapGainsTax <= spendable<br />Income tax >= 7 linear functions for the income tax brackets x=taxable income<br />temp1 >= 3 linear functions for the capital gains brackets x=taxable income + capital gains <br />temp2 >= 3 linear functions for the capital gains brackets x=taxable income<br />CapGainsTax >= temp1 - temp2<br /><br />I hope that is more clear.<br />Thanks,Unknownhttps://www.blogger.com/profile/05810668373168924861noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-86851290586250538692018-11-14T18:25:48.972-05:002018-11-14T18:25:48.972-05:00I'm not sure I'm following this, but my fi...I'm not sure I'm following this, but my first guess would be that you might be minimizing ctg rather than minimizing total tax. If I were filling out a tax return and focused only on minimizing capital gains tax, I would declare all my income as "ordinary". That would give me not capital gains tax (but would have me paying more tax overall, since I just passed up the lower CG rate in favor of the higher ordinary rate).Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-57531668367573562692018-11-14T17:23:31.837-05:002018-11-14T17:23:31.837-05:00Very useful post. I used it to guide the construct...Very useful post. I used it to guide the construction of a income tax calculation and it works great. I then tried to use it for calculation of capital gains taxes but this does not work. Basically I created the same piecewise linear tax function and then tried ctg >= f(ti+cg) - f(ti) where cgt is the capital gains tax, f() is the piecewise linear function, ti is taxable income and cg is capital gains. What happens is that f(ti) rises to match f(ti+cg) so cgt becomes zero. I don't know how to correct this or how to rewrite the capital gains tax function to get around this. Any ideas?<br />Thanks much,Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-70718070017336515972018-11-12T09:07:30.573-05:002018-11-12T09:07:30.573-05:00As written, no; the function uses lm to fit models...As written, no; the function uses lm to fit models. Hypothetically, you could change lm to glm inside the function to fit generalized linear models. The catch is that the add1 and drop1 functions use a deviance F-test for glm models, so I'm not sure it would truly conform to the original intent (picking variables based on p-values). Still, the deviance test is an F-test, so maybe this would be closer to what you want than what leaps::regsubsets does.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.com