Linear programming

The ALGLIB numerical library includes an efficient, large-scale LP solver available in C++, C# and other .NET languages, Python, and Delphi/FreePascal. The solver is dual-licensed, with free and commercial editions.

This article provides a high-level overview of ALGLIB linear programming functionality. See other articles in this section for an in-depth discussion:

• Working with LP solver
• Linear programming tips and tricks
• Simplex method
• Interior point method
• Benchmarking ALGLIB and other LP solvers

LP solver overview

Design goals

ALGLIB LP solver design goals include:

• Performance. The solver utilizes the latest SIMD instruction sets and other acceleration methods.
• Robustness. The solver reliably handles degenerate problems and performs internal integrity checks during its functioning.
• Scalability to large-scale problems. The solver can handle problems with over a million variables.
• Good handling of small-scale cases. Asymptotically good code also has low overhead for small-scale tasks (100-1,000 variables).
• Suitability for long-running industrial applications. The solver reduces memory fragmentation (when used from C++) and GC pressure (when used from C#) under a "long running code, constant stream of tasks" scenario. Both the amount of memory allocated and the allocations count are reduced; already allocated memory is reused as much as possible.

Algorithms

ALGLIB LP solver supports the most general formulation of linear programming problems: any mix of bounded, ranged, fixed or free variables with equality, inequality, or ranged linear constraints. It does not require you to manually convert input problem into a nonnegatively constrained form via the addition of slack variables.

Note #1
An important feature of the library is that it can very efficiently handle difficult cases, such as two-sided (range) linear constraints or free variables. Some solvers replace two-sided linear constraints with a pair of one-sided constraints (with similar transformations performed for free variables), thus incurring a huge performance penalty. By contrast, ALGLIB LP solver has no additional performance penalties in such cases.

The library includes two linear programming algorithms with common API:

• revised dual simplex method
• interior-point method (default option, recommended).

We recommend IPM over the simplex method for several reasons. First, IPM is much easier to accelerate with parallelism or SIMD than the simplex. The simplex method has very complex internal logic with irregular data access patterns that are hard to optimize. On the other hand, the interior-point method has a fairly straightforward structure, with most time being spent in the sparse symmetric linear solver.

Second, the simplex method scales badly with problem size growth. Being an active set method, it requires O(N+M) iterations to solve a problem with N variables and M constraints. Thus, a problem with 1,000,000 variables will need about 1,000,000 iterations, regardless of its properties. The interior point method has been demonstrated to show better empirical asymptotic behavior.

Benchmarks

Our LP benchmark compares the performance of the ALGLIB LP solver with other open source libraries. The short summary is that ALGLIB is on par with the best open source solvers available!

LP software library structure

The ALGLIB LP solver is available in multiple programming languages, including C++, C#, and Python. Most numerical libraries have their core functionality implemented in just one programming language (e.g., C++ or C#), using wrappers to access it from other programming languages. ALGLIB, however, has independent C/C++ and .NET backends with 100% identical functionality.

Using the LP solver from C++, Python, and FreePascal/Delphi

ALGLIB for C++ is a C/C++ numerical library with optional Python and FreePascal/Delphi wrappers. It is a highly portable library that can be compiled in a Windows or Linux environment (or any other POSIX system). It will work under any CPU capable of supporting double-precision math, including x86, x64, ARM, and RISC-V.

The library itself is implemented using plain C/C++ for the best portability across compilers, processors, and systems. However, it also includes SIMD-capable kernels for performance-critical parts. In particular, the interior point LP solver (its sparse linear algebra part) is very efficiently accelerated with SIMD.

Using the LP solver from C#

The .NET version of ALGLIB is a C# interface (with optional IronPython and VB.NET wrappers) that can connect to several backends.

The first and most important backend is a pure C# implementation. When compiled with ALGLIB_USE_SIMD #defined, ALGLIB can utilize the SIMD intrinsics introduced in recent .NET releases (.NET Core 3+, .NET 5+). SIMD support greatly increases the performance of the interior-point method, making it comparable to that of the C/C++ implementation. When compiled without SIMD, ALGLIB is a fully managed assembly compatible with any .NET version released since .NET Framework 2.0.

Alternatively, C# users may work with the C# wrapper around a precompiled C/C++ native library (the so-called HPC core, available under Windows and Linux). The HPC core can be used with any .NET version released since .NET Framework 2.0. It provides the best performance at the cost of moving a precompiled native binary along with your app.