GLPK/Reviews and benchmarks
Independent reviews and numerical benchmarks are an important part of any optimization solver project. This page lists some independent assessments of GLPK and attempts to give an indication of where GLPK might normally excel.
GLPK is free software — which may be an advantage or disadvantage depending on your needs and views. Access to the source code allows researchers, in particular, to modify GLPK to suit their needs and to later submit their improvements back to the GLPK maintainer for possible inclusion.
GLPK is unable to match the performance (or price) of the top commercial solvers for very-large scale instances. To give just one example, CPLEX can be expected to be 10–100× faster for dual simplex problems. More specific comparisons can be made by reviewing a selection of the current benchmarking surveys.
The GLPK solver offers the following methods and features:
- the revised simplex and primal-dual interior-point methods for non-integer problems
- the branch-and-bound algorithm together with Gomory's mixed integer cuts for integer and mixed integer problems
- a selection of graph theory routines for graph, flow network, and critical path problems
- inclusion of the MiniSat solver for boolean satisfiability problems
- support for arbitrary-precision arithmetic
- support for ODBC connectivity to interface with relational databases and spreadsheets.
All features, except the graph routines, are available through the GLPSOL command-line utility.
The number of variables and constraints is not specifically limited by GLPK. Large or hard problems may, of course, exceed the available memory or fail to solve in a reasonable time.
- Fourer, Robert (June 2009). "Software survey : linear programming". OR/MS Today 36 (3): 46-55. — available for download (requires registration).
Benchmark tests are deliberately challenging and do not necessarily represent the kinds of problems that users wish to solve.
The official GLPK benchmark results are not posted here in order to avoid the inevitable maintenance delay. They are instead included as part of the official GLPK documentation. In contrast, the Mittelmann benchmarks can be viewed directly — while noting that some aspects of GLPK functionality, including the graph theory routines, are not covered by Mittelmann.
MIPLIB is a suite of mixed integer test problems from ZIB, currently at version MIPLIB 2003 . The GLPK project routinely benchmarks against test sets 2.0 and 3.0 of this test suite. The latest results are reported in the text files doc/miplib2.txt and doc/miplib3.txt in the official GLPK documentation.
Hans Mittelmann from the School of Math & Stats, Arizona State University maintains a benchmarking site at plato.asu.edu/bench.html. Although GLPK is not listed on the start page, it is included in the appropriate test categories. The benchmarks are conducted using the NEOS server. GLPK features in the following test suites:
- plato.asu.edu/ftp/lpfree.html — linear program tests for serial (single threaded) solvers
- plato.asu.edu/ftp/milpf.html — mixed integer linear program tests for serial (single threaded) solvers.
Problem size metrics are included with the test results.
NEOS server portal
The GLPK project does not undertake formal code reviews. However users sometimes post unsolicited comments to the GLPK mailing lists. For instance:
"Many thanks to all for such a first class package. The code is some of the best, if not the best, I've ever seen. I've been sole support for several million lines of other people's code over the years. So it's a real treat to see something so well written." Source: GLPK help list, 13 January 2011.
Comment: users can post their problem and solution metrics here (this section will migrate to a stand-alone page as demand dictates).
- Achterberg, Tobias; Koch, Thorsten; Martin, Alexander (2006). "MIPLIB 2003". Operations Research Letters (Elsevier) 34 (4): 1-12. doi:10.1016/j.orl.2005.07.00. http://www.zib.de/Publications/abstracts/ZR-05-28.
- Bob Fourer noted on 01 February 2011 that the University of Wisconsin, who operate NEOS, might well be persuaded to support MathProg as well.