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. ______________________________________________ R-help@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.
