[R] Binary Quadratic Opt?

[Petr Savicky]

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.