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[edit | edit source]
BAK is a tool for analyzing the branch-and-bound behavior of GLPK and other solvers. [1] [2] 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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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).[3] For an air traffic control application, see Rios and Ross (2010).[4]
References[edit | edit source]
- ↑ 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.