Performances of pywraplp vs mathopt (including LP warm-start)

[quentinplsrd]

First of all, thanks to the google team for these amazing optimization libraries. They are extremely useful in my research work.

I have been testing both pywraplp and mathopt in Python and I am a but confused by their performances.
If I am not wrong, mathopt will replace pywraplp and is more general than pywraplp. I would expect mathopt to be at least as fast (or even faster) than pywraplp.

Concretely, I have numerous LP problems that are very similar and, to save time, I have been solving them consecutively using LP warm start to leverage previous LP solutions.

• When using pywraplp, I simply update the coefficients and bounds using Cst.SetUb(...), Cst.SetCoefficient(...), and run the problem again using solver.Solve()
• When using mathopt, I also update the coefficients and bounds using Cst.upper_bound=..., Cst.set_coefficient(...), and run the problem again using result = mathopt.solve(model, solver, model_params = mathopt.ModelSolveParameters(initial_basis = result.solutions[0].basis))

In both cases, I use the solver GLOP

However, from my numerical tests, using pywraplp is 2 to 3 times faster than using mathopt.
I am not sure that it is only because of the LP warm-start process because, if I check the run time of each individual run, pywraplp is also faster.

Is this difference of performances normal/known?

[soppera]

One difference between MathOpt and pywraplp is that MathOpt separates the model from the solver(s).

With pywraplp you would reuse the same underlying Glop model when changing only a few things. This is possible with MathOpt as well by using IncrementalSolver. This class will allow you to call its solve() method multiple times and to reuse the same Glop solver.

[quentinplsrd]

Gotcha! Thanks for the reply!

If I understand well, even after running solver = mathopt.IncrementalSolver(model, solverType) I can still modify the constraints of the model like I would using Cst.upper_bound=..., Cst.set_coefficient(...), and then I simply run result = solver.solve().
The object "solver" will keep being updated of the modifications made to the object "model", correct?

[quentinplsrd]

I just tested it and it is definitely better: ~13,000 LP solve will take

• 375s with mathopt using initial_basis
• 236s with mathopt using IncrementalSolver
• 146s with pywraplp

There is still something that takes longer with mathopt but I am not sure what...

[soppera]

Note that as documented in the IncrementalSolver class I would recommend using with to make sure you always call .close() to free the underlying C++ objects:

with IncrementalSolver(model, SolverType.GLOP) as solver:
  ...

That said:

The object "solver" will keep being updated of the modifications made to the object "model", correct?

Yes. when you call solve() if first send an ModelUpdateProto containing only the changes since the construction or previous call to solve() to Glop. Any change you do before a call to solve() are taken into account.

There is still something that takes longer with mathopt but I am not sure what

This is a bit harder to say without being able to test by myself. There could be multiple reasons for this given the number of very short solves you have. Some ideas:

• MathOpt Python uses a pure Python implementation for Model and the computation of the ModelUpdateProto. This may add some visible overhead compared to a simple call to C++ as with pywraplp.
• To call the c++ MathOpt uses Pybind11 instead of SWIG; on top of that it uses protos. This could lead to added time.
• MathOpt tries to keep the default settings of underlying solvers while pywraplp was overriding these defaults. I don't think this is the case for Glop but maybe there is something I don't know about Glop settings.

It would be easier with a proper measure of performances with some profiler.
Perhaps you can add some timers in IncrementalSolver to measure how much time is spent in export_model() and _update_tracker.export_update() compared to the time spent in self._proto_solver.solve().

[quentinplsrd]

This is very helpful, thanks!

[rma350]

To add a little to what soppera, said:

It is very hard to say what is wrong without running a profiler. One guess is that building your protos could be a bottleneck. Internally, we use a C++ implementation of python proto. Getting this work externally requires some extra configuration/may not be possible with our existing build systems (bazel more likely to be supported than cmake). E.g. see:

https://stackoverflow.com/questions/74941471/how-to-i-install-protobufs-c-python-extension

Stepping back a bit, if model construction is indeed the bottleneck, and not solve time, then I think the right thing to do is to move as much of the computation out of python as possible. Ideally, you could just write the code in c++/java/go. But of course this is not always possible. Another option, assuming your data begins in numpy arrays, for mathopt to add bulk operations for Python, which is something we would like to do. I think that numpy bulk operations are utlimately faster and less intrusive to the code than trying to optimize all the constant factors by manually inlining things.