8
$\begingroup$

Which non-textbook variants (primal/dual, revised) and techniques (e.g. steepest-edge) do professional solvers like Xpress, CPLEX, CLP use, to get the best out of the simplex algorithm?

This question is about the Simplex algorithm for LP only, not other parts of software packages (such as presolve and crash)

Improve this question
$\endgroup$
11
  • 6
    $\begingroup$ This question, too, is hard to answer because it is so broad. Commercial solvers use a huge number of techniques to improve the performance of "vanilla" simplex. (Not to mention that many of those techniques are trade secrets.) So, if you want to know something in particular, like "Do commercial solvers use primal or dual simplex?" or "What is the improvement in performance if we use a certain pricing rule?" then ask something like that. But IMO this question is just about as broad as your previous question that was closed. $\endgroup$
    – LarrySnyder610
    Jun 15, 2019 at 0:47
  • 3
    $\begingroup$ It might also help if you provide some context as to why you are asking. Are you writing your own solver? Writing a paper about solvers? Starting to learn about simplex and wondering what theoretical aspects are/aren't important in practice? Context like that will help us give you answers that are useful to you. $\endgroup$
    – LarrySnyder610
    Jun 15, 2019 at 0:48
  • 2
    $\begingroup$ Thank you Larry for asking. I'm a student working on my bachelor thesis. One part of it is giving an overview about modern techniques, variants and algorithms in linear programming (only continuous values, no MILP, ILP, ...). My knowledge in this topic is only fundamental. Another part of my thesis work was to develop a solver for "vanilla" simplex- and interior point affine-scaling-method in 3D. I successfully did that. I already looked into some manuals from professional solvers like LINDO. But many dont give a good insight how they solve lps exactly. Even excel does not do that. $\endgroup$
    – Gehhilfe
    Jun 15, 2019 at 1:21
  • 1
    $\begingroup$ What I want to present in my paper are quick insights on how this tools solve them. How they perform (runtime), maybe some algorithms that are not implemented yet and which instances can be solved in which time (assumption). $\endgroup$
    – Gehhilfe
    Jun 15, 2019 at 1:23
  • 2
    $\begingroup$ Aha, that does provide some useful context. Well first of all, in that case your question sounds like you are asking us to write a section of your thesis, which I'm sure is not what you intended. :) But more to the point, if what you want to know is how certain tools perform -- ask exactly that, about the specific tools you are interested in. If you want to know some algorithms that are in the academic literature but not implemented in commercial solvers, ask that. If you want to know what makes an LP instance easy or hard, ask that. I would suggest that you ask those as separate questions. $\endgroup$
    – LarrySnyder610
    Jun 15, 2019 at 1:25

2 Answers 2

Reset to default
18
$\begingroup$

First of all, usually implementations are centered around the revised dual simplex, not the primal (even though solvers will still use a primal simplex method implementation for some tasks in the solution process).

According to Huangfu and Hall and Koberstein, the most important non-textbook techniques for the dual revised simplex appear to be:

Dual Steepest Edge algorithm for choosing the variable leaving the basis Forrest, Goldfarb: Steepest-edge simplex algorithms for linear programming

Bound Flipping Ratio Test See for example Koberstein

It is based on the observation that the reduced cost value of a boxed non-basic primal variable can be kept dual feasible even if it switches sign by setting the variable it to its opposite bound. This means that the dual step length can be further increased and breakpoints associated with boxed primal variables can be skipped as long as the dual objective function keeps improving

Using LU factorization No solver I know actually inverts the basis matrix to solve the linear systems. Simplex implementations typically compute a (sparse)LU factorization and update it using Forrest-Tomlin updates to avoid too-frequent recomputation of the factorization.

Exploiting Hypersparsity Exploiting the fact that when solving a linear system the right hand side is soemtimes/often sparse. See for example Hall, McKinnon

Exploiting parallelism While the linear algebra in a sparse simplex implementation is not trivial to parallelize, there are some things that can be done to make use of parallel machines. See for example Huangfu, Hall and Hall.

Note that much of the speedup of solvers compared to one another is often due to a better presolve and/or crashstart implementation. I suspect some of the better open-source simplex implementations to not perform much worse than commercial implementations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is very useful. Thank you so much. $\endgroup$
    – Gehhilfe
    Jun 15, 2019 at 16:56
20
$\begingroup$

There is a series of three lectures of Robert Bixby (the Bi in Gurobi) on Solving Linear Programs: The Dual Simplex Algorithm. Have a look at the third part Implementing the algorithm where he talks about many details and tricks for implementing general bounds, finding a feasible basis, pricing, and solving linear systems.

In particular at about 38:00 he explains that there is a single step in solving triangular systems that, when done wrong, takes 99.9% of the solving time in sparse systems, and shows how it can be implemented efficiently.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you Marcus! I've heard of that name before and read and article of him. He seems to be a big fish when he was involved in gurobi and cplex. I will definitely check that out! $\endgroup$
    – Gehhilfe
    Jun 15, 2019 at 1:39
  • $\begingroup$ This trick of exploiting hyper-sparsity is a very important one in the simplex method's armoury, but it doesn't apply to all sparse LP problems. But, when it does, the level of effect that Bixby talked about is observed. $\endgroup$
    – SparseRunner
    Jul 3, 2019 at 18:43
  • $\begingroup$ Any similar materials on implementing algorithms for solving IP ? $\endgroup$
    – Antarctica
    Sep 5, 2019 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.