On Aug 2, 2012, at 12:39 PM, Petr Savicky [via R] wrote: > 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. >
OK. I guess then my approach to solve the Graph matching problem using binary opt pr. seems destined to fail. I know you told about Kohenan maps but I am not exited about it since it some sort of neural network which involves training. So that approach may not be suitable. I wrote about another approach, reducing the "Graph matching with upper bound on degree of vertex" to "Graph isomorphism where degree of vertex has upper bound" since "Graph isomorphism where degree of vertex has upper bound" has tractable solution. This approach seems promising. I also came across solving Graph matching using Simulated Annealing (http://randomwalker.info/luther/kaggle-deanonymization/Graph_Matching_via_Simulate.html) which also seems promising. How do you feel about these? > > 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? I thought lpSolve is the best optimizer freely available in R so I was using it. Do you recommend another one? But if my model consist of 100,00 binaray variable then I assume even commercial optimizer also won't scale? Appreciate your comments. Thanks in adv Khris. > > Petr. > > ______________________________________________ > [hidden email] 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. > > > If you reply to this email, your message will be added to the discussion > below: > http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4638835.html > To unsubscribe from Binary Quadratic Opt?, click here. > NAML -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4638844.html Sent from the R help mailing list archive at Nabble.com. [[alternative HTML version deleted]] ______________________________________________ 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.
