Improve performance for large models

[MBradbury]

Addresses some performance issues identified in #749.

Primary changes:

1. LpConstraint no longer inherits from LpAffineExpression, this is so a reference can be kept to the already created object instead of copying it
2. Avoid creating temporary LpAffineExpression when building a LpConstraint with a RHS that is an int/float
3. Avoid creating temporary lists (e.g., of Iterables before iterating over them, before transforming lists into another form)

In some experiments with a model I am working with I have observed 4x improvement in setting constraints. pulp/apis/cplex_api.py:buildSolverModel has gone from 70s to 50s.

Comparison of numbers in performance script from #749 comparing the original performance to performance with this PR. Using list of tuples and passing that directly to LpAffineExpression remains faster than using lpSum.

Name	Original	PR
Slow Objective	16.692	16.595
Slow Constraint	22.000	6.435
Fast Objective	2.945	2.999
Fast Constraint	20.278	5.552

[MBradbury]

Just a note that I added some type hinting to help me understand the code. Happy to remove if needed.

[pchtsp]

please run the black linter as per instructions: https://coin-or.github.io/pulp/develop/contribute.html#applying-the-black-linter-formatter (and check any other step you may be missing). I'll try to review the changes soon.

[MBradbury]

Thanks for the changes. they look comprehensive. I also appreciate the type hints.

I'm curious though if there was a way to keep the inheritance of LpAffineExpression without making a copy when initializing the LpConstraint. Can't we just modifiy the LpConstraint init in line 1012 to fill the values without copying them? and then we would keep everything else as is.

This will still lead to a large copy as it is essentially copying a dict to another dict. So for the test file that would be a copy of a 3 million entry dict.

Another approach could be to have LpAffineExpression not inherit from dict and instead have it as a variable. Then the constraint would just use that variable when inherited from LpAffineExpression, avoiding the large copy.

[MBradbury]

I have tried to decouple LpAffineExpression from its dict base class, but this has led to test failures I cannot get to the bottom of. This commit can be found here: https://github.com/MBradbury/pulp/commit/12feb605e9b84af2c030d1ffb25e13110ba94100 if you have the opportunity to see what might be wrong.

[stumitchell]

Looking good however, I suggest that we do a major version change as the change to modifying things in place instead of copying may cause errors in existing code.

[pchtsp]

it seems some tests are failing

[MBradbury]

Looks like LpConstraint needs a asCplexLpAffineExpression method that calls the method of the same name on expr. Or the test can be updated to use LpProblem.objective.expr.asCplexLpAffineExpression instead of LpProblem.objective.asCplexLpAffineExpression.