Hi Bert, I won't post any more messages on this thread as problem has shifted from Optimization in R to Graph Algorithms.
Rest fine Khris. On Aug 2, 2012, at 9:13 PM, Bert Gunter [via R] wrote: > 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 <[hidden email]> 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]] > > > > ______________________________________________ > > [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. > > > > -- > > 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 > > ______________________________________________ > [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-tp4633521p4638896.html > To unsubscribe from Binary Quadratic Opt?, click here. > NAML -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4639006.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.
