Re: [Help-glpk] want to contribute

[Andrew Makhorin]

>                       I'll start getting familiar with the
>branch-and-bound code to see what I can add.

Great! Unfortunately, GLPK branch-and-bound routines are not documented
yet (they are "raw", so I decided to document them later, when they will
be well-tried). However, I hope that a lot of comments will help you to
understand with source code. The following files are related to B&B:

glpmip.h                B&B header (contains all B&B data structures);

glpmip/mip1_driver.c    B&B driver routine (it is called from API
                        routine glp_integer);

glpmip/branch_first.c   branch heuristic routines; they can be used as
glpmip/branch_last.c    examples;
glpmip/branch_drtom.c

Note that B&B driver routine exploits a set of routines that implement
components of the revised simplex method (glprsm.h, glprsm/*.c; see also
the document "GLPK Implementation of the Revised Simplex Method" in the
distribution).

If you will have any questions or need an additional information about
GLPK components, please contact me.

>    What is your preference on consulting other GPL code?  For example,
>bonsaiG (GPL) and lp-solve (LGPL) both have branch-and-bound.  In addition
>to consulting the literature, I could take a look at what those codes do.
>It seems to me that they're resources we might as well take advantage of,
>unless there's a reason to build up everything "from scratch".  What do
>you think?

I'm familiar with lp-solve (it is included in Debian GNU/Linux CDs).
Its LP part is based on eta file and "textbook" pricing and pivoting
(plus perturbation to prevent cycling). Branch heuristics are trivial
(branching on the first variable and random branching). GLPK beats it.

bonsaiG is much more interesting. Unfortunately, I found no benchmarks
for pure LP, however, benchmarks for MIP are imposing. I think that
consulting its code is a good idea.

Andrew Makhorin