Re: [Help-glpk] GLPK for Pattern Recognition

[Nigel Galloway]

> ----- Original Message -----
You may find that it helps to seperate finding the best fit from finding the
points which define the line. When I was looking at this earlier in the year I
came up with yacfs.mod (see glpk examples). BigMing that produces good results
for test data which actually represents a single line.

However general data doesn't always provide insight that a special case does.
Looking at seperating two paralell lines proved difficult because if you have a
good line it wants to be mid way between the two.

Not careing about the line being a good fit produces attachments 
http://www.geocities.com/nigel_galloway/parl1.JPG and 
http://www.geocities.com/nigel_galloway/parl2.JPG
. While neither line is a good fit it does in each case identify the
points which lie on a line. parl2.jpg also demonstrates that it chooses the
line with most points. The points on the line can then be taken and yacfs.mod
applied to find the best fit.

Attachments http://www.geocities.com/nigel_galloway/glpk0.1.JPG, 
http://www.geocities.com/nigel_galloway/glpk0.2.JPG, 
http://www.geocities.com/nigel_galloway/glpk0.3.JPG and 
http://www.geocities.com/nigel_galloway/glpk1.0.JPG show the
algorithm applied to the original test data with different degrees of tolerance.

I applied the algorithm to your test data with different degrees of tolerance,
see attachments http://www.geocities.com/nigel_galloway/Cern0.1.JPG, 
http://www.geocities.com/nigel_galloway/Cern0.2.JPG and 
http://www.geocities.com/nigel_galloway/Cern0.5.JPG.


> From: "Gianluca Cerminara" <address@hidden>
> To: address@hidden
> Subject: [Help-glpk] GLPK for Pattern Recognition
> Date: Thu, 27 Aug 2009 00:20:46 +0400
> 
> 
> 
> Hi,
>       I'm a new user of your nice library. We are trying to implement an
> algorithm  for track fitting and pattern recognition for an HEP
> experiment at CERN based on MIP and LP techniques as described in the note:
> http://cms.cern.ch/iCMS/jsp/openfile.jsp?type=NOTE&year=2007&files=NOTE2007_007.pdf
> 
> The first prototype is working nicely but we are experiencing some
> performance problems: the speed of the algorithm is not yet competitive.
> Since I'm not an expert in linear programming I need some help to
> understand if some of the options of the GLPK APIs can help.
> In particular what are the pros and cons of calling glp_intopt after
> having performed the LP relaxation with the glp_simplex instead of
> calling the built-in presolver?
> Any reference would be appreciated.
> 
> We are using version 4.39.
> Thanks in advance for any feedback,
> 
> Best regards,
>       G
> 
> --
> --------------------------
> Gianluca Cerminara
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk

>


-- 
_______________________________________________
Surf the Web in a faster, safer and easier way:
Download Opera 9 at http://www.opera.com

Powered by Outblaze