Thanks for the response Petr On Aug 2, 2012, at 11:11 PM, Petr Savicky [via R] wrote:
> 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. > > ______________________________________________ > [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-tp4633521p4638921.html > To unsubscribe from Binary Quadratic Opt?, click here. > NAML -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4639005.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.
