Parallel nonlinear solvers

As a developer of parallel non-linear software, I want to share my experience working in this space and the challenges we face. If I were to break down why we don't have more parallel non-linear software I would pick the following reasons:

1. Expectations vs reality
2. Inherent difficulties in designing and implementing the algorithms.
3. Lack of good tools to implement, test, and deploy distributed software.

1. Expectations vs reality

Unfortunately, NLP or MINLP are very broad terms so people tend to expect a piece of software that solves e.g., NLP to solve every type of NLP, which simply cannot happen. That NLP may be sparse, dense, mostly linear, convex, pseudoconvex, large, small, parametric, etc. In every case, there are different optimal ways of exploiting parallel hardware, but building a piece of software that implements all of these ways is incredibly difficult, which is why we have several specialised packages.

In other words, parallelism in non-linear optimisation is tricky from a design point of view because how we choose to allocate parallel resources depends on the real-life problems our solver is designed to solve.

There are three main applications of parallelism for MINLPs:

1. Calculating derivatives in parallel (important in very dense problems)
2. Doing the factorisation step in parallel (important in very large problems)
3. Solving the problem many times in parallel, e.g., parallel branch-and-bound or multistart (important in MINLP problems)

A solver can only really do one of these in parallel, and that design choice determines what problems that solver can solve well.

For instance, with some tweaking IPOPT can run MUMPS in MPI mode, so if factorisation is the bottleneck, that's a solid choice. This makes sense for IPOPT as it is designed to do a single local optimisation as quickly as possible.

On the other hand, our own solver, Octeract Engine, is designed to prove global optimality and to locate feasible solutions for difficult MINLP problems. Therefore, for us it made sense to use parallel branch-and-bound because we need to solve millions of local optimisation problems, so when we run in MPI mode that's how we allocate work to the CPUs.

Other examples with various degrees of parallelism are SCIP, KNITRO, and NLPAROPT.

Now, if one was to use IPOPT with MPI-MUMPS for a large-scale local optimisation problem, that would be much faster than a parallel branch-and-bound solver, if IPOPT manages to solve the problem. If it doesn't, it often turns out that no amount of manual tweaking can yield a feasible solution in which case parallel branch-and-bound would have saved us time all along. Similarly, certain problems are just too big to feed into a solver that doesn't factorise a matrix in parallel.

These differences in expectations vs what the scientific reality is, mean that solver companies usually have to engage a lot in consultancy work (vs just building more and better stuff), and that academic projects rarely come to a state where they are usable by the community (IPOPT is a bright exception).

2. Algorithmic/Implementation difficulties

From an implementation point of view, it is hellishly difficult to come up with and implement a parallel framework correctly. As an example, it took us about a year to implement the parallel framework for Octeract Engine (and this is a team of people who had done this before). For the problems that our engine solves, we implemented so-called "true parallelism", in the sense that investing more CPUs results in linear speedups.

However, it took me 5 years to create and test the algorithm that achieves this (my PhD and post-doc). The reason this takes so long is that a high performance algorithm is never something we can implement by reading/creating a flowchart. In other words, it never "just works". It takes hundreds of tricks (the term is literally "advanced black magic") to make these kinds of algorithms work well in practice. Importantly, it takes much more effort than LP algorithms, because the structure we can expect in NLP can literally be anything.

On top of that, parallel computing applications tend to target large problems. The size factor comes with a plethora of issues around data structures, distributing memory, and actually thinking about the complexity of every tiny part of the solver to avoid bottlenecks, which are non-issues for smaller problems. All of this blends into one big interactive system that is very hard to design using good software practices without compromising performance.

3. Lack of tools for development, deployment and testing

Algorithmic difficulties aside, a big bottleneck is that our best choice for high throughput applications is MPI, which is simply just not a good enough tool anymore because it requires too much boilerplate and modern software is just too complex for that.

This is compounded by the fact that even when we do make it work on our rigs it comes with a host of portability, deployment, and maintenance issues.

For instance, after solver development was done, it took us around 4 months of full-time testing to ensure that it would run on all OS/hardware, and I swear that we ran into every single obscure issue in the history of Linux in the process (can't deny that it was a lot of fun though). We saw compiler bugs, kernel bugs, dependencies that would only build if we tried twice, linking problems that only happened some of the time even on the same machine, but my favorite is an issue where MPI would fail to work 1 in 10 times, and only if we used more than 60 cores (59 or fewer was fine).

Even then, we still have a few tickets of obscure issues that only occur when people run massive problems on clusters, and it can take a lot of time to reproduce and fix each one because we have to build our own tools most of the time (there's nothing we can buy out of the box).

From our point of view, we would love to have better tools because it would allow us to spend less manpower on maintenance and testing, and more on R&D and implementing new parallel algorithms.