Supporting MIOSQP (in python)

[hongkai-dai]

The authors of OSQP solver recently extend their solver to mixed integer quadratic programming. This MIQP solver is open-sourced in https://github.com/OxfordControl/miosqp. According to their paper, they claim a comparable performance to Gurobi, and sometimes up to 7x speedup over Gurobi. It would be great to support this solver in Drake (as we don't have an open-source MIQP solver supported in Drake yet).

One issue is that this MIOSQP solver is written in Python. So likely we can only call this solver in Python binding. How shall we support a third party software that is written only in Python, not in C++, within Drake's framework? Is there an example?

cc @RussTedrake @jwnimmer-tri

[jwnimmer-tri]

\CC @EricCousineau-TRI FYI

Is there an example [of writing a SolverInterface subclass in Python]?

Nope.

The SolverInterface is bound, but doesn't appear to offer an override mechanism for (Do)Solve yet.

Also, not all MP methods needed by a Solver are bound yet (like quadratic_costs is bound but generic_costs is not).

---

One issue is that this MIOSQP solver is written in Python. So likely we can only call this solver in Python binding. How shall we support a third party software that is written only in Python, not in C++, within Drake's framework?

My suggestion is to make a prototype to see if the solver is useful for our problems (or whatever experiment can tell us if its useful). If that shows promise, then rewrite MIOSQP in C++ within Drake, with due credit to the original authors. It is a relatively small amount of code beyond OSQP.

Using the upstream Python MIOSQP would difficult for a few reasons. For one, it would only be available in pydrake (and not drake_cxx), but lots of our users only use C++. (Embedding a Python interpreter in a C++ library is possible, but very difficult.) Also, it uses OSQP's Python bindings which we haven't packaged yet.

---

It's possible that a good way to make the prototype would be to add pydrake bindings for SolverInterface enough to subclass it in Python? Those bindings could be useful in the future for us or users.

[EricCousineau-TRI]

Agreed on these above accounts. If it's trivial to rewrite the logic in C++, then yeah, we should do that. If we want to write solve extensions in Python, it is totally possible, but I agree with Jeremy's points above; additionally, it would require more extensive bindings of the existing costs and constraints to ensure that they can be fully introspected. (Useful to have, but not sure if it's the most pressing thing at this time.)

(Embedding a Python interpreter in a C++ library is possible, but very difficult.)

Warning: Strong opinion, but I would absolutely hate to have C++ code depend on an embedded Python interpreter. This generally creates more headaches and more restrictions unless it's purely an end-user application.

The community is divided on this, but I side with the author who cites Pokey the Penguin: https://www.twistedmatrix.com/users/glyph/rant/extendit.html It is referenced here with alternative opinions (search for glyph/rant on the page): http://lua-users.org/wiki/LuaVersusPython - but the primary counterpoints are for end-user applications, not libraries.

[hongkai-dai]

I agree the better solution is to write MIOSQP in C++.

Rewriting the code is not a trivial task, especially adding all the unit test on each piece of code. I probably won't have time for it in the very near future. I will change this issue to "backlog".

[EricCousineau-TRI]

To clarify, if you end up starting to prototype and need help hacking, I can certainly help in this regard. If you have some good benchmark problems that don't need the abstraction of MathematicalProgram, that'd be awesome. However, if we wanna test stuff out against Anzu and hack around and MIOSQP answers some major pain points, I can help there. I just don't want an embedded interpreter to land in master for use in library code, ever.

[hongkai-dai]

Thanks @EricCousineau-TRI . I probably won't work on writing C++ MIOSQP in the near future. If I do start working on it, I will definitely discuss with you.