On Wed, Aug 01, 2012 at 04:55:30AM -0700, khris wrote: > Hi Petr, > > It been sometime since I wrote. But here are the latest developments. > > When I give the binary linear opt problem to lpSolve optimizer than for small > instance it gives correct answer but when size of nodes increase let's say 16 > then there are about 2000 binary variables and lpSolve just does not come > back with any answer even after running for a full day. I plan to solve for > node size upto atleast 100, so I guess I need to do something fundamentally > different. > > Now I understand that lpSolve is using Branch and Bound Algorithm which to me > looks highly inefficient, for in the wrost case it will try to solve 2^n LP > relaxation problem. Maybe that's why I do not get answer even when n=16. So > what do I do to make lpSolve solve problem efficiently.
Integer linear programming is an NP-complete problem and in general requires an exponential time. It is not surprising that lpSolve failed to solve a problem with 2000 variables. It can solve some problems with a few hundreds of variables, but not every such problem. > In the lpSolve document there does not seem to be any option where one can > specify which variable should the optimizer use to use LP relaxation first? > Is there way to control in some way Branch and Bound algorithm used by > lpSolve apart from the going in side the code and tweaking it. I do not know, whether this may be controlled. Do you have a specific reason to use lpSolve for your problem? Petr. ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
