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.
Solver capabilities[edit | edit source]
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.
Independent reviews[edit | edit source]
- Fourer, Robert (2009). "Software survey : linear programming". OR/MS Today. 36 (3): 46–55.
{{cite journal}}: Unknown parameter|month=ignored (help) — available for download (requires registration).
Numerical benchmarks[edit | edit source]
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 suite[edit | edit source]
MIPLIB is a suite of mixed integer test problems from ZIB, currently at version MIPLIB 2003 [1]. 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.
netlib suite[edit | edit source]
The GLPK project routinely benchmarks against the netlib suite from ftp://ftp.netlib.org/lp/data. The latest results are reported in the text file doc/netlib.txt in the official GLPK documentation.
Mittelmann benchmarks[edit | edit source]
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[edit | edit source]
The NEOS Server for Optimization offers a portal for trialling GLPK. Due to the way the portal is organized, problem instances must be submitted in the GAMS language and not in native MathProg. [2]
Code quality[edit | edit source]
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.
Problem/solution metrics[edit | edit source]
Comment: users can post their problem and solution metrics here (this section will migrate to a stand-alone page as demand dictates).
References[edit | edit source]
- ↑ 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.
- ↑ Bob Fourer noted on 01 February 2011 that the University of Wisconsin, who operate NEOS, might well be persuaded to support MathProg as well.