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. Thanks in advance Regards Khris.
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.
Hi Petr, Thanks for the reply. Your reply answers the question perfect. Unfortunately converting the problem to linear opt would increase the number of variable making it non solvable. I guess a general approach will be unfeasible so need to look for specific approach. Appreciate if you have any more wise advices. Rest fine Khris. -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634078.html Sent from the R help mailing list archive at Nabble.com.
On Thu, Jun 21, 2012 at 02:46:10AM -0700, khris wrote:> Hi Petr, > > Thanks for the reply. Your reply answers the question perfect. > Unfortunately converting the problem to linear opt would increase the number > of variable making it non solvable. I guess a general approach will be > unfeasible so need to look for specific approach.Hi Khris: A general approach to reduce the size of the system is to select a subset of the binary variables and set each of them to a constant. This reduces the size of the system for the solver. Trying all combinations of the chosen variables and choosing the best yields the solution of the original problem. How many variables has the original and the transformed system? Can you send the original quadratic system? If it is too large, put it on the web and send a link to it. Petr.
Hi Petr, Appreciate your feedback and sorry for the delay in responding. The following is the description of problem from start:- We have a set of sensors in XY plane arranged in more or less a rectangular grid and we know their (x,y) co-ordinate. Now these sensors send data and from that data using Data mining techniques I can find out the relative distance between Sensors. So the question was using the relative distance matrix obtained from Database can we figure out (x,y) position of sensors in DB. So I modelled the problem as inexact match between 2 Graphs. Since the best package on Graphs i.e. iGraph does not have any function for Graph matching I converted the Inexact graph matching problem to Binary Quadratic Opt Problem. Since there is no specialized package for Binary Quadratic Opt, based on your input I converted it into Binary Linear Opt problem. So now the problem is I have a solution but it is not scalable at all. The way out seems to be(as you too have pointed), 1. To not model it as generalized inexact Graph matching problem. But some how models it as rectangular grid matching with focus on vertex matching rather edge matching. That will bring down the complexity from n^4 to n^2 where n is the number of sensors. 2. Another alternative could be that opt problem may fall in the category of semi definite programming, then we have efficient solvers for that. This is the story, appreciate your feedback. Rest fine Khris. -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634589.html Sent from the R help mailing list archive at Nabble.com.
On Tue, Jun 26, 2012 at 11:52:15PM -0700, khris wrote:> Hi Petr, > > Appreciate your feedback and sorry for the delay in responding. The > following is the description of problem from start:- > > We have a set of sensors in XY plane arranged in more or less a rectangular > grid and we know their (x,y) co-ordinate. Now these sensors send data and > from that data using Data mining techniques I can find out the relative > distance between Sensors. So the question was using the relative distance > matrix obtained from Database can we figure out (x,y) position of sensors in > DB.Hi Khris: If i understand the problem correctly, you have a list of (x,y) coordinates, where some sensor is located, but you do not know, which sensor is there. The database contains data for each sensor identified in some way, but you do not know the mapping between sensor identifiers from the database and the (x,y) coordinates. Is this correct?> So I modelled the problem as inexact match between 2 Graphs. Since the best > package on Graphs i.e. iGraph does not have any function for Graph matchingI think, the problem is close to http://en.wikipedia.org/wiki/Graph_isomorphism You have estimates of the distances between the sensors using identifiers from the database. So, you know, which pairs of sensors are close. This is one graph. The other graph is the graph of closeness between the known (x,y) coordinates. You want to find a mapping between the vertices of these two graphs, which preserves edges.> I converted the Inexact graph matching problem to Binary Quadratic Opt > Problem. Since there is no specialized package for Binary Quadratic Opt, > based on your input I converted it into Binary Linear Opt problem.The problem of graph isomorphism is hard in general, but if one of the graphs is a rectangular grid, which does not have too many automorphisms, the problem is not too hard. Try, for example, the following approach. Look for small groups of the sensors, which form connected subgraphs, which have the form of small pieces of the rectangular grid. If you have such a small subgraph, look for nodes, which can be add to the subgraph to make it a larger piece of the grid. To start, the algorithm can choose any sensor, say S_0. Find all its neighbours. There should be at most 4 neighbours (in an ideal grid). Call the group of these neighbours S_1. Then, find sensors, which are neighbours to at least two members of S_1. Call them group S_2. The connections between S_0, S_1 and S_2 should form a pattern like 2 - 1 - 2 | | | 1 - 0 - 1 | | | 2 - 1 - 2 The digits 0, 1, 2 distinguish elements of S_0, S_1, S_2. Continue this in order to enlarge this recognised pattern. If the grid is not ideal, the process may require to maintain several candidate connected patterns and choose those, which can be extended with further sensors and discard those, which cannot. Another approach is as follows. Choose a random mapping between the sensors and (x,y). Define a measure of the quality of the mapping. For example, the number of matching edges minus the number of non-matching edges. Then, use local search to maximize the quality. For example, in each step, exchange two sensors in a way, which increases the quality. Do you think that some of these approaches is applicable to your situation? Petr.
Hi Khris, If all your variables are binary then you may want to check CPLEX and/or Gurobi (both provide a free academic license). http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ http://www.gurobi.com/products/additional-products-using-gurobi/r The algorithms that CPLEX and Gurobi use for quadratic programming are designed to work with convex objective functions, with the one exception when all variables are binary. In that case CPLEX and Gurobi apply some transformation that in certain cases will allow you to solve binary quadratic optimization problems. Regards, Menkes -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634971.html Sent from the R help mailing list archive at Nabble.com.