New Pyomo Expression System

[Bill Hart]

Hi, all:

For the past month or so I've been developing a new expression system for Pyomo, specifically to (a) avoid cloning during expression creation/manipulation and (b) avoid recursive expression operations (esp. during cloning and generation of canonical representations used for solver I/O).

The Pyomo5 expressions are in a pretty good state, and I wanted to give everyone an update and ask for some help.

Status:

The expr_dev branch is where pyomo5 expressions have been developed.  At this point, most of the tests in Pyomo pass on my laptop.  That means that I'm not testing parts of the code that rely on solver interfaces (e.g. CPLEX, IPOPT), but hopefully our core testing logic for expressions does not intimately depend on those! 

The current implementation includes a new representation object: StandardRepn, which serves as surrogate for AmplRepn and which is used to build CanonicalRepn.  Once I'm convinced that things are working, I'll deprecate the use of AmplRepn and CanonicalRepn.

I've done performance testing of expression generation, which look good.  In many cases Pyomo5 is faster, in some cases it's somewhat slower (10-20%).  But in all cases I avoid cloning, so there are no gotchas if the user doesn't construct expressions "the right way".  Also, I've created a Sum() function which acts just like sum(), but creates a single MultiSum expression object;   this is MUCH faster than using sum(), and it points to a way that users can optimize expression generation.

The current branch includes some changes that are not backwards compatible to Coopr3 and Pyomo4.  However, the Coopr3 and Pyomo4 expression logic was left intact, and the associated tests in pyomo.core are passing.  It just that there are likely edge cases and functionality that don't work.  When I do performance comparisons, I'll work on those.

I have NOT created a generic expression-tree-walker logic, but I know how to do this using the visitor pattern.  I'm open to input on how to structure the visitor logic and/or what type of visitor actions need to be supported.  I'll prototype this "soon";  the expression printer needs to be overhauled, and this is a good use-case for a generic expression-tree-walker.

PLEASE HELP ME WITH PERFORMANCE TESTING:   JP and Carl have given me some largish testing problems, but I've had troubled getting good test problems.  I'm going to work on performance profiling the end of this week.

Cheers,

--Bill

P.S.  I'm relatively confidence that Pyomo5 expressions will replace the default Coopr3 expressions soon (before the end of September).  This expression system is more reliable than Coopr3 or Pyomo4, and it can work seamlessely on CPython and PyPy (and probably Jython).  Hence, this will resolve a key outstanding issue for the deployment of Pyomo on alternative Python implementations.

[Bill Hart]

Here's an update on pyomo5 expressions:

I've finished a complete implementation of pyomo5 expressions and the new StandardRepn object.  Almost all tests in Pyomo are passing with these new expressions.  There are several notable advantages for this new capability:

. Scalability:  By elimination recursive operations, we can generate deep expression trees without running into stack limitations in Python.

. Clearer Semantics:  The semantics of entangled expressions are clearer, and the use of cloning is more principled (I'll document this more separately).

. Performance Stability:  There are no "right or wrong" ways of building expressions to avoid implicit cloning.

. Support for PyPy and Jython:  Pyomo5 expressions don't require reference counting, so they natively support these Python implementations.

. Runtime:  Worst case the performance with these expressions is a little bit slower, but in common cases (e.g. simple linear expressions) you can generate expressions much more quickly.

I'm in the process of benchmarking expressions with large models.  I haven't received many exemplars from developers, so please send stuff my way.

My "next steps" include:

. Deprecating multiple inequalities of the form:  0 <= x+y <= 1.   These are not supported by Python's syntax, and our implementation is a hack that has too many unintended consequences.

. Reworking the LP and NL writers to use the StandardRepn object and to eliminate recursive function calls.  Also, I'll create a binary NL writer.

. Create a expression tree walker using the visitor pattern, to help isolate the expression logic from other parts of the Pyomo code base.

. Documentation!