Binary Quadratic Opt?
Locked
 
|
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-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. |
Re: Binary Quadratic Opt?
|
On Fri, Jun 15, 2012 at 05:17:36PM +0530, Anup Bhatkar wrote:
> 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. Hello: I do not know, whether there is a package directly suitable for binary quadratic optimization. However, one can try the following. A quadratic problem with binary variables may be reformulated as a linear problem with additional binary variables. Linear problem with binary variables may be solved using lpSolve package http://cran.at.r-project.org/web/packages/lpSolve/index.html The transformation can be done as follows. For every product x_1*x_2, add a new variable y, use it instead of x_1*x_2 to make the objective function linear and add the constraints 0 <= x_1 + x_2 - 2*y <= 1 If x_1, x_2, y are all {0, 1}, then these constraints are equivalent to the constraint y = x_1 * x_2 This transformation may increase the number of variables significantly, so it is not guaranteed that the problem is solvable. However, it can be. Hope this helps. Petr Savicky. ______________________________________________ [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. |
|
|
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. |
Re: Binary Quadratic Opt?
|
|
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-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. |
|
|
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. |
Re: Binary Quadratic Opt?
|
|
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. ______________________________________________ [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. |
|
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/r The 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 |
|
|
Hi Menkes,
Thanks for the reply but just academically free license won't work for me. GNU or more is reqd. Rest fine Khris. On Jun 30, 2012, at 7:21 PM, menkes [via R] wrote: Hi Khris, |
|
|
In reply to this post by Petr Savicky
Hi, Petr,
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. Regards Khris.
|
Re: Binary Quadratic Opt?
|
|
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. |
|
|
Thanks Petr for the reply.
Let me do implementation and see how how goes. Enjoy your vacation. Rest fine 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: |
|
|
In reply to this post by Petr Savicky
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: |
Re: Binary Quadratic Opt?
|
|
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-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. |
|
|
On Aug 2, 2012, at 12:39 PM, Petr Savicky [via R] wrote: On Wed, Aug 01, 2012 at 04:55:30AM -0700, khris wrote: I wrote about another approach, reducing the "Graph matching with upper bound on degree of vertex" to "Graph isomorphism where degree of vertex has upper bound" since "Graph isomorphism where degree of vertex has upper bound" has tractable solution. This approach seems promising. I also came across solving Graph matching using Simulated Annealing (http://randomwalker.info/luther/kaggle-deanonymization/Graph_Matching_via_Simulate.html) which also seems promising. How do you feel about these? > 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 thought lpSolve is the best optimizer freely available in R so I was using it. Do you recommend another one? But if my model consist of 100,00 binaray variable then I assume even commercial optimizer also won't scale? Appreciate your comments. Thanks in adv Khris.
|
Re: Binary Quadratic Opt?
|
This discussion needs to be taken off (this) list, as it appears to
have nothing to do with R. -- Bert On Thu, Aug 2, 2012 at 2:27 AM, khris <[hidden email]> wrote: > > On Aug 2, 2012, at 12:39 PM, Petr Savicky [via R] wrote: > >> 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. >> > > OK. I guess then my approach to solve the Graph matching problem using binary opt pr. seems destined to fail. I know you told about Kohenan maps but I am not exited about it since it some sort of neural network which involves training. So that approach may not be suitable. > I wrote about another approach, reducing the "Graph matching with upper bound on degree of vertex" to "Graph isomorphism where degree of vertex has upper bound" since "Graph isomorphism where degree of vertex has upper bound" has tractable solution. This approach seems promising. > > I also came across solving Graph matching using Simulated Annealing (http://randomwalker.info/luther/kaggle-deanonymization/Graph_Matching_via_Simulate.html) which also seems promising. > > How do you feel about these? > > >> > 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? > > I thought lpSolve is the best optimizer freely available in R so I was using it. Do you recommend another one? But if my model consist of 100,00 binaray variable then I assume even commercial optimizer also won't scale? > > Appreciate your comments. > > Thanks in adv > Khris. > > > > >> >> 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-tp4633521p4638835.html >> To unsubscribe from Binary Quadratic Opt?, click here. >> NAML > > > > > > -- > View this message in context: http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4638844.html > Sent from the R help mailing list archive at Nabble.com. > [[alternative HTML version deleted]] > > ______________________________________________ > [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. -- Bert Gunter Genentech Nonclinical Biostatistics Internal Contact Info: Phone: 467-7374 Website: http://pharmadevelopment.roche.com/index/pdb/pdb-functional-groups/pdb-biostatistics/pdb-ncb-home.htm ______________________________________________ [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. |
Re: Binary Quadratic Opt?
|
|
In reply to this post by khris
On Thu, Aug 02, 2012 at 02:27:43AM -0700, khris wrote:
> > On Aug 2, 2012, at 12:39 PM, Petr Savicky [via R] wrote: > > > 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. > > > > OK. I guess then my approach to solve the Graph matching problem using binary opt pr. seems destined to fail. I know you told about Kohenan maps but I am not exited about it since it some sort of neural network which involves training. So that approach may not be suitable. > I wrote about another approach, reducing the "Graph matching with upper bound on degree of vertex" to "Graph isomorphism where degree of vertex has upper bound" since "Graph isomorphism where degree of vertex has upper bound" has tractable solution. This approach seems promising. > > I also came across solving Graph matching using Simulated Annealing (http://randomwalker.info/luther/kaggle-deanonymization/Graph_Matching_via_Simulate.html) which also seems promising. > > How do you feel about these? I agree with Bert that this does not belong to this list. The only thing, which i can suggest for graph isomorphism is to try igraph package. If you have questions concerning its use, start a new thread. I have no experience with graph isomorphism and igraph. > > > 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? > > I thought lpSolve is the best optimizer freely available in R so I was using it. Do you recommend another one? But if my model consist of 100,00 binaray variable then I assume even commercial optimizer also won't scale? The problem is not that lpSolve is not a good solver, but that integer linear programming is not suitable for your problem, since it requires too large instances to express graph isomorphism. I do not believe that other solvers can handle these instances significantly better. 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. |
|
|
Thanks for the response Petr
On Aug 2, 2012, at 11:11 PM, Petr Savicky [via R] wrote: On Thu, Aug 02, 2012 at 02:27:43AM -0700, khris wrote: |
«
Return to R help
|
1 view|%1 views
Loading...
| Powered by Nabble | Edit this page |