[R] Binary Quadratic Opt?

[Petr Savicky]

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.

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

Petr.