Questions on Linear Programming Pivot Algorithms

As part of a final project for my linear programming course, I have been asked to discuss efficient implementations of pivot algorithms, including which combinations of the ideas we have talked about in class this fall are actually implemented. If you find yourself with the time and the ability to share without giving away any proprietary knowledge of yours, could you get back to me on the following questions?

Which pivot algorithms does your software implement for solving LP's? I've seen primal and dual simplex when using your tools in the past. Any others?

I've learned in a previous LP course that revised simplex can greatly improve the efficiency of pivot calculations for LP's. Do you use any variations of revised simplex? If yes, could you share which publicly available variants most closely resemble which you use? Are there any other concepts you use for ensuring pivots are calculated efficiently?

When it comes to deciding how to pivot, we have learned about least ratio and lexicographic minimums for picking new bases as well as Bland's rule for avoiding cycles. Do you use any of these concepts in your software for deciding how to pivot in an LP? If so, could you share which and what publicly available advances to those rules you use? If you don't, could you share what other kinds of pivoting rules and cycle avoidance techniques your software uses?

Beyond selecting and calculating pivots, are there any other concepts you leverage to solve LP's efficiently? I know from my time as an OR scientist before grad school that my colleagues would talk about preprocessing as being a large source of the improvements in which optimization models could be solved by solvers. In your response, could you include the kinds of things you do for preprocessing and if any of them are things that can be done in general for all LP's?

I know you all have many paying customers whom probably keep you quite busy with questions on how your solvers work, so it really means a lot to me that you took the time to read my email and think about the questions I asked.

Sean

Jaromił Najman

Gurobi Staff

December 08, 2020 15:00

This is a cross-post to How Close is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms?

Richard Oberdieck

Hi Sean,

I just saw that you asked a similar set of questions on the OR stackexchange, and already got some good answers e.g. from Mark Stone. I think that will give you a general overview of what we are doing in Gurobi.

Best regards

Richard

Questions on Linear Programming Pivot Algorithms

Comments

Didn't find what you were looking for?