[R] Binary Quadratic Opt?

[Petr Savicky]

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 matching

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