subject:"\[R\] Binary Quadratic Opt\?"

Re: [R] Binary Quadratic Opt?

2012-08-03 Thread khris

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:

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.

If you reply to this email, your message will be added to the discussion
below:
http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4638921.html
To unsubscribe from Binary Quadratic Opt?, click here.
NAML

--
View this message in context:
http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4639005.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.

[R] Binary Quadratic Opt

2012-08-03 Thread khris

Hi Bert,

I won't post any more messages on this thread as problem has shifted from
Optimization in R to Graph Algorithms.

Rest fine
Khris.

On Aug 2, 2012, at 9:13 PM, Bert Gunter [via R] wrote:

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.

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?

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]]

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

If you reply to this email, your message will be added to the discussion
below:
http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4638896.html
To unsubscribe from Binary Quadratic Opt?, click here.
NAML

--
View this message in context:

Re: [R] Binary Quadratic Opt?

2012-08-02 Thread Petr Savicky

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.

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

Re: [R] Binary Quadratic Opt?

2012-08-02 Thread khris


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]]

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

Re: [R] Binary Quadratic Opt?

2012-08-02 Thread Bert Gunter

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 khris...@gmail.com 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.

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

Re: [R] Binary Quadratic Opt?

2012-08-02 Thread Petr Savicky

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.

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?

Petr.

Re: [R] Binary Quadratic Opt?

2012-08-01 Thread khris

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.

Re: [R] Binary Quadratic Opt?

2012-07-05 Thread khris

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:
 
  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-tp4633521p4635457.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.

Re: [R] Binary Quadratic Opt?

2012-07-04 Thread Petr Savicky

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.

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

Re: [R] Binary Quadratic Opt?

2012-07-02 Thread khris

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, 
 
 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 
 
 If you reply to this email, your message will be added to the discussion 
 below:
 http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634971.html
 To unsubscribe from Binary Quadratic Opt?, click here.
 NAML



--
View this message in context: 
http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4635082.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.

Re: [R] Binary Quadratic Opt?

2012-07-02 Thread khris

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.

Regards
Khris.

 
  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

Re: [R] Binary Quadratic Opt?

2012-06-30 Thread menkes

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

--
View this message in context: 
http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634971.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.

Re: [R] Binary Quadratic Opt?

2012-06-29 Thread 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.

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

Re: [R] Binary Quadratic Opt?

2012-06-27 Thread khris

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.

Re: [R] Binary Quadratic Opt?

2012-06-21 Thread khris

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.


--
View this message in context: 
http://r.789695.n4.nabble.com/Binary-Quadratic-Opt-tp4633521p4634078.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.

Re: [R] Binary Quadratic Opt?

2012-06-21 Thread Petr Savicky

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.

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

[R] Binary Quadratic Opt?

2012-06-15 Thread Anup Bhatkar

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.

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

Re: [R] Binary Quadratic Opt?

2012-06-15 Thread Petr Savicky

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.

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

Re: [R] Binary Quadratic Opt?

[R] Binary Quadratic Opt

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

[R] Binary Quadratic Opt?

Re: [R] Binary Quadratic Opt?

18 matches

Site Navigation

Mail list logo

Footer information