[R] Binary Quadratic Opt?

[Bert Gunter]

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 <khris108 at 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 at 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