This discussion needs to be taken off (this) list, as it appears to have nothing to do with R.
-- Bert On Thu, Aug 2, 2012 at 2:27 AM, khris <khris...@gmail.com> 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? > > >> > 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. -- Bert Gunter Genentech Nonclinical Biostatistics Internal Contact Info: Phone: 467-7374 Website: http://pharmadevelopment.roche.com/index/pdb/pdb-functional-groups/pdb-biostatistics/pdb-ncb-home.htm ______________________________________________ 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.
