[R] Binary Quadratic Opt?

[Petr Savicky]

On Fri, Jun 15, 2012 at 05:17:36PM +0530, Anup Bhatkar wrote:
> Hello,
> 
> I have to solve Binary Quadratic Optimization problem i.e the objective function is quadratic, constraints are linear and variable are binary. I checked the "quadprog" package but it does not seem to be right choice for the problem.
> 
> Can any one suggest what would be the best package to solve the Binary Quadratic opt.

Hello:

I do not know, whether there is a package directly suitable for binary
quadratic optimization. However, one can try the following.

A quadratic problem with binary variables may be reformulated as a linear
problem with additional binary variables. Linear problem with binary
variables may be solved using lpSolve package

  http://cran.at.r-project.org/web/packages/lpSolve/index.html

The transformation can be done as follows. For every product x_1*x_2, add
a new variable y, use it instead of x_1*x_2 to make the objective function
linear and add the constraints

  0 <= x_1 + x_2 - 2*y <= 1

If x_1, x_2, y are all {0, 1}, then these constraints are equivalent
to the constraint

  y = x_1 * x_2

This transformation may increase the number of variables significantly, so
it is not guaranteed that the problem is solvable. However, it can be.

Hope this helps.

Petr Savicky.