MathOpt LinearTerm v. LinearProduct

[DimitrisMantas]

First off, thank you to the OR-Tools team for their hard work!

I'm playing around with MathOpt in Python and noticed the documented difference between LinearSum and sum(Iterable). Given another warning in the LinearBase docs regarding inefficiencies with operator overloading, it would seem to me that it's best to avoid it.

As such, I was wondering if there is any practical difference between expressions like x * 3, which returns a LinearTerm instance, and LinearProduct(3, x).

Thanks!

[rma350]

For most users, how you build your model does not matter much. Write the simplest possible (often with operator overloads) that that is asymptotically optimal for model building and ignore constant factors. When you run the code, if you notice that model building time is a meaningful fraction of total time, and model build time + solving time is a meaningful fraction of application time (e.g. maybe reading the database to fetch you data is slower), then it is time to optimize (this is uncommon, but does happen).

Some specific tips on improving Python performance: Calling mathopt.fast_sum(), rather than the build in Python sum(), will result in fewer objects being created to represent the expression tree (and solves some other issues and is recommended universally). The Model Builder API has a primitive for inner products that mathopt is missing, so doing sum_i a_i * x_i requires making an object for each multiplication, which can add up (similar to calling sum()). Re using LinearProduct vs LinearTerm, these objects appear to have ~the same size (both have two fields). If you are just multipling a constant times a variable, I would expect performance to be better with linear term, since there some extra structure we probably exploited somewhere to reduce the number of loops we need to run when we flatten an expression tree.

If the expression building really is the bottleneck (typically only happens if you have already moved all your other computation to get organize your data into C++ via numpy, if you are writing loops in python this doesn't help), you can just bypass expressions all together and directly set coefficients on variables/constraints, but this will make your code harder to read. And setting each coefficient (at least in the newest version of ortools) will cause a language boundary crossing, which is also kind of expensive.

Big picture, trying to optimize constant factors in Python is (IMO) a losing battle, as the language is not really designed for this. Having bulk operations via numpy to build your model (so all the work is done in C++) is a better way out than trying to micro optimize the very slow python code. We have some prototypes of this internally, no roadmap on if/when this will be submitted. We generally just use C++ directly if performance is an issue and cross the language boundary higher in the stack, but this is harder outside Google.

[DimitrisMantas]

Wow, thanks for your very detailed answer and insights, Ross! Much appreciated!

I agree with your view on potentially micro-optimizing the model building process, perhaps I got a bit carried away playing around with the framework.

On a side note, while working through the various examples on Github, I found myself preferring mathopt.LinearSum over sum or mathopt.fast_sum, so I’d definitely appreciate an inner product primitive being introduced in the future! I’m currently computing these with something like LinearSum([a[i] * x[i] for i in Iterable]) but this is a bit verbose IMO, and gets worse the more indices you're summing over…

[rma350]

Note that mathopt.fast_sum in fact creates a LinearSum object:

or-tools/ortools/math_opt/python/expressions.py

Line 62 in 474b5c3

return variables.LinearSum(summands_tuple)

so these approaches are not so different. Having an efficient inner product is on the TODO list, but I am not actively working on it.

In general, I think users shouldn't really need to interact with LinearSum, LinearBase, LinearTerm etc explicitly in their code, this is borderline an implementation detail. Really they should only need the arithmetic operators and fast_sum. The types are really only public so users who use a type checker (e.g. mypy) can write functions that return linear expressions.