How a computer scientist organised her wedding

In the weeks preceding their wedding, brides the world over face the same tricky problem: figuring out where to seat their guests for the meal. Most brides spend days looking at pieces of paper, penciling in guests' names at tables, then rubbing them out when that plan doesn't quite work. Computer Scientist Karen Petrie, a Dorothy Hodgkins Royal Society Research Fellow at the University of Dundee had another solution for her wedding. She wrote a computer program to create her table plan. She tells us more.

I work in an area of computing called Constraint Programming. Problems often consist of choices, and making the best choice can be extremely difficult. Constraint programming is the branch of artificial intelligence where computers help us to make these choices.

A constraint programming problem consists of a series of choices, options for each choice and restrictions, or ‘constraints' on those choices. A solution just allocates options to choices so that all of the constraints are satisfied. For table planning, for example, the problem was to place guests (options) at tables (choices), subject to constraints like "married couples should be placed together". Other constraints include that people of similar age should be placed at the same table, people must be seated with at least one other person they know, and people who don't get on should be separated.

Unfortunately my program came up with 195 valid table plans for my 150 guests! I know that most people would be happy that their friends and family were so friendly that they could be seated in so many positions with no possible arguments, but for me it was a headache. Which table plan was the best one to choose? I ended up reading through them all and doing some tweaks to come up with what I thought was the ideal solution. This led me to think that there must be a better way.

The experience inspired me to develop a system that will summarise the solutions of a constraint problem in an easy to understand and compact way. The new system will tell users both what's the same about different solutions and, more importantly, point out all the differences. For table plans this means that users will be able to see which tables contain the same guests whatever the plan, and which guests can be moved between tables. They will then be able to either choose the best table plan. Alternatively they can add more constraints on those guests that can be moved between tables, then find a new ideal plan.

However, that's not the end of the problem. We were lucky in planning our wedding in that there was a possible table plan. What if our guests had so many conflicting personalities that there weren't any plans that fulfilled all the constraints? Just tell the user that there are no possible solutions? That would hardly help an already stressed bride.

I'm therefore also working on a system to overcome the problem of having too many awkward guests. The way it works is to calculate the best possible plans: the ones where the most, if not all, constraints are met. The system then asks the user to decide which of the constraints should not be fulfilled. With table plans that means it presents a small number of plans, telling the bride which constraints aren't met in each. She can then choose the table plan that best suits her needs.

I hope this system for dealing with cases where a problem does not have a single neat solution, in a user-friendly manner, will also work for other similar problems. That includes problems like rostering nurses, timetabling classes at schools and scheduling buses and trains. This would make constraint programming a useful technology in many aspects of our daily life.

The good news is that I successfully married Chris Jefferson, who is also a researcher in constraint programming, on the 5th of September, 2008. There were no complaints from guests about where they were sitting and no arguments. The guests did not realise their seats had been allocated by a computer program; although, it was obvious that they were at the wedding of computing enthusiasts by the cake.