[Help-glpk] Re: The GLPK questions

[Rastislav Galia]

On Mon, 3 Feb 2003, Andrew Makhorin wrote:

> Thank you for your interest in glpk.
> 
> >I'd like to express my feeling from using GLPK. I've been testing the soft 
> >for a while mostly on big SetCovering/SetParting problems. It seems the 
> >GLPK has quite stable and performing LP solver (good job :-) ), but MIP is 
> >a bit simplistic and I feel there is a potential for improvement. 
> 
> Yes, you are right. The mip solver currently implemented in glpk is
> based on the branch-and-bound method with an easy branching heuristic,
> so it is inefficient for most interesting mip problems. Besides, many
> useful features (preprocessing, presolving, etc.) are not implemented
> yet.
> 

Yes, but besides presolve the LP engine seems to be quite complete, you 
use reasonable startup basis (is it triangular crash ?), Forrest-Tomlin 
basis factorization, ...

> >Commercial solvers use quite some techniques for making MIP perform well, 
> >namely lifted cover cuts, Gomory cuts. According to reports these improved 
> >performance dramatically. Do you think there will be some effort for 
> >making these being part of GLPK ? Would you be able to accept any form of 
> >help implementing these techniques ?
> 
> glpk has a component, which allows generating cutting planes on
> solving mip problems (in particular, the b&b mip solver is implemented
> using that component; however, cutting planes are not used there). So,
> if you are interested in implementing some classes of cutting planes
> (or other things related to mip), please inform me, and I will provide
> you with a necessary information.

Of course, I am interested in implementing Nemhauser's cover cuts. Any  
kind of information is, of course, welcome. Have you any ideas what else 
can be implemented ?

/Rastjo