On Thu, Aug 02, 2012 at 02:27:43AM -0700, khris wrote: > > 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?
I agree with Bert that this does not belong to this list. The only thing, which i can suggest for graph isomorphism is to try igraph package. If you have questions concerning its use, start a new thread. I have no experience with graph isomorphism and igraph. > > > 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? The problem is not that lpSolve is not a good solver, but that integer linear programming is not suitable for your problem, since it requires too large instances to express graph isomorphism. I do not believe that other solvers can handle these instances significantly better. 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.
