Re: [Help-glpk] GLPK for Pattern Recognition

[Andrew Makhorin]

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

You may try to enable cutting planes; sometimes this helps.

Could you post me (not to the list) an example of your mip instance
in mps or cplex lp format? Then I could say something more definite.

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

Obtaining optimal solution to lp relaxation with glp_simplex is just
a feature that allows avoiding this step in glp_intopt (sometimes it
may take a long time). As a rule there is no reason to disable mip
presolver, in which case solving lp relaxation is not needed.


Andrew Makhorin