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]]
