Is it time for a native Julia LP(Simplex) solver?


#21

Maybe SoPlex is an option here. It’s not open-source, but has an academic licence and they code is published. As their main features, they also include:

  • a compile-time option to use 80bit extended (“quad”) precision for numerically difficult LPs,
  • an LP iterative refinement procedure to compute high-precision solution, and
  • routines for an exact rational LU factorization and continued fraction approximations in order to compute exact solutions.

I’m not sure, but I imagine it’s possible (with moderate effort) to use MPFR-style big floats. In any case, the authors might be interested in your instances that have numerical difficulties :slight_smile:


#22

@StefanKarpinski shines a light on the very essence of what I was think but couldn’t express when says:

If you go and look at Clp which is arguably the better open source solver, you will see that most of the code is very low-level code, that Julia would allow to be instead be written at a very high level.

For example, if you look in ClpSolve.cpp you will see it is filled to the brim not with the mathmatical definitions, but with the boiler plate code of dealling with matries and vectors.

Stefan, can you speak to what kind of simplification you have seen for projects that port out of c++. From your award presentation I was inspired to make the following example, but ultimatly I have to believe it is not a fair apples to apples comparison.

I have to believe that the 300x code reduction is not a realistic goal.


#23

There might be a lot of “boilerplate” that comes from supporting relatively generic interfaces (COIN OSI), but I think the actual simplex implementation will be low-level, even in Julia. That is, there is not a lot of reuse of sparse linear algebra, for example, as most of that should be tailored specifically to the task of LP solving.