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

Specific Domains Optimization (Mathematical)
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:

1 Like
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.
https://github.com/coin-or/Clp/blob/master/Clp/src/ClpSolve.cpp

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.

24

Hello everyone,

Sorry for being one year late to this conversation, back then I did not know this even existed :slight_smile:

I share the view of the mayority of you that having a better open source linear solver option in the Julia world should be a priority.

Considering the two options mentioned above I would rather prioritize improving wrappers of existing open source solvers, than developing anything from scratch. If developing something good from scratch would be easy, the commertial solver business would have shut down long time ago.

Only after improving the wrapper to the last performance drop, and being sure a Julia native solver can offer big enough benefits against the open source c++ coded solver would I dedicate any effort in developing a new solver in Julia.

Currently I am stuck looking for solver alternatives, all options I have seen have sizeable problems either:

  1. Costs are prohibitive for large scale parallel computing

  2. Poor performance and stability

There is one truly open source solver with decent performance for which a Julia wrapper exists (Clp), however, the integration in Julia has much room for improvement. The same problem takes 8 seconds with Cbc.jl and 400 seconds with Clp.jl, as many problems need dual variables Cbc is not always an option…

I have gathered some ideas of what could be changed in the wrapper. Let me list these ideas and share them with you:

Idea 1: The performance drop may be due to the wrapper using add_row and/or add_column (see: Obtaining duals for LP on Cbc - Clp's performance lagging · Issue #301 · coin-or/Cbc · GitHub)

Idea 2: The copy_to method can also be improved (Cbc and Clp performance - #16 by Diego)

Idea 3: Part of the code of Cbc.jl could be reused to improve Clp.jl

Do you have any other idea on how to improve the performance of Clp.jl? What would the time savings of that idea be? What about the implementation effort? What about the savings and the costs of ideas 1 to 3?

Thank you!!

25

I think that there is also a lot of hope in the open-source community for the HiGHS solver, for which a Julia/MOI wrapper is being developed: HiGHS.jl

1 Like
26

Wouldn’t a well tuned and optimized (With all Julia’s great array machinery) solver based on the ADMM framework be able to be competitive with commercial solvers for LP?

Julia has an official interface to the QSQP Project, but probably writing something like QSQP in Julia will yield even more efficient solver which might be even competitive for LP (I wish we could get also the C code generator).

They were able to beat commercial solvers quite easily. Though they show Quadratic Programming problems and not Linear Programming. But maybe the ADMM with optimization targeting LP specifically can achieve similar results.

2 Likes
27

Well, there is a difference between solving “only” a single LP by itself, or solving a sequence of (very similar) LPs in the context of branch-and-bound for MIP. For the first case, an interior point algorithm (e.g. Tulip.jl is appropriate to implement from scratch. For the second case, an implementation of dual simplex is preferred, which makes uses of very specific linear algebra operations for very sparse data.

Personally, I believe that the main benefit of a pure Julia implementation would be the use of number types different from Float64, that is, generic algorithms.

1 Like
28

COSMO.jl is a pure-julia ADMM-based solver for linear and quadradic conic optimization.

That being said, comparing performance is easier said than done. ADMM-based methods are first-order methods: they’re great to get to reach modest accuracy fast, not so much to get high-quality solutions. They also require some tuning to be highly performant.

3 Likes
29

I can see it is developed by the same team as QSQP.
Doe sit have the same optimizations?

As in QSQP Benchmark they compare the performance in High Accuracy mode and beat those commercial solvers.

31

I share the view of the majority of you that having a better open source linear solver option in the Julia world should be a priority.

Importantly, a priority for whom?

For a large majority of users (I’m not afraid to say at least 80-90% of practitioners), what’s needed is a convenient way to build an optimization model, solve it and get a solution. You don’t need a Julia-based solver for that, you need a robust solver that you can call from Julia. In addition, since you likely won’t peek at the code, you don’t need it to be open-source either. Maybe you do want to be able to use it for free though (BTW, most commercial solvers offer free, unrestricted academic licenses).

Therefore, I believe the needs of these 80-90% of users are best served by packages such as JuMP.jl, Convex.jl and the underlying MathOptInterface.jl and solver wrappers.

As for justifying the existence of a Julia-based solver, the main reasons for having coded Tulip.jl in Julia are the following:

  • It was straightforward to handle arbitrary arithmetic. For instance, using Float128 rather than Float64 arithmetic requires 0 change in the source code, while the user simply declares Model{Float128}() instead of Model{Float64}().
  • It was also straightforward to implement specialized linear algebra. Specifically, it took me 264 loc to implement a specialized block-angular matrix type + factorization routines and to interface it to Tulip.
  • More broadly, it gives me access to a wide ecosystem of packages, from which Tulip can benefit, e.g.: JuMP, iterative methods for solving linear systems, GPU-based linear algebra kernels.
11 Likes
32

I would like to give a different perspective to this topic, mostly for MILP problems and from a non expert.

The use of MILP formulations is massive in many sectors, I will take just power systems as an example. The fact that these systems with their strategic nature depend on what 3 to 5 commercial solvers to function is a risk that is not covered in my sense.

Especially in a context where with more renewables the optim side will be more and more the value generator in national energy system vs sourcing cheap oil from some country in the other side of the planet.
If we add to that possible political issues that can prevent access to the technology like commercial wars between major economies I feel that 3 to 5 solvers is a very low number.

It’s certainly not the mission of the Julia community to solve that problem, but I try to talk about this issue whenever I can to practitioners in corporations relying too much on Gurobi & CPlex and to the smart guys and girls who can actually solve this problem. Maybe we can have a consortium to support such an initiative some day?

Someone needs to throw significant amount of money and effort at this problem to have a competitive solution, but why do it when you can buy licenses … until you can’t.

Sorry for the pessimistic tone but this is a topic that I have a hard time to wrap my head around.

3 Likes
33

But are the solvers really strategic, in the sense that taking them away would make such planning impossible?

AFAIK other methods, like (approximate) dynamic programming, Lagrangian relaxation, various evolutionary algorithms etc are used for power systems. I always had the impression that formulating as a MILP is done mostly out of habit/tradition (“this is the tool everyone uses and I was trained to use it”), and also because allows for a black-box solver.

This reminds me of people using Gauss for Computational General Equilibrium, with whole books about how to do it, while the actual problems are tractable in plain vanilla optimization packages in most languages these days without any problems.

34

The exemple I have in mind is solving the power system dispatch for a full country in minutes. I think it’s already using relaxations and tweaking the solver to get the performance. (So actually you get very quickly locked with a solver for this kind of problems).

I don’t work on these problems myself so I can be wrong, but this is what I understood from discussions with practitioners in these fields.

1 Like
35

Something like coin-or.org? Their software isn’t written in Julia, but it is open source, and the benchmarks I’ve seen put it within a factor of 2 of Gurobi’s performance.

EDIT: nevermind on performance claim. It’s true for their LP solver Clp but does not appear to be anywhere close for their MIP solver Cbc. For MIP, the benchmarks I’m looking at indicate MIPCL is at least within an order of magnitude.

36

The performance is often problem dependent, but across the board on industrial applications, I hardly ever hear that the performance of open source solver are acceptable for the operational problem sizes. And I think that they benchmark them regularly.
But I let people who actually work on these kinds of problems comment if they are tuning in!

37

FWIW I doubt IBM (CPLEX) is going anywhere any time soon.

38

This discussion is growing beyond the Julia ecosystem and community. :slight_smile:
What started as a “How about a Julia simplex solver” has turned into more of a “we need more high-performance open-source solvers”. Since this is a Julia forum, well, why not write them in Julia too?
OR forums like https://or.stackexchange.com/ would be a good place to discuss this topic.

At the heart of the discussion, I think, is the following: there is currently a dichotomy between commercial solvers, which are robust, efficient, but few and pricey, and open-source ones, which are free but not as good.
I feel it’s important to know how it came to be that way.

The main reason is that the performance of (commercial) MIP solvers stems from decades of continued development: there is no silver bullet, but a lot of small enhancements that eventually add up to tremendous performance improvements. That effort is possible because money is being paid to support a team of developers (typically half- to a dozen people).
Open-source solvers, on the other hand, tend to be one-off developments, sometimes followed by some level of maintenance. SCIP --albeit not technically open-source-- is the only successful example I know, and they have industrial partners that fund (parts of) its development.

Developing a new solver, and getting it adopted, faces a chicken-and-egg problem: no one will use it until it’s good, but it takes time (and money) to build something good. In addition, AFAIK, there is no example of a viable business model out of an open-source solver. Atoptima, whose team develops the column-generation framework Coluna.jl might become a nice case study.

Finally, open-source modelling languages go a long way in addressing the lack of competition between solvers (and how strategic any one product can become): if your country’s power grid planning is tied to CPLEX, when CPLEX disappears, you are in big trouble. If you could switch to Gurobi/Xpress/Mosek/LocalSolver/SAS/Knitro/Baron/Octeract/etc. in a glimpse, it’s already less of an issue. (think about how containers made it easy to switch between platforms & cloud vendors).

I would be very curious to see an MBA case study on something like “how many optimization solvers should there be in the world”?

11 Likes
39

Yes. Incredibly so.
The “real-time” unit commitment problem to decide what every generator in regional a power-grid must be solved every 5 minutes, or the electricity grid will stop working. Mass blackouts and power surges.
It is supercomputers in bunkers under-mountains level strategic.

Could you reformulate that problem to not be phrased a a MILP?
Sure, but it would still be computationally equivelent to a MILP, and we wouldn’t have the decaused of tools and knowledge to build from.

11 Likes
40

I am not an expert on this, but my understanding is that the MILP formulation is already an approximation, so it does not follow that other approaches would be computationally equivalent and equally costly. Eg (approximate) DP approaches have come a long way and can solve large problems in microseconds.

I am assuming that the present situation is maintained because the industry has a lot of existing infrastructure they are hesitant to touchand few resources for R&D into algorithms/open source software that have payoffs in the future, and there is a supply side willing to provide solutions. So this is in a sense fine. I have no horse in this race, and I think that power grid operators should just use what works for them.

2 Likes
41

My two cents on the matter: I started thinking about this after I saw how well the Measurements.jl and DifferentialEquations.jl packages work with each other. I was wondering whether you could get similarly nice ways of e.g. formulating a robust optimisation problem, or stochastic problem if some of your parameters were defined by a distribution. Or solving power flow problems with complex variables. I have no idea if this would be possible in the way I think it would, but one can dream.

2 Likes