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. ______________________________________________ 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.
