Hi Petr, It been sometime since I wrote. But here are the latest developments.
When I give the binary linear opt problem to lpSolve optimizer than for small instance it gives correct answer but when size of nodes increase let's say 16 then there are about 2000 binary variables and lpSolve just does not come back with any answer even after running for a full day. I plan to solve for node size upto atleast 100, so I guess I need to do something fundamentally different. Now I understand that lpSolve is using Branch and Bound Algorithm which to me looks highly inefficient, for in the wrost case it will try to solve 2^n LP relaxation problem. Maybe that's why I do not get answer even when n=16. So what do I do to make lpSolve solve problem efficiently. In the lpSolve document there does not seem to be any option where one can specify which variable should the optimizer use to use LP relaxation first? Is there way to control in some way Branch and Bound algorithm used by lpSolve apart from the going in side the code and tweaking it. Appreciate your feedback. Thanks Khris. On Jul 4, 2012, at 8:25 PM, Petr Savicky [via R] wrote: > On Mon, Jul 02, 2012 at 06:11:37AM -0700, khris wrote: > > > Hi, Petr, > > > > > > > > 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? > > > > Yes. > > > > > > > > > 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. > > > > Yes, I agree the problem is more into Graph theoretic domain to be more > > precise inexact graph matching whose generalization is the Graph > > Isomorphism problem. The problem is more general than Graph Isomorphism. > > Let me define the problem more formally. > > > > We have 2 weighted undirected graphs. In one graph I know the distance of > > every vertex from every other vertex whereas in another graph I know only > > which vertices are close to a given vertex. So I know the neighboring > > vertices given a vertex. So the distance matrix of other Graph is > > incompletely known. So the question is can I find the best alignment > > between the 2 graphs. > > > > Ex:- G1 is know the complete distance matrix. For G2, if there are four > > vertices let's say (v1, v2, v3 v4) the I know edge weight (v1,v2) and > > (v1,v3) but have no information of edge weight(v1,v4). Similarly I know > > about (v2,v3) but no information about edge weights (v2,v4) or (v3,v4). > > > > So I was thinking of not to model it as general inexact Graph matching > > problem for then the complexity n^4. It seems the best way to model the > > solution is to consider only edges with are at distance of 1 unit i.e. > > closest edge from every vertex and not every edge from the given vertex. > > This will bring down the complexity from n^4 to 6*6*n^2 assuming every > > vertex has atmost 6 neighboring vertex. Quadratic complexity seems > > manageable. Ofcourse now the solution become lot more sensitive to the > > errors in Graph G2. Assuming best case if I have no errors in G2 i.e. for > > every vertex I know correctly it's closest neighbored in the rectangular > > grid then optimizing distance between G1 and G2 should give me best correct > > alignment. This seems to be the best approach under current circumstance. > > > > As far as implementation goes I think I still have to use optimization > > package since there are not any readily and freely available function for > > inexact graph matching. > > > > Petr how do you feel about it. Appreciate your feedback. > > Hi. > > I am on vacations with only occasional access to the internet. > > One way to solve your problem is to formulate it in a way, > in which it can be solved by some existing solver. I do not > know, whether this is possible. Look at self-organizing maps > (Kohonen maps). They try to map points with unknown mutual > relationships to a 2 dimensional grid. However, i am not sure, > whether the input to this method is suitable for your problem. > > Another way is to write your own program. I sent some suggestions > in this direction in a previous email. If you want, we can discuss > this in more detail next week, when i am back from vacations. > > All the best, Petr. > > ______________________________________________ > [hidden email] 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. > > > If you reply to this email, your message will be added to the discussion > below: > http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4635416.html > To unsubscribe from Binary Quadratic Opt?, click here. > NAML -- View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4638654.html Sent from the R help mailing list archive at Nabble.com. [[alternative HTML version deleted]] ______________________________________________ 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.
