8

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)

Michael Feldmeier
  • 2,856
  • 14
  • 40
Gehhilfe
  • 453
  • 3
  • 6
  • 6
    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. – LarrySnyder610 Jun 15 '19 at 00:47
  • 3
    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. – LarrySnyder610 Jun 15 '19 at 00:48
  • 2
    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. – Gehhilfe Jun 15 '19 at 01:21
  • 1
    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). – Gehhilfe Jun 15 '19 at 01:23
  • 2
    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. – LarrySnyder610 Jun 15 '19 at 01:25
  • This question is a bit better than the last one, which was extremely broad, since it is limited to linear programming; but the number of techniques is still broad, so I'm not sure if we will get a good, focused set of answers without narrowing the scope. – Marcus Ritt Jun 15 '19 at 01:32
  • Okay thank you for your input. @LarrySnyder610 – Gehhilfe Jun 15 '19 at 01:32
  • 1
    Presolve is not part of the Simplex algorithm per se, but is extremely important to solver performance on real problems. – Mark L. Stone Jun 15 '19 at 02:09
  • 1
    @Gehhilfe I reworded the question a bit. If this is not what you meant, feel free to revert. As such I think the question is answerable. Of course commercial solvers will include trade secrets, but I don't think the simplex-part of commercial solvers is much different than in very good open-source solvers. I believe in the end the differences in performances comes mostly down to presolve and crashstart. – Michael Feldmeier Jun 15 '19 at 07:20
  • @LarrySnyder610 Why do people keep closing questions as too broad after they have been answered? Then we have to go through this nonsensical process of trying to get enough reopen votes for it to be reopened. Only then in some cases for it to be closed yet again. As has been done here, these supposedly overly boroaf question can often be answered with structured references to the literature. Those are valid answers in my opinion.even if the detailed answer is not written out in the answer itself. Yes, some close votes were prior to editing of the question, but at least one was after. – Mark L. Stone Jun 15 '19 at 10:09
  • 1
    @MarkL.Stone Is your question/objection about this question itself or about the general philosophy of close/open-votes? If the latter, would you post your question on Meta? I think that's the right place to have a conversation about how the community wants to handle open/close votes, as opposed to in the comments of a particular question. I'd like to hear others' opinions about your question, and that's more likely to happen on Meta. – LarrySnyder610 Jun 15 '19 at 12:14

2 Answers2

20

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.

Marcus Ritt
  • 2,715
  • 13
  • 35
  • 1
    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! – Gehhilfe Jun 15 '19 at 01:39
  • 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. – SparseRunner Jul 03 '19 at 18:43
  • Any similar materials on implementing algorithms for solving IP ? – Antarctica Sep 05 '19 at 10:57
18

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.

Michael Feldmeier
  • 2,856
  • 14
  • 40