0
$\begingroup$

I am learning linear programming through the book Introduction to Linear Optimization by Dimitris Bertsimas.

Many of the exercises can be implemented in code. This is an example of such an exercise: (https://i.stack.imgur.com/WzloF.png). Are there any courses or other sources that explain how to implement these algorithms in, for example, Gurobi, or other algorithms such as interior point methods or the ellipsoid algorithm? I want to also gain a more practical understanding of linear programming in addition to a theoretical understanding by reading the textbook.

$\endgroup$
1
  • $\begingroup$ For that particular exercise, the intent seems to be to use a bisection search, but consider also the Charnes-Cooper transformation. $\endgroup$
    – RobPratt
    Oct 3, 2023 at 20:07

1 Answer 1

2
$\begingroup$

Disclaimers:

  • I interpret your question as asking about how to implement LP solving algorithms (the core) and not about how to apply LP technology having access to some LP solver / oracle
  • I'm not a solver developer!

Textbook vs. Real-world

Imho LP (and MIP) technology is heavily lacking textbooks covering state-of-the-art real-world implementations. There is a large difference between theory and practice!

Skimming over the employee lists of the well-known commercial vendors of this kind of software one can see a huge pool of people with a background at the Zuse Institut Berlin (ZIB) which might somewhat indicate how expertise builds up and is transferred. But that's just probably only part of the story.

IPMs

Interior-point solvers are probably much more easy to implement (for real-world purposes) as (at least when not competing with the state of the art like Mosek and co.) the sparse-algebra needed is rather generic-purpose and these routines dominate time-consumption and complexity in implementations: sometimes third-party software is available, e.g. MUMPS, SuperLU; sometimes not (there are more IPM-suited ones depending on the algorithmic core), but literature seems more complete here). There are still other parts less well-covered like matrix-scaling and co.

Simplex

Simplex-style solvers howewer seem way more specialized and factorization-routines don't seem to reappear in other applications (unlike MUMPS and SuperLU).

This doesn't mean that there aren't great resources. But those are scattered. Papers on presolving (also relevant for IPMs) seem rather complete to me. Simplex factorization, pivoting and co. can also be found. Things related to numerical-stability howewer: less transparent.

Source code

At some point, one probably has to read (open-source) code. Good picks are:

  • CoinOR Clp (Cbc) (arguably hardest codebase to read; C++)
    • Contains IPM (2nd class citizen)
  • Soplex (SCIP) (best documentation; ZIB in-house codebase; C)
  • Highs (more modern/smaller codebase; more modern algorithmics; C++)
    • Contains IPM
  • ortools Glop (more modern/smaller codebase; more modern algorithmics: C++)

More modern algorithmics related to (seems to be the core of modern impls dropping original algos of Clp/Soplex; buttake it with a grain of salt):

Huangfu, Qi, and JA Julian Hall. "Parallelizing the dual revised simplex method." Mathematical Programming Computation 10.1 (2018): 119-142.

All of those solvers (ortools being a bit different) extend to MILPs with branch-and-bound-and-price and such.

A more minimal but interesting POC (also giving pointers on whats lacking):

"This is not a textbook implementation and contains some advanced features that are important for practical implementations..."

Textbook recommendations (personal)

IPMs

Wright, Stephen J. Primal-dual interior-point methods. Society for Industrial and Applied Mathematics, 1997.

I wrote a Convex QP solver once surviving well known testsets and this book served as core reference.

Simplex

Maros, István. Computational techniques of the simplex method. Vol. 61. Springer Science & Business Media, 2012.

Only book imho really targeting real-world implementations (but a bit dated). A quote supporting my points in the intro:

"Over the years I was approached by several people asking for advice regarding the implementation of the simplex method. They were complaining that information was scarce and scattered in the literature. Additionally, they were not aware of all the aspects to be considered."

Resources recommended by vendors

IBM/Cplex

Link

Gurobi

Link

$\endgroup$

Your Answer

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

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