Performance suggestion: templates

[michaelbynum]

Implementing solver interfaces that utilize templates could significantly improve performance (including memory consumption).

[whart222]

Can you flush this idea out further? That will help us critique which ideas we focus on at the hackathon.

[blnicho]

I think the idea here is to try "templatizing" indexed Constraints/Expressions by default so that only a single expression tree needs to be constructed and then it could be reused when writing out each individual index.

[michaelbynum]

@blnicho Described the basic idea. Let me flush this out a little further.

First, I should note that there is a range of possibilities here. I will discuss a rather extreme version.

Consider the constraint:

y[i] = a[i] * x[i] + b[i] * v[i]

defined over a large index set. The idea of templates is to generate a single expression tree rather than an expression tree for each constraint. When the model goes to a solver, we can walk the expression tree once and then hand all of the constraints to the solver through whatever mechanism is effective for that solver interface.

As an example, let's consider the above constraint with the Gurobi direct interface. One way to create constraints in the Gurobi python interface is with a list of coefficients and a list of variables. We can avoid creating pyomo expression trees for all of the constraints and work primarily with native python containers. In this case, we could directly create the following lists:

[1, -a[i], -b[i]]

and

[y[i], x[i], v[i]]

for each i in the index set. At first, it may seem that this approach has very limited application. However, @jsiirola and @carldlaird have ideas on how to make this very flexible.

[jsiirola]

To follow what @michaelbynum said, we can (today) generate template expressions like the example he gave. We can also get templates for more complex expressions like

m.x[i] <= sum(m.y[i,j] for j in model.J[i])

where the sum is a node in the expression tree and has not been expanded.

I believe that it should be possible to "cannonicalize" template expressions using a slight variant of the visitor-based generate_standard_repn function I prototyped a couple months ago.

Doing this should have both significant speed and memory improvements: we don't have to generate or walk all the individual expressions. There is a little extra work, as we will still have to perform variable aggregation when we expand the templatized standard repn (m.x[i] and m.x[j] could resolve to the same _VarData; m.x[i] could be fixed, etc...), but that should be much faster than walking an expression.

I have been thinking about how to support template expressions in a way that is a drop-in capability with few (if any) user-visible changes. I think I can do this (there would need to be a few changes to Constraint, but I think they can all be fully backwards-compatible).

[jsiirola]

In addition, @carldlaird has some really intriguing ideas for an extended syntax that can support even more complex expressions like restrictions on the indexing sets.

[jsiirola]

Archived on the master Performance Proposals Issue (#1430). Closing this performance proposal until active development has begun.