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
The final report for the project can be found here