Discussion: Consider using pulp, or at least more generally hiding ilpy APIs

[tlambert03]

While looking into possible refactors to support https://github.com/funkelab/motile/issues/9, I've had a few thoughts/realizations. Broadly speaking, I'm reconsidering the degree to which ilpy and C++ code is necessary for setting up the problem (vs actually calling the solve() method and solving it). Most of what motile is doing is creating a nice API on top of heavy duty ILP solvers (right?) and until we actually call solve(), we're mostly just managing coefficients (something that could quite easily be done in pure python with acceptable performance).

1. Motile uses ilpy types liberally throughout the library, when perhaps pure python objects would be easier maintain (in terms of development)
   • add_costs and motile.Costs mostly deal with ilpy.Variables and motile.Weights ... both pure python objects
   • add_constraints either deal with ilpy.Expressions (which are essentially just combined ilpy.Variables) or ilpy.Constraint objects, which, while backed by C++ objects in ilpy, is really just a simple container for coefficients and a relation. Similarly, the Solver.constratints object is an ilpy.Constraints object, which is just a std::vector container for ilpy.Constraint. Something which could be represented by a python list or set. In fact, Solver.constratints can be swapped out quite easily for a python set without breaking tests, which would make #9 much easier to solve.
2. The primary place where the power of the C-extension is leveraged is in Solver.solve()... and that method actually rebuilds almost all of the ilpy types, including recreating the ilpy.Solver and ilpy.Objective. So it would be very feasible to make that the only method that works with ilpy, leaving all of the rest of the logic internal to motile, likely facilitating/easing development.

3. In some quick tests, I was actually able to swap ilpy almost entirely for pulp another python library quite similar to ilpy that I just discovered. Pulp also wraps SCIP and gurobi, as ilpy does, in addition to a bunch of other solvers. It seems well maintained (80 contributors, ~2k stars, last commit this month) and is available on conda forge (which would help solve https://github.com/funkelab/ilpy/issues/14 wherein you must have gurobi installed to run ilpy, even if you don't have the license). To change Solver.solve() to use pulp, it would look like this:

   def pulp_solver(self) -> pl.LpProblem:
       import pulp as pl
   
       # Create the 'prob' variable to contain the problem data
       prob = pl.LpProblem("Problem", pl.LpMinimize)
       prob.solver = pl.getSolver('GUROBI')
   
       variables = [
           pl.LpVariable(f"x{i}", cat=v.name) for i, v in self.variable_types.items()
       ]
   
       # Objective function
       prob += pl.lpSum([c * variables[i] for i, c in enumerate(self.costs)])
   
       # Constraints
       for c in self._constraints:
           op = {
               ilpy.Relation.Equal: operator.eq,
               ilpy.Relation.GreaterEqual: operator.ge,
               ilpy.Relation.LessEqual: operator.le,
           }[c.get_relation()]
           prob += op(
               pl.lpSum([c * variables[i] for i, c in c.get_coefficients().items()]),
               c.get_value(),
           )
   
       return prob

In my tests, the pulp solver did come up with the same final objective value for every test run in motile, but it yielded with different values for each variables... So I might need some help understanding expectations in the results. (@cmalinmayor, perhaps you could help me evaluate that?)

Summary

So, the thing I'm proposing we consider is this:

• Maybe we vendor ilpy.Expression and ilpy.Variable, both of which were pure python objects I added in https://github.com/funkelab/ilpy/pull/9 that could just as easily be motile.Expression and motile.Variable.
• We try to keep all of the interaction with ilpy in the solve() method. Which would make it easier to experiment with other backends like pulp.

I can open an example PR for that if you like. @funkey @cmalinmayor

this might be particularly useful in the context of the napari plugin you're building, as that may require your full package (and all of its dependencies) to be on conda-forge if you want it to be easily installable (and currently, we can't build ilpy on conda-forge because it demands gurobi be present at build time, and that's not on conda-froge)

[cmalinmayor]

This seems like a very positive change to me, but I need to take a closer look at the internals of motile/ilpy/pulp to have a more informed opinion. It would certainly make it easier for a newcomer to understand motile if all the main building blocks were in Python. In regards to the tests, I took a brief look at the graphs we use for testing and it seems very feasible that there are multiple optimal solutions with equivalent costs, in which case it is not "wrong" if pulp selects a different optimal solution than ilpy. I'd have to examine the exact tests in more detail - perhaps we can do that together this week.

[tlambert03]

sounds good, yeah lets chat about it. One minor point of clarification: I'm not necessarily proposing ditching ilpy and using pulp instead, but rather minimizing the degree to which we let the internals of ilpy invade the design of motile. It should be very easy to maintain compatibility with both ilpy and pulp, and indeed any future library that wraps C extensions of ILP/MIP/QP solvers)