BonsaiG

This is the terminal source distribution for bonsaiG, a mixed-integer linear programming code, last updated November 10, 2004. Probably the single biggest improvement is the elimination of all Fortran, thanks to Andrew Makhorin and the basis code from GLPK).

BonsaiG is no longer under active development: I'm heavily involved with the COIN-OR project, which has its own MILP solver, cbc. Unless you have some compelling reason for using bonsaiG (e.g., interest in some of its less common algorithms), I strongly recommend you try cbc.

bonsaiG was developed as a research code, and as such it's primarily written to be useful to me for algorithm development. But it may well be useful to you, too, and that's one of my motivations for keeping it available. The second motivation is to repay my debt to others: The opportunity to work with the sources of the early MILP codes BandBX and Zoom/XMP was invaluable to me. By making the source of bonsaiG available (and more recently, through working with the COIN-OR project), I hope to provide a similar opportunity to others.

To keep bonsaiG accessible to the public at large, it's offered to you under the terms of the Free Software Foundation General Public License (popularly known as `copyleft').

As a research code, bonsaiG is built more for flexibility and robustness than for speed. Compiled with full debugging capabilities (the default build), it's downright paranoid and can tell you far more than you'll ever want to know about what it's doing while it solves your MILP problem. Compiled with full optimisation, it's decently fast, but if you want real speed, check out cbc. If you have money, buy a commercial code.

bonsaiG accepts problems in MPS format, and writes output in a form that's reasonably human-readable but conforms to no particular standard.

bonsaiG was developed on a Sun workstation running the Solaris operating system, using the Sun Workshop compilers and programming environment. The source distribution offered in the last paragraph below (code and makefiles) should work for Solaris/Workshop or Linux/GCC.

Thanks to Hans Mittelmann for his assistance (and a little prodding) on initial ports of bonsaiG. We also ported bonsaiG to run on an HP system, and a subsequent user reported success on an Alpha/Open VMS platform. These configurations are not explicitly supported in the distribution, but you can likely figure out how it works from the README and the source.

In general, bonsaiG should not be particularly difficult to port to any environment which supports ANSI C and IEEE floating point. I don't have access to a wide selection of configurations (or time to play with them, for that matter), so about all the help I can offer you in determining how to port bonsaiG to your particular computing environment is clarification on why the code uses a particular construct and advice on common problems. Typically, the biggest problems are with the use of IEEE infinity and NaN, big-endian vs. little-endian representation, and the availability of supporting functions.

I categorically refuse to provide any assistance whatsoever in making bonsaiG run under any flavour of Windows. Don't bother to ask --- try the COIN-OR code instead. Better yet, get a decent operating system.

If you find bugs in the code, well, see the opening comments about COIN-OR and cbc. If you're desperate, send me email; if it's sufficiently interesting I may be able to offer you some advice for debugging.

Looking for test cases to see if you've built the code properly? Try the MIPLIB 3.0 problems. p0033 or flugpl are two of the smallest and easiest. I've included them, along with example .spc files used to control bonsaiG, in the Examples directory in the distribution.

If you want to read a bit about the code before downloading the distribution, the tech report "bonsaiG: Algorithms and Design", while sorely out-of-date, describes the algorithms and gives performance data for bonsaiG on the MIPLIB 3.0 set. Other files in the documentation directory (equally out-of-date) are a user's manual for bonsaiG and technical reports describing the dylp LP code and the consys constraint system package.

The source distribution is a gzip'ed tar file; most likely your browser will unzip it for you, leaving you with the tar file. The gzip'ed file is about 1MB, and unzips to a tar file of about 4.5MB. It includes all necessary source (bonsaiG, dylp, and various library packages), makefiles, and the documentation and examples mentioned above. It's fronted by a request for your name and email address, which I hope you'll provide. It gives me a little documentation when I'm asked to justify the time I've spent on this.

Lou Hafer
lou@cs.sfu.ca
November 10, 2004