[R] Binary Quadratic Opt?

[khris]

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.