[Help-glpk] plans for MIP improvements

[Brady Hunsaker]

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

     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".
     I need to read through a few more papers, but hopefully I'll be
working on the code within a week or two.  At that point I'll get a better
sense of whether any changes to the main code are worth considering.  I'll
post again then, 

Brady

----------------
Brady Hunsaker
Georgia Institute of Technology
Program in Algorithms, Combinatorics, and Optimization
School of Industrial and Systems Engineering

E-mail address:   address@hidden