An detailed explanation of the algorithm Gurobi uses to solve LP and IP

Answered

Yuzhou Jiang

• April 04, 2024 17:36

Hi there,

This is a general question. What are the algorithms Gurobi uses to solve LP and IP? Are there resources available that I can read? I am looking for a more detailed explanation.

Thanks,

Yuzhou

0

• 

  Michel Soares

  • April 05, 2024 17:32

  

  

  Hi Yuzhou,

  I would suggest you start by studying the Simplex Algorithm followed by Interior Point Method, for LPs. For MIP/IP you should start by studying the Branch and Cut algorithm.

  You can start by looking in the the wikipedia pages and look for more in-depth material as you progress.

  Gurobi uses these algorithms as a basis, but with more complicated implementations and auxiliary heuristics.

  0
• 

  Yuzhou Jiang

  • April 07, 2024 00:29

  

  

  

  Hi Michel,

  Thanks for these info. I am an OR professional so I am aware of these methods you mentioned. What you provide is a rather general statement and what I am looking for is materials that are more advanced-OR-graduates-facing. For example, what does pre-solve do? How do Simplex Algorithm and Interior Point Method work together? And further, I am more interested in the "complicated implementations and auxiliary hueristics" you mentioned. I am not sure if this is too much for ask, but if Gurobi has this type of resource available publicly, I'd happy to be directly learn from it. 

  Thanks so much,

  Yuzhou

  0
• 

  Riley Clement

  Gurobi Staff

  • April 07, 2024 08:09

  Hi Yuzhou,

  I'd first take a look at our Advanced Algorithms webinar recording.  Some of it you may be familiar with, some of it may be new.  You may also find some interesting material if you trawl through our YouTube channel.

  Then for more advanced material you will need to consult text books and scientific literature.

  For example,

  Presolve:

  Savelsbergh, Martin WP. "Preprocessing and probing techniques for mixed integer programming problems." ORSA Journal on Computing 6.4 (1994): 445-454.

  Achterberg, Tobias, et al. "Presolve reductions in mixed integer programming." INFORMS Journal on Computing 32.2 (2020): 473-506.

  Interior point methods:

  A Mathematical View of Interior-Point Methods in Convex Optimization - James Renegar
  
  Primal-Dual Interior-Point Methods- Stephen J. Wright

  Simplex:

  Istvan Maros: Computational Techniques of the Simplex Method
  
  Achim Koberstein: The dual simplex method, techniques for a fast and stable implementation

  - Riley

   

   

   

   

  0
• 

  Michel Soares

  • April 07, 2024 10:46

  

  

  Hi Yuzhou,

  Besides the material Riley provided, there a few other points that are really important in MIP, which might be worth looking at:

  - Branching rules: Achterberg, Tobias, Thorsten Koch, and Alexander Martin. "Branching rules revisited." Operations Research Letters 33.1 (2005): 42-54.

  - Cuts:I do not know of any paper that explains them all in details, but you refer to Gurobi's parameter page and see the available MIP Cuts from the parameters. Most, if not all them, you should be able to find details on the what the yare and implementations.

  - Heuristics: again, I do not know a Gurobi resource covering all the heuristics used, but you should be able to find material on this on the internet, looking for "mip heuristics" or "matheuristics".

  Finally, there are a lot papers published by the Gurobi team over the years, unfortunately most are quite old, but you can always lookup the team's name and read their papers. You may also look into what was published by other solvers, specially CPLEX on the past, since Gurobi's team came from it, and SCIP, since Tobias Achterberg came from its team.

  0

Please sign in to leave a comment.