# 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

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
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:
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 . As an example, this file might start with the following lines.
A python script can be used to create intermediate files for visualizing this information with gnuplot:
The resultant files can be viewed with a PNG file viewer, for instance evince:

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

## References

* ↑ Hunsaker, Brady. "Branch-and-bound Analysis Kit (BAK)". {{cite journal}}: Cite journal requires |journal= (help)
* ↑ Ozaltin, Osman Y.; Hunsaker, Brady; Ralphs, Ted K. (2007). "Visualizing branch-and-bound algorithms" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
* ↑ Tebboth, James Richard (2001). A computational study of Dantzig-Wolfe decomposition (PDF) (PhD thesis). University of Buckingham, United Kingdom.
* ↑ Rios, Joseph; Ross, Kevin (2010). "Massively parallel Dantzig-Wolfe decomposition applied to traffic flow scheduling" (PDF). Journal of Aerospace Computing, Information, and Communication. 7 (1): 32–45.