Dependency Management for Uno

[worc4021]

Hello!

I would like to propose the creation of a dependency build repository for Uno. I use the word in its conventional sense, not necessarily a single git repository.

Personally, I really like that Uno is built with cmake, I think cmake is great at managing the platform tool chain on my behalf. However, when it comes to dependency management cmake has multiple different options and not quite the one unifying one..

In principle there are three different options:

1. Using cmake's find_library. The user somehow obtained whichever library and we find the library as a file and make cmake aware of this. There is a little more going on but essentially we're looking for a file path. If some macros have to be defined or we have to build position independent code or whatever, we have to tell cmake because this mechanism doesn't determine this. Similarly additional dependencies that the library itself has remain our responsibility.
2. Using cmake's IMPORTED library. Very similar to the previous option, only that we make the library into a full cmake target to use syntax such as target_link_library(<target> PRIVATE foo) instead of target_link_library(<target> PRIVATE ${foo_LIBRARY}) and target_include_directories(<target> PRIVATE ${foo_INCLUDE_DIR}). Slightly neater to be using, but we still have to somehow obtain the library.
3. Using cmake's installed targets. This is similar in the usage to an imported target, however, cmake does all the flag defining for us. This is possible if we have source code access to foo. In this case cmake generates a file for us to use the library in any other cmake project, e.g. in uno.

My proposition, is to incorporate dependency builds to levy cmake's installed targets. Whoever wants to build Uno will need source code access to all the solvers, so option 3 becomes available. This would entail the creation of repositories with CMakeLists.txt files for metis (and its toolbox function GKLib), bqpd, ampl, ma57 and mumps.

As and when additional solvers are added to the list of options, we'd have to add their dependency build as well. But this would shift all the complexity to individually testable builds, which can address whichever platform, tool chain, etc specific issues we might encounter.

The sequence of events for a fresh Uno build in my proposed scenario would be like this:

1. Clone dependency builds
2. Populate the source of the dependency build repos with your licensed code
3. Make the installed libraries available for Uno

For point 3, I have added a single folder where I keep installed libraries to the environment and refer to it, rather than modifying CMakeLists.txt files every time.

I have examples/potential candidates of the installable cmake builds for all but the ma57, e.g. here is one for AMPL. All but the mumps build turned out to be trivial.

What is done elsewhere? There aren't many other big solvers where we can see the build to compare. There are other smaller sovlers that rely e.g. on Metis, but usually the list of dependencies is short and the build itself is hardly ever what you'd call modern. Notably, ipopt is the only sophisticated build that really comes to mind. There dependencies are indeed managed with dependency builds similar to what I propose. The build tool chain is very unix focused and if you ever had the pleasure of compiling ipopt for commercial applications on windows outside the msys ecosystem to maximise performance you will know that it is a challenge. Having said that, I think that Uno has the opportunity to also be the first big nonlinear solver to have a slick integration into modern build processes.

I would be keen to hear whether integration into other domains might require a different solution altogether, as I have no insight into e.g. the current julia integration efforts.

I'd be happy to contribute to dependency builds, if we chose to go into that direction.

Cheers,
Manuel

PS. technically, there is a fourth option of how to incorporate dependencies. Including their build into the uno build, such as FetchContent or CPM, but I discarded them since this wouldn't scale well and its a rather poor compromise in my experience. If you thought about vcpkg.. Wouldn't it be cool if it worked for licensed stuff..

[cvanaret]

Thanks for the proposal, @worc4021!
I'm tagging the other contributors, in case they want to jump in: @leyffer @odow @david0oo @amontoison @traversaro

[traversaro]

I have been monitoring uno for some time, and I think it is really great. For what regards dependency management, in my lab we try to use conda-forge to manage all its dependencies to have a unified way of managing Python and C++ dependencies. We even have some (private) recipe for building some non-open-source software like ma27. So, at some point I would like to package uno in conda-forge, and all the work done for Julia integration will help a lot on this! However, conda may not be the best option if you are looking for a workflow in which you build all the dependencies from source, at least at the moment (some tools are being developed that could simplify the "build all dependencies from source", but they are not ready at the moment).

If you thought about vcpkg.. Wouldn't it be cool if it worked for licensed stuff..

