> ----- 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" <[email protected]> > To: [email protected] > 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 > [email protected] > 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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
