Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

LP/QP solver BQPD and possible alternatives #33

Open
odow opened this issue Oct 17, 2024 · 17 comments
Open

LP/QP solver BQPD and possible alternatives #33

odow opened this issue Oct 17, 2024 · 17 comments
Assignees
@cvanaret
Labels
question Further information is requested

Comments

@odow
Copy link
Contributor

odow commented Oct 17, 2024

HiGHS is MIT and it's easy to compile and distribute.

This would be muuuuuch easier than trying to agree on a way that we can distribute Uno with BQPD.
@cvanaret
Copy link
Owner

cvanaret commented Oct 18, 2024 •
edited
Loading

I agree! It's on my to-do list.
We will see a difference in performance though, since HiGHS solves only convex QPs. Negative curvature seems to be important to make good progress (but perhaps they will extend their QP solver to nonconvex QPs some day?)

@cvanaret cvanaret self-assigned this Oct 18, 2024
@traversaro
Copy link
Contributor

traversaro commented Oct 18, 2024 •
edited
Loading

I am not sure if it relevant in this context (I always get confused by the different requirements of different solvers) but proxsuite since 0.5.0 supports non-convex QPs, see https://github.com/Simple-Robotics/proxsuite/releases/tag/v0.5.0 and Simple-Robotics/proxsuite#257 .

@odow
Copy link
Contributor Author

odow commented Oct 19, 2024 •
edited
Loading

We will see a difference in performance though

I don't think this is the most important consideration. It doesn't have to be HiGHS. But it's hard (or impossible) to distribute a version of Uno with the LP/QP subproblem features if we need the non-free BQPD.

Another option Is OSQP: https://github.com/osqp/osqp

since HiGHS solves only convex QPs. Negative curvature seems to be important to make good progress

I don't understand the details in Uno well enough to comment. At the very least, HiGHS is an excellent LP solver.

but perhaps they will extend their QP solver to nonconvex QPs some day?)

This seems hard.

@imciner2
Copy link

imciner2 commented Nov 1, 2024

I don't think this is the most important consideration. It doesn't have to be HiGHS. But it's hard (or impossible) to distribute a version of Uno with the LP/QP subproblem features if we need the non-free BQPD.

Another option Is OSQP: osqp/osqp

I was actually wanting to add an interface for OSQP after we get OSQP 1.0 finished.

@leyffer
Copy link
Collaborator

leyffer commented Nov 1, 2024 via email

@odow
Copy link
Contributor Author

odow commented Nov 1, 2024

Providing a closed source binary library could be sufficient for people who compile Uno themselves. But I'm a bit cautious including it in Uno_jll for us to distribute.

  • What license would you provide the binary under?
  • Who would compile and host the binaries?
  • What platforms would be supported?

Currently we build Uno for a whole host of platforms: https://github.com/JuliaBinaryWrappers/Uno_jll.jl/tree/main?tab=readme-ov-file#platforms

  • macOS: aarch64 and x86_64
  • Linux: x86_64, i686, aarchh64, armv6 and v7, and PowerPC
  • Widows: x86_64 and i686
  • FreeBSD: x86_64

We also have both glibc and musl, and for differing C++ ABIs.

Perhaps we could have just BQPD binaries for Windows x86_64, Linux x86_64, macOS x86_64, and macOS aarch64, and then compile without BQPD on the more niche platforms?

@cvanaret
Copy link
Owner

cvanaret commented Nov 2, 2024 •
edited
Loading

Perhaps Sven @leyffer meant that we could build binaries of BQPD using BinaryBuilder.jl (without disclosing the source) in a BQPD_jll.jl package, the same way we built Uno_jll.jl?

@leyffer
Copy link
Collaborator

leyffer commented Nov 2, 2024 via email

@odow
Copy link
Contributor Author

odow commented Nov 2, 2024 •
edited
Loading

To clarify, I am not comfortable including BQPD in Uno_jll unless:

  • You make the source code publicly available under an open-source license. We then compile, host, and distribute BQPD_jll for every platform on Yggdrasil.

or

  • You compile and host the BQPD binaries (but not source code) under an open-source license on the public internet. We pull in the binary during Uno_jll's build.

The first approach is my preferred option. The second could work, but we will probably run into various compatibility issues and need to restrict what platforms we include BQPD on.

However, it doesn't seem like either of these are viable options.

So, if you want to use the Julia infrastructure to compile and distribute Uno, there are three options:

  1. Keep the status quo. BQPD is not available.
  2. Do what Ipopt does and allow linking at run-time
    • Users would need to email you, compile the binary themselves, and then set some option in Uno
  3. Do what HSL does
    • You compile and host a BQPD_jll package locally (not on the public internet). Users need to email you for access.
    • We compile a public facsimile of BQPD_jll with the correct symbols but no actual code. This lets the compilation of Uno_jll succeed because it thinks everything is there.
    • Then at runtime, users swap out our fake BQPD_jll with the real one from Sven

@imciner2
Copy link

imciner2 commented Nov 4, 2024

So, if you want to use the Julia infrastructure to compile and distribute Uno, there are three options:

1. Keep the status quo. BQPD is not available.

