GLPK/Add-Ons

This page describes "add-ons" to GLPK — including unofficial extensions to the GLPK codebase to provide some special functionality. As such, these extensions require a suitable compilation environment.

BAK: branch-and-bound analysis kit

Branch and bound tree generated with BAK and rendered with gnuplot

BAK is a tool for analyzing the branch-and-bound behavior of GLPK and other solvers. BAK is distributed with a GPL 2.0 license and a CPL 1.0 license — the choice of which to employ is left to the user.

Adding BAK to GLPK

The latest BAK version can be downloaded with

svn checkout https://projects.coin-or.org/svn/CoinBazaar/projects/BAK

The source can be viewed at https://projects.coin-or.org/CoinBazaar/browser/projects/BAK/.

BAK comes with some patched source files for GLPK in the directory bak/interfaces/GLPK. First copy these files to the normal GLPK source directory and then rebuild GLPK afresh (see chapter Compiling GLPK).

Usage

The modified standalone solver GLPSOL writes a file with branching information. The name of this file is specified using command-line option --bakfile, for example:

glpsol --bakfile tsp.bak -m tsp.mod

The file contains information about the nodes created, the branching process, the integer infeasabilities encountered, and the run-time progress. The file format is documented at [1]. As an example, this file might start with the following lines.

#SOLVER: GLPK
#PROBLEM: (null)
0.002000 branched 1 0 M 6030.000000 6.466667 32
0.002000 candidate 2 1 L
0.002000 candidate 3 1 R
0.004000 branched 2 1 L 6030.000000 6.466667 30
0.004000 candidate 4 2 L
0.004000 candidate 5 2 R
0.006000 branched 4 2 L 6069.000000 7.533333 32
0.006000 candidate 6 4 L
0.006000 candidate 7 4 R
0.008000 branched 7 4 R 6069.000000 7.266667 30
0.008000 candidate 8 7 L
0.008000 candidate 9 7 R
0.009000 infeasible 9 7 R
...

A python script can be used to create intermediate files for visualizing this information with gnuplot:

python bak/BAK_visual.py --all tsp.bak

The resultant files can be viewed with a PNG file viewer, for instance evince:

evince tree_alt.004.png

Dantzig-Wolfe decomposition

Dantzig-Wolfe decomposition is a technique for splitting a suitably structured LP problem into subproblems — and then solving these separately and usually in parallel. The underlying constraint matrix needs a certain form of block structure. The technique, first proposed in 1960, is attracting renewed interest, given the advent of inexpensive multi-core personal computers.

The Dantzig-Wolfe Solver project, now hosted at SourceForge, provides a general, parallel implementation of Dantzig-Wolfe using GLPK. The code was authored by Joey Rios. The first public release, version 1.0, was uploaded on 15 October 2010.

This implementation uses the Pthreads thread management library. Small modifications to GLPK were necessary to allow it to run concurrently. As a result, GLPK in its entirety is included in the Dantzig-Wolfe Solver project codebase. Aside from Pthreads, no other specialist libraries are required.

The code has been successfully built on Mac OS X 10.5 and 10.6, Red Hat Enterprise Linux, and Windows XP via cygwin.

The author hopes this tool will provide a starting point for further research into Dantzig-Wolfe decomposition. Indeed, while many papers across several domains have taken advantage of DW, this is possibly the only project that offers DW source code for open testing and development.

The software has some limitations. As at October 2010, only LP formulations can be used and the subproblems must be bounded. There may also be bugs.

The modeler provides CPLEX LP input files for the master problem and each of the subproblems. A simple guide file, that tells a command-line tool where everything is, also required. The codebase contains several DW examples taken from textbooks and websites or developed by the author.

For an assessment of Dantzig-Wolfe decomposition in general and under parallel computation, see Tebboth (2001). For an air traffic control application, see Rios and Ross (2010).