Binder and Colab are compiled without any MIP solver

[TobiaMarcucci]

As discussed with @hongkai-dai. cc @EricCousineau-TRI.

Currently it is not possible to solve mixed integer programs (linear or quadratic) in pydrake using Binder or Colab, since Drake is not compiled with Gurobi or Mosek there. Would it be possible to support MILP and MIQP in some way in Binder and Colab? Thanks.

[EricCousineau-TRI]

If you're talking about completely public, unrestricted access to the solvers, my initial guess would be no, it wouldn't be possible due to licensing restrictions.

@jwnimmer-tri and @jamiesnape: Can I ask if this sounds accurate?

Can you describe your specific use-case? e.g.

• Why do you want it in Binder / Colab?
• Who are the intended users? (who do you want to have access to it?
• Are there potentially license-free solvers available?
• Or are there license-free solvers available?

[TobiaMarcucci]

I understand and agree. But I think it might be worth finding a MIP solver that can be used on Drake's Binder tutorials or in Colab for Underactuated? Even if it is not super performant.

My use case: I'm writing problem sets for the Underactuated class (which is now Colab only) and I'd like the students to solve some MILPs/MIQPs. I don't know about license-free solvers, but @hongkai-dai wrote a simple solver in C++: would it makes sense to have python bindings for that? (The simplest problems I've in mind just have a dozen of binaries.) In case you are interested, I can do a quick search to see if there are good free solvers out there.

Last thing that I don't fully get: how is it possible then that we can use SNOPT in Colab? SNOPT requires a license too, right? Is it fundamentally different from the case of Gurobi or Mosek?

Thanks for the quick response!

[EricCousineau-TRI]

Last thing that I don't fully get: how is it possible then that we can use SNOPT in Colab? SNOPT requires a license too, right? Is it fundamentally different from the case of Gurobi or Mosek?

I believe that we have an explicit agreement with Snopt that we are permitted to redistribute it compiled into Drake, but only if we prevent the public symbols from being accessible (i.e., people can only use Snopt through Drake's interface, not anything else).

I do not believe we have an agreement like that in place with Gurobi or Mosek. @hongkai-dai Can I ask if you know anything about that?

My use case: [...]

Thanks! Not really sure what's possible. Perhaps there are ways to work with Gurobi / Mosek in concert with the class, but I can't really speculate further than that.

[hongkai-dai]

Yes, I can add a python binding for the branch-and-bound C++ implementation in Drake. Will try it over the weekend.

A better solution is probably to add the third party MILP solvers. We have the following options

1. Cbc from COIN-OR. It uses EPL 1.0 license
2. GLPK I am not sure what license it uses, seems GPL?
3. SCIP. It uses ZIB Academic license.

@jamiesnape @jwnimmer-tri , which license is compatible with Drake? From a quick check it seems SCIP is the fastest MIP solver among the three above, is ZIB Academic license compatible with Drake?

For SNOPT, the reason why we can use SNOPT is because the authors of SNOPT kindly agrees us to ship SNOPT binary in Drake.

[jwnimmer-tri]

Issue #11200 is slightly related.

Yes, we have special permission to distribute SNOPT in binary-only form to the public when called via the MathematicalProgram interface.

We do not have any such agreement for Gurobi or Mosek. For an MIT class, you may be able to offer it to students using MIT's licenses. Something akin to #8836 could offer a "bring your own Gurobi". Or, within the class you could compile your own pydrake binaries (with Gurobi) instead of using the public images.

[jwnimmer-tri]

We already use a bunch of COIN-OR libraries in Drake (EPL); that is fine. The coinor-cbc/bionic 2.9.9+repack1-1 amd64 is already in Ubuntu 18.04.

GLPK is GPL-3 so we cannot use it.

SCIP's license excludes commercial use so we cannot use it.

License overview is https://github.com/RobotLocomotion/drake/issues/4045.

[hongkai-dai]

@TobiaMarcucci Also to make sure that we are on the same page, in the slack discussion you said the pset will solve MILP. In the github comment above you mentioned both MILP and MIQP. Do you want to support both MILP and MIQP? CBC and GLPK doesn't work for MIQP.

[TobiaMarcucci]

In the particular pset I have in mind (footstep planning) MILP would work fine, but I think in general we will end up solving MIQPs more often? I think the typical use of MIP in the class would be for some simple hybrid MPC with quadratic cost. So I think a solver that could do both would be better.

[RussTedrake]

11200 seems very relevant here, indeed. We could potentially use MIOSQP for the class even if it's not a good candidate for shipping with drake. But I do think we'd want to trampoline the SolverInterface methods to python so that we could write the wrapper and have everything run through the MathematicalProgram interface. @TobiaMarcucci -- do you think MIOSQP is a viable option?

[TobiaMarcucci]

Yes, MIOSQP could be an option. From what Bartolomeo told me, the branch and bound part is not optimized, but it should work fine for small problems. Also should be able to solve MILPs, I guess, since OSQP can solve LPs. So it can definitely be an option for class. But I can come back to you with more details on that.

I think for class it'd be very important for it to be accessible via the MathematicalProgram interface.

[jwnimmer-tri]

11200 alludes to this but I'll restate it more directly:

But I do think we'd want to trampoline the SolverInterface methods to python so that we could write the wrapper and have everything run through the MathematicalProgram interface.

For a solver (or solver adapter) written in Python, the most important thing is that the solver can call all of the methods on MathematicalProgram required to retrieve the problem specification, and all of the methods on MathematicalProgramResult required to populate the result.

It is not strictly required that the solver extend SolverInterface or SolverBase -- it only needs to do that if it's going to be called generically. And since we're not (yet) going to have ChooseBestSolver choose a python-based solver, the need to call it generically seems low.

For example:

prog = MathematicalProgram()
# ... add costs and constraints to prog ...
solver = MiosqpSolver()
result = solver.Solve(prog)
assert result.is_success()

still works even if the solver is just

class MiosqpSolver():
   def Solve(prog, initial_guess = None, solver_options = None):
        return MathemathcalProgramResult()

without SolverInterface nor SolverBase anywhere in the picture.

[RussTedrake]

Excellent point @jwnimmer-tri. Thanks. That’s obviously the correct path forward (even if we did eventually want to somehow make it available via the generic Solve).

[RussTedrake]

@TobiaMarcucci — i guess if both @hongkai-dai’s existing branch and bound and MIOSQP both profess to being unoptimized B&B, then perhaps it’s better to go with @hongkai-dai’s after all?

[TobiaMarcucci]

I think it makes sense to go for Hongkai's.

Fwiw: Just spoke with Bartolomeo who told me that, for MILPs, MIOSQP might suffer a bit since, for non-strictly convex QPs, OSQP does not have linear convergence rate. He suggests to add some quadratic regularization in case.