Simplex method for LP

The simplex method is one of the two most often used linear programming algorithms (another popular approach is the interior point method, which is also included in ALGLIB). ALGLIB implements the so-called revised dual simplex method with several essential performance and stability improvements, which are discussed in the sections below.

This article provides a high-level overview of the ALGLIB implementation of the simplex method. It discusses questions like the algorithm's strong and weak sides and its stability and performance properties. The ALGLIB linear programming API is described in this separate article.

Revised dual simplex method

Algorithm

The simplex method is an active set method. Each step of the simplex method deactivates one box constraint and selects another one to be activated (general linear constraints are always satisfied). Typically for an active set method, O(N+M) steps are needed for an N-dimensional problem with M general linear constraints.

The simplex method stops when the solver finds a trial point (uniquely determined by the active set) that is primal/dual feasible. Here, primal feasibility means that the trial point does not violate constraints, and dual feasibility means that there are no descent directions 'leaving' the trial point. A point that is both primal and dual feasible is the solution of the linear programming problem because it is both locally optimal and does not violate constraints.

The primal simplex method starts from a trial point that is primal feasible and iterates until dual feasibility. The dual simplex method starts from a trial point that is dual feasible and iterates until primal feasibility. ALGLIB implements a three-phase dual simplex method with additional degeneracy-breaking perturbation:

• Phase 1 finds the initial dual feasible point by minimizing the sum of the dual infeasibilities of the perturbed linear programming problem
• Phase 2 starts from the dual feasible point and iterates until it finds a point that is both primal and dual feasible
• Phase 3 removes degeneracy-breaking perturbation from the cost vector and performs a few iterations of the primal simplex method to restore dual feasibility

Improvements

Our implementation of the simplex method has following improvements over the 'textbook' version:

• Forrest-Tomlin updates for faster LU refactorizations
• A bound flipping ratio test (also known as long dual step) for longer steps
• Dual steepest edge pricing for better selection of the leaving variable
• Shifting (dynamic perturbations applied to cost vector) for better stability

Comparison with the interior point method

The interior point method, another solver implemented in ALGLIB, solves the linear programming problem by applying Newton's iteration to the linear target function with additional logarithmic barrier terms. The interior point method is, in some sense, dual to the simplex method:

• The simplex method has a very low iteration cost, but it needs about O(N+M) iterations to converge. Contrary to that, the interior point method converges in 10-30 iterations, but the iteration cost is much higher.
• The simplex method returns solutions that 'stick to bounds', i.e., it prefers points located exactly at the boundary of the feasible set. The interior point method, similarly to other barrier methods, returns points that approach bounds from the interior of the feasible region. As result, sometimes the simplex method and the interior point method return slightly different solutions (that still have same target function value).
• Finally, the interior point method is fairly easy to accelerate - the overall algorithm structure is very simple, with most time being spent in sparse Cholesky/LDLT factorization. Contrary to that, the simplex method is a very complex algorithm with data access patterns that are hard to optimize.

Performance aspects

In this section we review various factors that influence simplex method performance.

C++ vs. C#

Simplex method running time depends on whether you work with native ALGLIB (available from C++, C#, Python, and other languages) or its fully managed version (available from C#, VB.NET, and IronPython). The .NET framework has greatly improved over the last few years, but math-intense C/C++ code is still ~2x faster than equivalent fully managed C# code. This difference is mostly explained by the fact that managed code has to check every array access for array bounds violations.

As a result, working with native computational core is preferable. If you use ALGLIB for C++, you are already on the winning side. C# users may find it beneficial to use a C# wrapper around native core (available in the commercial edition). On the other hand, the fully managed version is still well optimized - we tried to achieve the best result possible under constraint of being fully managed.

SIMD and parallelism

The simplex method is notoriously difficult to parallelize and/or accelerate with SIMD. The algorithm is inherently sequential, with many low-cost interdependent steps and irregular memory access patterns. Thus, the ALGLIB implementation of the simplex method has no SIMD/SMP support.

Working with the simplex solver

Linear programming functionality is provided by the minlp subpackage. The minlpstate class provides a common interface for all solvers (simplex method and interior point method) supported by ALGLIB. This interface is described in this separate article, which explains how to specify and solve linear programming problems with ALGLIB.

This article is licensed for personal use only.