2. Do what Ipopt does and allow linking at run-time
   
   * Users would need to email you, compile the binary themselves, and then set some option in Uno

3. Do what HSL does
   
   * You compile and host a BQPD_jll package locally (not on the public internet). Users need to email you for access.
   * We compile a public facsimile of BQPD_jll with the correct symbols but no actual code. This lets the compilation of Uno_jll succeed because it thinks everything is there.
   * Then at runtime, users swap out our fake BQPD_jll with the real one from Sven

Longer term, it would be nice if we could somehow get BQPD support working in the UNO_jll, and creating a somewhat standardized workflow for doing this linking against proprietary libraries would be good, so I would say the method that HSL uses would be a good starting point. However, we also need to be careful that the software can properly handle the library not actually being the full library, so it should be able to identify that it doesn't have the library and fail gracefully to the user. (I don't know how the HSL facsimile handles that, actually).

Perhaps @amontoison can comment on how well the HSL fascimile system is working and if it is recommended to try that?

@amontoison
Copy link
Contributor

amontoison commented Nov 4, 2024 •
edited
Loading

@imciner2 For HSL_jll.jl, I added a C routine LIBHSL_isfunctional that returns a boolean, allowing us to determine at runtime whether we have the dummy or official version of libHSL.
Uno relies on it to use MA57 or MUMPS at runtime.

I can answer a few questions:

  • Linking at runtime is a pain on Windows; they don't use standard symbols for that, as usual... I don’t want to go down that path.

  • Doing it like HSL_jll.jl would require distributing a BQPD_jll.jl from a portal or website, along with a dummy BQPD that includes all the symbols needed by Uno, plus a way to detect at runtime whether we have the official BQPD. It’s like using a hammer on an egg.

  • The best solution is Oscar's second proposal: we cross-compile BQPD locally on all platforms using BinaryBuilder.jl.
    I can take care of that.
    We host all precompiled tarballs publicly somewhere (e.g., Sven’s webpage).
    We create a BQPD_jll.jl on Yggdrasil with all the precompiled tarballs.
    This is what we already do for some packages that are distributed only in precompiled form (e.g., CUDA_SDK_jll, MKL_jll, etc.).
    This approach avoids any compatibility issues and enables us to link Uno_jll.jl with BQPD_jll.jl. It also allows Charlie to generate precompiled Uno releases with BQPD here.

The two questions we need to answer are:

  1. Where should we upload all precompiled tarballs?
    I think Sven's webpage is suitable since some users could also request the precompiled form of BQPD directly from him.
  2. Finalize the license we want to include in the precompiled tarballs.

@leyffer
Copy link
Collaborator

leyffer commented Nov 4, 2024 via email

@imciner2
Copy link

imciner2 commented Nov 4, 2024

  • The best solution is Oscar's second proposal: we cross-compile BQPD locally on all platforms using BinaryBuilder.jl.
    I can take care of that.
    We host all precompiled tarballs publicly somewhere (e.g., Sven’s webpage).
    We create a BQPD_jll.jl on Yggdrasil with all the precompiled tarballs.
    This is what we already do for some packages that are distributed only in precompiled form (e.g., CUDA_SDK_jll, MKL_jll, etc.).
    This approach avoids any compatibility issues and enables us to link Uno_jll.jl with BQPD_jll.jl. It also allows Charlie to generate precompiled Uno releases with BQPD here.

I'm confused with what you are suggesting here. The precompiled packages like CUDA_SDK_jll and MKL_jll actually repackage the files and binaries compiled by the vendors into a tarball that we host on GitHub as an attachment to the releases, we don't link to any external tarballs in the JLL packages. That is then available to any Julia user to install.

Earlier in this thread, @leyffer said

As long as the binary package is not openly available.

was one of the conditions of use, so I think putting those precompiled tarballs with BQPD into the BQPD_jll repo would violate that because the binaries would be openly available for anyone to install. To do this so they aren't available to everyone, Sven still needs to control the distribution of them (somehow).

@leyffer
Copy link
Collaborator

leyffer commented Nov 4, 2024 via email

@imciner2
Copy link

imciner2 commented Nov 4, 2024

What I meant was that the source code is not public. It looks like the option that you describe would be OK.

Great, in that case we just will need some sort of statement (as the copyright holder) giving us the permissions to distribute the binaries, and include the appropriate license statement in the built tarballs. @odow I think you've done something similar for other packages, so maybe you can work with Sven to get that sorted out?

@odow
Copy link
Contributor Author

odow commented Nov 4, 2024

@amontoison can you please delete your comment? I don't want us to provide any legal advice or template.

Let's take this discussion offline. I'll send an email.

@amontoison
Copy link
Contributor

@odow Good idea.
I deleted the message.

@cvanaret cvanaret changed the title Add HiGHS as an LP/QP solver LP/QP solver BQPD and possible alternatives Nov 4, 2024
@cvanaret cvanaret added question Further information is requested and removed feature labels Nov 4, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@cvanaret cvanaret

Labels
question Further information is requested
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@traversaro @imciner2 @leyffer @odow @cvanaret @amontoison