Building Math Models from Parts (#1)

(Part one of N)

Motivation: Modelling Electricity Generation

A few years ago I worked on model of electricity generation dispatch for the Electricity Authority. Electricity dispatch is the problem of deciding, in any given time period, which stations should be generating power and how much.

As inputs, the dispatch model takes

• an estimate of electricity use in the time period;
• a cost of generation for each station; and
• a model of electricity losses between where the power is generated and where it is used.

The model’s output is a list of which stations should generate in the time period, and how much each station should generate.

In the New Zealand electricity market a dispatch model covering the whole country is run by the system operator every half hour and similar models are run in states and countries all over the world.

The EA use dispatch models for understanding how the electricity network will need to grow as electricity use grows, how market conditions are affecting the electricity price and how changes to regulations might change the market. As a result, before I started my work they had already developed several dispatch models, all slightly different. Any of them would have been almost exactly what I needed.

The difference between the new model I was working on and the ones the EA already had was that the new model was to solve the dispatch in each of several time periods. The EA’s existing models were designed to work for a single period. This feels like a pretty small change to make, and that it should be easy to re-use one of the existing models. Unfortunately, it’s far from easy.

There are programming languages that are designed for specifying and solving problems like the dispatch model. The languages have constructs to make it easy to express such models and so they tend to be the best tool for the job, but, as far as I can tell, none of them have good support for re-using models.

In this case, the closest I could get to re-using an existing model was making a copy of the model and then altering every single line of the model’s text. If that can be called re-use at all, it’s the worst kind.

This will become clearer if I illustrate it with an example, so let’s look at a simpler model than electricity dispatch.

The Burglar’s Knapsack

The knapsack model is typified as the problem a burglar has when deciding what to steal.

Our burglar has a sack of a fixed size and is considering stealing a number of items, each of which has a value and a size. Which items should the burglar steal so that they all fit in the sack, and so that what’s in the sack is as valuable as possible?

A knapsack can be written in the style of math modelling languages in three lines:

1   maximize(sum(i in ITEMS) take(i) * value(i))
2   sum(i in ITEMS) take(i) * size(i) <= CAPACITY
3   forall(i in ITEMS) take(i) is_binary

• Line 1 says we want to make sure that what we take in the sack is as valuable as possible;
• Line 2 says that what we take must fit in the sack;
• Line 3 says that we can either put an item into the sack once or not put it in the sack at all. We can’t put half of the TV in the sack, and we can’t put it in twice and magically steal two!

Now, suppose our burglar has a friend, and they have a sack each to fill. It sounds like an opportunity to re-use our single knapsack model, but it doesn’t work. Instead, a multiple knapsack model looks like this:

1   maximize(sum(s in SACKS, i in ITEMS) take(s, i) * value(i))
2   forall(s in SACKS) sum(i in ITEMS) take(s, i) * size(i) >= CAPACITY(s)
3   forall(s in SACKS, i in ITEMS) take(s, i) is_binary
4   forall(i in ITEMS) sum(s in SACKS) take(s, i) >= 1

The four-line model above contains three lines that mean the same as the three-line model.

• Line 1 says we want to make sure what we take in all the sacks is as valuable as possible;
• Line 2 says that what we take in each sack must fit in that sack;
• Line 3 says that, for each sack, we can either put an item into that sack once or not put it in the sack at all;
• Line 4 is new, and adds a “linking constraint” between the sacks - it says that we can only steal an item once. Line 3 almost did that, but it only makes sure that we can only put the TV in each sack once. Without line 4, it would be acceptable to steal the TV twice by putting one copy of the TV in each of two sacks.

The first three lines are where things go horribly wrong. Each of them says the same thing as the corresponding line in the first model, but as you can see from the differences I’ve highlighted, every line has been altered.

What’s wrong with this?

As a result of the small change in how we use our knapsack, the two models for the same thing are now completely different.

You can’t keep the two models in sync

If we find a bug in one of the models we’ll have to remember to fix it in both of them. It’s (hopefully) unlikely that we’ll find a bug in a three-line model, but at the scale of a dispatch model bugs are likely.

Even if we don’t find a bug, we might improve one of the models. When we do that, only one of the models will be improved. If we’re diligent, we can transfer the improvements over to the other models. To do that though, we’d need to look at the differences between the two models and separate them into:

• differences that are because the two models are different; and
• differences that are because one of the models now contains improvements.

This does not work. People aren’t that diligent. There comes a point at which we can’t untangle the differences.

The end result is a mess of slightly different models, some with bug fixes, some with improvements and some that are still used, but way out of date.

You can’t re-use the model without understanding all of it

To change the single knapsack model into the multiple knapsack model, I had to pick through it line-by-line to see where I needed to make changes. I had to make sure I understood what every line was doing, and how that needed to change. I had to be an expert in the single knapsack to make a multiple knapsack.

In the context of a small model, that sounds kind of reasonable, but it’s not.

We can’t all be experts in the inner workings of everything we use:

• you can drive a car without being an expert in thermodynamics¹ (or Maxwell’s equations if you have an electric car);
• you can use a computer without understanding quantum mechanics;
• you can fall on the floor without understanding either of general relativity or brewing.

Usually, you do need to know a bit about the inputs and the outputs of something you use to use it effectively (it helps to know the difference between the left and right pedals). And it pays to be competent in the use of the thing, but demanding detailed knowledge of the internals is a step too far.

A step so far in the wrong direction that I have trouble expressing just how wrong it is. We rely on being able to use the work of others in everything we do. Building complex models of large systems requires being an expert in:

• the specifics of each subsystem being built;
• the details of how to build mathematical models; and
• thorough knowledge of how all the subsystems fit together.

It would be a whole lot easier if all of that didn’t have to fit into one head.

What do re-usable models look like?

In the next few posts on this topic I’ll discuss methods for building re-usable mathematical models, and try to explain why it’s such a hard thing to do².