Re: [Help-glpk] plans for MIP improvements

[Andrew Makhorin]

>Hi,
>     I just wanted to give a brief update on my plans for improving the
>MIP solver.  This is mainly for Andrew, but I guess it might be of
>interest to anyone else who's listening (if there is anyone else).
>     I've been looking over the literature as well as examining lp_solve
>and bonsaiG.  As you said, lp_solve's branch-and-bound seems pretty
>rudimentary and not well documented either.  bonsaiG has some good
>ideas, but nothing extraordinary.  The main strength seems to be the use
>of "Arc Consistency", a phrase that comes from a related field (maybe
>constraint programming?), but in this implementation seems to pretty much
>mean aggressive bound tightening at each node.  A good preprocessing
>function should do the same and more.

It is interesting to note that although the current version of glpk mip
solver uses an easy branching heuristic, it contrives to successfully
solve some test problems from miplib faster than bonsaiG. See some
benchmarks at <ftp://plato.la.asu.edu/pub/milpf.txt>; these benchmarks
were obtained by Prof. Hans Mittelmann. Besides, there are also
benchmarks on his website at <http://plato.la.asu.edu/bench.html> for
most widely known commercial mip solvers.

>     It now seems to me that there isn't really any free software MIP
>solver out there that incorporates all the main ideas available in the
>current literature.
>     What I expect to work on first are
>      - heuristics to try to quickly find a good feasible solution at the
>root node
>      - preprocessing that will include bound tightening, coefficient
>reduction, logical implications, and (eventually) probing
>      - examination of branching strategy and backtracking (though you may
>already have the best documented defaults)

Most probably, introducing improved bounds and additional constraints
will give the desired effect even for the branching heuristic currently
used. (Dr. Lou Hafer, the author of bonsaiG, told me that his package
also needs cutting planes to make progress on the mip side.)

>     I think these enhancements should provide the biggest change in the
>size of the b&b tree.  The next change will probably be to add some
>cutting plane routines. Most of these changes may fit naturally, though we
>may want to consider adding "binary" as a separate variable type in
>addition to "integer".

It seems to me that there is no need to additionally introduce binary
variables. If you need to check if some structural integer variable is
binary, you can see at its type and bounds: if its type is 'D' (double
bounded), lower bound is 0.0, and upper bound is 1.0, it is of binary
kind. This check is reliable, because bounds of integer variables are
integer floating-point numbers and therefore not deformed by round-off
errors.

Andrew Makhorin