Major research grant to solve practical problems

St Andrews academics from the School of Computer Science have just been awarded a £1.1m research grant to develop a 'Constraint Solver Synthesiser' - software that they hope will dramatically improve the way we solve complex practical problems.

Lead researcher Dr Ian Miguel points out: "Constraints are everywhere. For example, in the production of a university timetable: the maths lecture theatre might have a capacity of 100 students; art history lectures might require a venue with a slide projector; no student can attend two lectures at once. Constraint solving offers a means by which solutions to such problems can be found automatically."

At the moment, even with the help of current constraint solvers, solving large, complex problems still requires the manual help of an expert - and such experts are hard to come by. The aim of the project is to improve dramatically the ability of constraint technology to solve large, practical problems efficiently, and remove the reliance on human expertise.

Dr Miguel said, "At present, people rely on constraint solvers that are jacks-of-all-trades. This is convenient, but means that we really struggle to solve some difficult problems. What we propose is, for a given problem of interest, decide what kind of constraint solver would solve it best and produce that solver automatically."

The researchers believe that the Constraint Solver Synthesiser will be a 'novel and elegant' solution and a groundbreaking direction for research in this field.

"This approach will allow us to introduce efficiency measures that work very well for these larger problems, but are not necessarily suitable for general use." Dr Miguel continued. "In other words, instead of being a jack-of-all-trades, the synthesized solver would be a master of a particular kind of problem - like trying to timetable a whole university!"

It's hoped that improved constraint technology could open up further research possibilities and would be valuable in a wide variety of disciplines, including scheduling, industrial design, aviation, banking, combinatorial mathematics, and the petrochemical and steel industries.

Source: University of St Andrews