What is the problem with licensed stuff and vcpkg? In vcpkg you can have arbitrary ports define in any directory, that you pass via --overlay-ports option, see for example https://github.com/robotology/robotology-vcpkg-ports . The ports can contain arbitrary logic, such as copying an existing library in the install prefix: https://github.com/robotology/robotology-vcpkg-ports/blob/efd91793e121185c1c67e49fe7d3e4b2860c5342/ensenso-binary/portfile.cmake . One could think of having a port that takes the licensed code somewhere in the filesystem (perhaps with the location pointed via a env variable) and then compiles the library, as if it was an open source library.

Also spack may be convenient in the context of "all deps from source" scenario, but I do not have a lot of experience with it.

[odow]

No opinion. We'll work around any changes and keep building via Yggdrasil.

People could just download the prebuilt binaries from https://github.com/cvanaret/Uno/releases

[worc4021]

Hello guys, thank you for your responses!

Is the sentiment then that we all three aren't big fans of the uno build? @traversaro you'd like uno to be managed in conda wheras @odow you build with yggdrasil..

The point you raise about vcpkg is valid, @traversaro. I had not considered this option for uno as it would require providing not only a cmake build for dependencies, but also the portfile for each one and on top of that we'd add vcpkg to the party. I.e. either a submodule or a required system wide install. Whereas cmake is already required to build.

I am not a heavy python user, but from my understanding conda is a package manager rather than library management tool for a build. Superficially, conda forge looks quite similar in that sense.

The reason to promote a build from source vs downloading prebuilt binaries is control of dependencies. In my experience nlp solvers are rarely deployed into standalone applications but end up in some tool chain which does many other things and goes many other places. Before you know it your hardware in the loop setup needs to work out how to incorporate MPI, because someone introduced uno with a mumps dependency in some trajectory planner. Naturally, at this point the practitioner will have to modify the builds and he's kind of on his own. But at the moment we're all kind of on our own.
In my case, I wanted to get uno building on windows without the msys shortcut simply for the performance. At this point, I had to either make cmake builds for all dependencies or have different builds for windows and linux.

Another point is that the QP/LP interface is fairly simple, i.e. if one is paying for e.g. a gurobi or xpress licence, one might want to use those qp solvers instead of bqpd. Without being able to build uno there is no way to incorporate even for the simplest of tools into it.

Not sure, where this leaves us, tbf.

[traversaro]

Is the sentiment then that we all three aren't big fans of the uno build? @traversaro you'd like uno to be managed in conda wheras @odow you build with yggdrasil..

