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.

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

• Gurobi Staff

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:

Simplex:

Istvan Maros: Computational Techniques of the Simplex Method

Achim Koberstein: The dual simplex method, techniques for a fast and stable implementation

- Riley

Hi Yuzhou,

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

- 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.