Benchmarking ALGLIB and other LP solvers

This article provides a benchmark of the ALGLIB linear programming solver and its comparison with other open source LP solvers. See the section contents for an in-depth discussion of ALGLIB's linear programming capabilities.

Solvers tested

The following solvers were chosen for our benchmark:

• ALGLIB interior point method (version 4.0.0) - A sparse interior point method suitable for both LP and QP problems. It is available from multiple programming languages, including C++, C#, Python, Java. The solver has several implementations (a native one written in C and a managed one written in pure C#). This benchmark evaluates the performance of the native implementation.
• HiGHS (version 1.5) - An LP, QP and MIP solver that implements simplex, active set and interior point methods. HiGHS is written in C++ and has multiple bindings for other languages, including C# and Python. The benchmark assesses the default configuration, which uses the interior point method for LP problems.
• CLP solver (COIN-OR LP, version 1.17) - An LP solver written in C++ that implements both primal and dual simplex methods. It also implements a barrier (interior point) method, although it is less mature than the primal/dual simplex. This benchmark evaluates the performance of the dual simplex method.
• GLPK (GNU Linear Programming Kit, version 5.0) - a package for solving LP and MIP problems, written in C. It implements both the primal and dual simplex method as well as the interior point method. This benchmark evaluates the performance of the dual simplex method.
• lp_solve (version 5.5) - a C library for the solution of LP/MIP problems. Implements dual simplex method.

Test problems

For our benchmark we used a set of 90 problems from the NETLIB test suite. Test problems have from several hundreds of variables to several thousands, with the largest problem having N=13525 variables and M=3000 constraints (fit2p problem).

Results

The plot below shows a total running time for each solver on the test suite:

It is clear that the winners (ALGLIB, HiGHS and CLP) show roughly similar results, whilst GLPK is roughly 2x behind, and lp_solve is 3x behind.

This article is licensed for personal use only.