CONSTRAINT PROGRAMMING

(web page under construction!)

Constraint Programming (CP) is a programming paradigm where constraints, i.e. relations over variables, are used as basic entities for problem solving. It differs from imperative programming in that the constraints express declarative relationships and thus do not specify how the constraints or the problem should be solved. Instead that is the work of the constraint programming system or language as well as the constraint solver. Constraint programming has strong links with logic programming because of its declarative nature and much of the work in constraints has arisen from Constraint Logic Programming. Work in CP has strong links with the artificial intelligence community and CP (and CSP) is a major area in AI. The main areas of research in CP at the School of Computing are in new constraints, consistency algorithms, local search and applications of CP such as scheduling, and CLP for program reasoning.

Arbitrarily defined finite domain constraints, also known as non-binary CSPs, pose a challenge for solvers because even local consistency is intractable in the worst case. We have devised a new global constraint called mddc which can be thought of as two different kinds of constraints. Firstly, any arbitrary finite domain constraint can be converted into a mddc constraint. Secondly, it can be used by itself directly as a global constraint.

The mddc constraint is representative of a new important direction in global constraints which exploits the inherent structure of a constraint both in terms of representation as well as in the consistency algorithm. Due to this, a solver based on the mddc constraint was the fastest single solver in the general non-binary category beating mature solvers with more sophisticated heuristics and search strategies in the 3rd International CSP Solver Competition, 2008.

The work in local search is both on applying local search to real world problems and also on improving local search itself. While local search is often unreasonably effective, it is difficult to tune or tweak a local search algorithm to reach that stage. We have looked at a new approach to tuning based on using visualizations to improve local search in black and white box settings. Visualization was used to obtain a new state of the art local search for the hard Low Autocorrelation Binary Sequence problem (LABS), an unconstrained optimization problem. Local search is used to obtain a real-world timetabling solver which has been evaluated in the International Timetabling Competition 2007 and also used to schedule school timetables in Singapore. We also applied local search surprisingly to the histogram construction problem which can be constructed using a quadratic time algorithm but local search obtains a near linear time algorithm. The result is a histogram construction algorithm which gives the state of art tradeoff between scalability and quality.

Representative Publications