How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms

Question

As part of a final project for my linear programming course, I have been asked to discuss implementations of pivot algorithms, including which combinations of the ideas we have talked about in class this fall are actually used by available solvers today. Would someone be able to answer or point me to resources on the following questions?

From my work so far with optimization solvers, I see primal and dual simplex seem to be the two pivot algorithms implemented. Do any commonly used solvers implement any others?

I've learned in a previous LP course that revised simplex can greatly improve the efficiency of pivot calculations for LP's. Is revised simplex commonly used within today's solvers? If so, is there any specific variants of it that are most popular? If it isn't used, are there any other methods of calculating pivots employed?

When it comes to deciding how to pivot, we have learned about least ratios and lexicographic minimums for picking new bases as well as Bland's rule for avoiding cycles. Are these concepts still relevant for today's solvers, and if so are there any specific variants that are most popular? If not, what other kinds of pivoting rules and cycle avoidance techniques are common?

I know from my time working with OR scientists before grad school that my colleagues would talk about preprocessing as being a significant source of the improvements in which optimization models could be solved by solvers. What kinds of things are done for preprocessing and can any of them be done in general for all LP's? Is there anything in addition to preprocessing that solvers do outside of selecting and calculating pivots that help solve performance?

Answer 1

There was an excellent lecture by Bob Bixby in 2015 at the Zuse Institute Berlin (ZIB) as part of Combinatorial Optimization at Work 2015. Bixby founded CPLEX and Gurobi, 2 of the 3 leading commercial MILP+ solvers.

The lecture is divided into 3 videos, and gives the actual nitty gritty about what makes LP Simplex family solvers work effectively on large-scale problems. The lecture covers pricing, why dual Simplex is usually better than primal Simplex, and the advances made in efficiently doing sparse linear algebra in these algorithms. I think this will answer your questions.

Robert Bixby: Solving Linear Programs: The Dual Simplex Algorithm (1/3): Some Basic Theory

Robert Bixby: Solving Linear Programs: The Dual Simplex Algorithm (2/3): The Dual Simplex Algorithm

Robert Bixby: Solving Linear Programs: The Dual Simplex Algorithm (3/3): Implementing the Algorithm

Answer 2

One of the best resource I know is the series of lectures on linear programming that was part of the CO@work workshop 2020. I especially recommend the lectures by Bob Bixby (he is the "bi" in "Gurobi"). They are freely available here, and you'll find some theoretical and practical viewpoints.

As for presolving: it is fundamental for MIP, and very important even for LP. In a nutshell, presolve removes elementary redundancies (like a constraint $x = 1$ or duplicate variables), reduces problem size and improves numerics. In this direction, you can have a look at the "Presolving" and "Learning to scale" lectures from CO@work. If you are into academic papers, these two references pretty much cover LP presolve:

• Andersen & Andersen, Presolving in linear programming
• Gondzio, Presolve analysis prior to applying an interior-point method

Answer 3

The videos linked in the other answers contain some of what I will write here but both my writing and the videos are still only scratching on the surface of actual simplex implementations. I'll try to directly answer the questions here:

1. Dual simplex is the most important simplex algorithm right now (because of its performance when solving LPs and because of its warm starting capabilities in the context of mixed integer programming solvers and branch-and-cut). Network simplex can be a superior choice for instances where it applies. Crossover simplex is needed to get a basic solution from an IPM solver or any other method that returns a not necessarily basic solution to LPs. To the best of my knowledge no commercial solver uses a true criss-cross method (except maybe in the context of a phase 1).

2. The revised simplex is what is used but the important part are the details. A (hyper-) sparse LU Update method to solve the linear systems is very important for good performance, see the thesis by Achim Koberstein for some details on that. The thesis also contains information about the bound flipping ratio test (long step method) that was skipped in the Bixby-Videos and has some importance for dual simplex. The Harris ratio test is also very important for a fast and stable simplex implementation.

3. The pivoting rules typically discussed in class are not efficient in practice. As far as I can say all solvers use some form of (projected) steepest-edge pricing or approximations thereof (like DEVEX). Especially for dual simplex, steepest edge pricing, if implemented efficiently, is hard to beat.

4. As far as I can say all solvers use some form of perturbation to avoid cycling. There are many details to think about, but in the end its pretty much what Bixby says in his videos. Its not very fancy but works great.

5. Presolve (or preprocessing) is much more important for mixed integer programming solvers than for LP solvers. The basic techniques pointed out in references here are typically applied, but don't change the performance all that dramatically. That said, there are some techniques that can dramatically change how fast an instance is solved. Three things come directly to mind:

   • Removing dependent rows: mostly for IPMs and is done using a simplex type algorithm itself
   • Dualizing the problem: if a problem has many more rows than columns, solve the dual.
   • LP folding: removing a form of symmetry from LPs at the cost of potentially having to do a crossover at the end (Grohe et al., 2014: Dimension Reduction via Colour Refinement).