I am not sure if with "uno build" you mean the existing build system, or your proposal. Anyhow, there is something I want to stress out: what I think is ideal for a build system of a library like uno is not to force any package management aspect on their user, and I definitely do not think that anyone using uno should be forced to use conda and/or conda-forge (or any other package manager) to provide its dependencies. Even if one wanted to add in uno CMake build system somehow the possibility to build dependencies from source (for example via CMake's ExternalProject, but I am not sure if this is your proposal to be honest), I do not think it would make a lot of sense to force this, but rather this should be an option that users (and especially people packaging uno in package managers) should be able do disabled. If you want a comparison, I think casadi https://github.com/casadi/casadi is a good example: in casadi you can build each dependency via ExternalProject if you set the options -DWITH_<dep>:BOOL=ON and -DWITH_BUILD_<dep>:BOOL=ON, but if for example you are packaging casadi in package manager, and you want your preferred packaged manager to handle the dependency, you set the -DWITH_<dep>:BOOL=ON and -DWITH_BUILD_<dep>:BOOL=OFF, so <dep> will be found via find_package call.

On this point, I think the videos “Don't package your libraries, write packagable libraries!” in https://www.youtube.com/watch?v=sBP17HQAQjk and https://www.youtube.com/watch?v=_5weX5mx8hc go in depth and explain what I think is my point.

I am not a heavy python user, but from my understanding conda is a package manager rather than library management tool for a build. Superficially, conda forge looks quite similar in that sense.

I am not sure how you define "package manager" and "library management tool", so I am afraid I am not able to comment on this. I am not sure if this is helpful, but just to clarify:

• conda is a cross-platform package manager that is not specific to any programming language (even if it is heavily used by the scientific Python worl), and it supports installing executable, C/C++/Fortran libraries, Python libraries, CMake libraries, etc etc. It is kind of a system package manager in Linux distributions (so like apt/yum) but it manages software in a user virtual environment (that is basically just a directories + a few scripts that set environment variables to "activate" that directories.
• While conda was the first package manager that defined and permits to install "conda" packages, now multiple package managers permit to install conda packages and manage conda environments, the most used (beside conda itself) are mamba, micromamba and pixi.
• conda-forge is not a package manager, but rather a community-mantained distribution of conda packages. If you are familiar with Linux distributions, "conda-forge" is like Debian or Arch, while "conda" is apt or pacman.

[traversaro]

Reading again your proposal, I read:

Whoever wants to build Uno will need source code access to all the solvers

Personally I am not in favor of this, I think it should be possible to build Uno even if you just have access to the binary of all the solvers/dependencies, for the reason discussed in the previous comment.

[worc4021]

Thank you for your response. I liked the videos that you linked. I believe I've not made my point clear, as I think the talks you linked are very much in line with what I'm after. I wanted to compile uno on windows with a conventional toolchain (not msys) to put in place a matlab interface - downloading the prebuilt binaries is of no great use to bundle one mex and n shared libraries to become the uno matlab interface. In the process of building uno for windows, I needed to deal with the uno dependencies. I had to make all dependencies available. This means bringing in whatever meson build hsl has, bqpd is built with make, ampl also a make project and then there is mumps.. All of these libraries build perfectly fine on windows and linux without having to have custom build scripts for them that differ between windows and linux etc. if you bring them into cmake. BUT the existing builds for them either force you to be in msys (and here by force you I mean that either you do it or you simply do not get it) or you put in major extra work. I had to deal with this and I have a solution that relies only on a couple of cmake files and they do not need any TLC to build on various linux distros with icx and gcc as well as on windows with icx, with/without openmp and so on and so on.. But! I am not a software developer by trade so my solution could be garbage and someone else could make a huge deal better one. However, it does work!
The ExternalProject you mention seems like a decent option to me as well. But from what I know it compiles rather than links existing libraries. To me that is not a problem, as to the best of my knowledge, the libraries that uno relies on are distributed as source, so source code access is equivalent to having a licence.
What I do want to avoid, is to create a mex for uno based on a divergent build of uno itself. Whichever solution can meet this, is fine for me. Making a mex in my experience is pretty much synonymous with targetting windows, I don't know the numbers but I would expect that a vast majority of matlab users run on windows.

[david0oo]

Independent of the compilation, I have a remark for the Matlab interface. We implemented a Casadi interface, which is basically ready and only needs to be revived. One of the reasons why it is not shipped with the Casadi wheels at the moment is that bqpd is closed-source.
Casadi comes with a Matlab interface, so this would bring the modelling and the automatic differentitation for free.

[metab0t]

As a user who recently trying to build Ipopt on Windows without msys toolchain and gave up eventually, I deeply understand the frustration on building NLP solvers with dependencies on Windows.

The main difficulties are:

1. The unix-centered autotools workflow is difficult to use with MSVC.
2. There are no single reliable Fortran compiler on Windows like gfortran on Linux (flang-new in LLVM is maturing and there is ifx from Intel). Many linear solvers are written in fortran like spral, mumps and HSL.
3. No decent dependency management on Windows. The common dependencies like blas, lapack and metis usually exist in binary form compiled with msys toolchain and is difficult to use with MSVC.

For standard binary build, conda-forge might be the way to go because it uses MSVC as the native compiler on Windows and will use flang-new in the future to provide a dependency chain with proper ABI.

However, I want to point out that there is another way called dynamic loading to avoid the dependency issues to build binaries. In the build process, we only use the header files of third-party dependencies, then the main binary/library loads dynamic libraries of linear solvers or BLAS or LAPACK in runtime to acquire the handles of functions.

This approach is especially useful in the field of optimization because there are many non-free dependencies that cannot be distributed or only exist in binary form (like HSL, BQPD and other commercial solvers). As I mentioned above, there are also open source dependencies that are difficult to build on Windows. Dynamic loading can solve these issues because the main executable/library does not need these dependencies to build (dependency-free build), while keeping the ability to use them. The users can acquire these dependencies and use them with the main executable/library. It even allows switching the customized binaries at runtime if the user has an enhanced or modified version of dependency.

This method has been used by Ipopt to load HSL. OR-tools from Google and my project PyOptInterface also use similar techniques to load commercial optimizers.

As the QP/LP interfaces in Uno get implemented for multiple optimizers, I think that dynamic loading will become more appealing.

For open source solvers, if Uno bundles the static libraries, it is difficult to switch customized builds.

For non-free dependencies, there are two options:

1. Disable them and distribute binaries. Users must rebuild Uno from source if they want to use these depencencies and related functionality.
2. Build with them and distribute binaries. The binaries will complain "symbol not found" unless the users have ALL non-free dependencies.

I am happy to provide assistance if Uno plans to use dynamic loading to manage some of its dependencies.

[metab0t]

The public binary release should be able to call non-free binary without rebuilding from source and work without issues when non-free component is not available.

If Uno supports Gurobi and COPT as LP/QP solver, the released uno_ampl.exe should work no matter Gurobi or COPT is installed. Otherwise, there would be $2^N$ combinations for $N$ optional non-free components.

[worc4021]

I see where the confusion comes from! I have been talking about UNO, not about uno's ampl driver. I have only recently started looking more into ampl and from what I understand ampl (not uno_ampl) comes with all sorts of solvers pretty much built in, once one acquires the license one simply switches to the solver and voila. In that context, yes, it would be extremely bothersome to be rebuilding the driver. I am not sure what the plan for uno in ampl is, but I would expect that at some point uno the library will have to be somehow integrated into the ampl ecosystem so that users of the regular ampl can simply select uno as the solver and get going.

However, uno_ampl is only one interface to the uno solver and imposing conditions that make sense for this interface onto the underlying library would be a little bit like saying everybody who wants uno needs matlab installed because here is a matlab interface that I've been working on and it will not compile without it. That would of course be ludicrous! :) In spirit, I think, the approach described in the videos linked above is the way forward. In that sense whatever we end up on, in my eyes, should allow to build with the tools of a language spec without emulators and without the user HAVING TO change the build files himself. So in other words, the dynamic loading approach to cmake would simply mean setting BUILD_SHARED_LIBS:BOOL=ON so as long as I can deactivate this, I wouldn't care.

On your point about the combinatorial explosion: I don't think this is a problem for uno (the solver library). Uno has been designed modularly from ground up. When you enable (or add) a solver you also enable (or add) a unit test for it. I.e. even if you have a solver configuration that isn't the default as long as you have your unit tests working you should be ok. Naturally, the exhaustiveness of unit tests is always a point of contention and for systems that have feedback around their components one can always be surprised, i.e. the solver around e.g BQPD acts based on the output of BQPD and if the output of Gurobi were slightly different (but within tolerance) we would see slightly different results. But as far as building in testability, uno is in a pretty good place (in my eyes).

And perhaps a more combative stance on commercial solvers: In my experience solvers for which we do not get source files tend to take shortcuts and e.g. force one to be using particular versions of openMP and or MPI libraries because that's what they built with. In a world, where every solver works plug and play with the generally uploaded release build, these restrictions would be imposed on everything else. In my opinion, the uploaded binaries only have to work. Someone who finds out about uno should be able to pick them up and evaluate whether uno is good for their needs. Once they need to build uno into their tools they will need to build anyway. And! At the very last, once one has embarked on investing thousands of dollars for a gurobi, mosek or xpress license or so, maybe just consider getting a software engineer to help integrate it properly ;)

[metab0t]

The dynamic library of Uno has the same problem.
Like I said above, uno.dll will depend on gurobi120.dll and copt.dll.

There are also a lot of users of commercial solvers in academia who are not "one has embarked on investing thousands of dollars for a gurobi, mosek or xpress license or so". It is not wise to tell the users "hey, we support commercial solvers but if you use them, you are on your own and please compile the binary from the source by yourself".

[worc4021]

Why would it if you don't build the gurobi interface, which is what is currently done. I don't have access to ma57, so the interface to the ma57 is simply not compiled. If I get given a copy of ma57 it changes nothing until I build the library with the interface files.

But I think we're getting off topic. The original question was, how can we have a build that covers the main platforms without the user having to get his fingers into the cmake itself.

[metab0t]

Support for Gurobi is not even implemented currently, and I am only taking it as an imaginary example.

Apparently, we have different opinions on whether the official binary release should contain ALL functionalities with no need to build from source.

[Tianlongi]

Hello!
I've been following UNO for a long time. While researching the QP subproblem related to the SQP algorithm, I noticed that you mentioned a LaTeX manual on BQPD. However, I did not find the download address of this resource. I believe this resource will be of great help to my research. I would like to ask if you can provide any guidance or other information on how to access the BQPDLaTeX manual.

[cvanaret]

Hi there,
Here is the only BQPD manual I'm aware of: bqpd.pdf.
The null-space method was described in this paper: https://link.springer.com/content/pdf/10.1007/s101070050113.pdf
Hope that helps!

cc @leyffer