17 messages
Open this post in threaded view
|
Report Content as Inappropriate

 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. ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

 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.
Open this post in threaded view
|
Report Content as Inappropriate

 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. ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|
Report Content as Inappropriate

 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.
Open this post in threaded view
|
Report Content as Inappropriate

 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_isomorphismYou 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. ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|
Report Content as Inappropriate

 In reply to this post by khris 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/rThe 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
Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

 On Wed, Aug 01, 2012 at 04:55:30AM -0700, khris wrote: > 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. Integer linear programming is an NP-complete problem and in general requires an exponential time. It is not surprising that lpSolve failed to solve a problem with 2000 variables. It can solve some problems with a few hundreds of variables, but not every such problem. > 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. I do not know, whether this may be controlled. Do you have a specific reason to use lpSolve for your problem? Petr. ______________________________________________ [hidden email] mailing list https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate

Open this post in threaded view
|
Report Content as Inappropriate