This is an EPSRC-funded project GR/M90641 supported by .
The project duration is 3 years, completing in Autumn 2003.

The aim of the project is to investigate what happens when we change the representation of problems. For example, we can represent a vehicle routing problem (routing vehicles to pick up goods) as a factory scheduling problem: i.e. we represent vehicles as machines on the shop floor, visits as operations to be performed, and the travel distances as transition (setup) times between operations. What representation will be best, and under what circumstances? This change of representation is a change of representation in the large.

We can also have changes of representation in the small. For example, we can reformulate a constraint satisfaction problem (CSP) using boolean variables as an instance of satisfiability (SAT), or with 0/1 variables as a problem of finding an independent set.

There are some obvious reformulations, such as graph colouring as a problem of partitioning into independent sets. And there are some less obvious reformulations, such as the execution of a program (such as Gale Shapley) into applying arc-consistency to a suitable representation.

The final report for the project can be found here