Problem solving

St Andrews University academics have been awarded a £1.1m research grant to develop constraint solver synthesiser software.

Using constraint solver software, engineers can solve various complex problems such as scheduling, resource allocation, planning, and timetabling.

But at present, even with the help of such constraint solvers, solving large, complex problems still requires the manual help of an expert, and such experts are hard to come by.

Now though, engineers from the school of computer science at St Andrews University think they can develop new constraint solver synthesiser software to solve that problem. The academics have recently been awarded a £1.1m research grant from the EPSRC to help them do this.

The central aim of their research is to develop a constraint solver synthesiser that can generate a constraint solver specific to solving a given problem. Synthesising a solver from scratch will also enable a fine-grained optimisation not possible for a general solver, allowing much larger, more difficult problems to be solved, according to the researchers.

Dr Ian Miguel, lead researcher, said: ‘At present, people rely on constraint solvers that are jacks-of-all-trades. While they are convenient, they struggle to solve some difficult problems. What we propose is, for a given problem of interest, to first decide what kind of constraint solver would solve it best and then to generate that solver automatically.’

It is hoped that improved constraint technology would be valuable in a wide variety of disciplines, including scheduling, industrial design, aviation, banking, combinatorial mathematics, and the petrochemical and steel industries.