(__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.

- Y. Zhang and Roland H. C. Yap, Solving Functional Constraints by Variable Substitution, Theory and Practice of Logic Programming, to appear.
- Felix Halim, Panagiotis Karras, Roland H. C. Yap, Local Search in Histogram Construction, AAAI: 24th AAAI Conference on Artificial Intelligence, 2010, to appear.
- Kenil C. K. Cheng and Roland H. C. Yap, An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints, Constraints 15 (2), 254--304, 2010.
- Felix Halim, Panagiotis Karras, Roland H. C. Yap, Fast and Effective Histogram Construction, CIKM: 18th ACM Conference on Information and Knowledge Management, 2009, 1167-1176.
- Steven Halim, Roland H.C. Yap and Felix Halim, Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem, CP: 14th International Conference on Principles and Practice of Constraint Programming, 2008, 640--645.
- Michael Clark, Martin Henz, and Bruce Love, QuikFix-A Repair-Based Timetable Solver, PATAT: 7th International Conference for the Practice and Theory of Automated Timetabling, 2008