[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Re: The GLPK questions
From: |
Rastislav Galia |
Subject: |
[Help-glpk] Re: The GLPK questions |
Date: |
Mon, 3 Feb 2003 13:42:38 +0100 (CET) |
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