Research seminar:

     Modelling and Solving Problems using Non-binary Constraints

By:
			      Roland Yap
		  http://www.comp.nus.edu.sg/~ryap/
			 School of Computing
		   National University of Singapore

On:
		       Tuesday 30th of May 2006
		at 11:15 in room 1311 of www.MIC.uu.se

Abstract:

In Constraint Programming (CP), one usually makes use of special
purpose constraints such as arithmetic or other global constraints.
Consistency algorithms for the general case where one doesn't have
special semantics tend to be more focused on binary constraints.  It
is however non-intuitive to model problems using binary constraints.
This talk shows how to model problems which do not have a natural
custom constraint by using non-binary constraints.  The first part
will show how to model/construct custom non-binary constraints using
the difficult Still-Life problems as a case study.  Since the
non-binary constraints which are natural for Still-Life have high
arities, defining and representing the constraints is itself a
problem.  We demonstrate that Binary Decision Diagrams (BDDs) can be
used for this task.  We will discuss a variety of more sophisticated
models which make use of different custom non-binary constraints.  The
end result we show more sophisticated models making use of ad-hoc
constraints are able to achieve much stronger propagation than with
the typical constraints in CP systems.

In the second part of the talk, we will consider the issues of
building a solver for non-binary constraints.  We will focus on the
special case of non-binary boolean constraints.  We introduce the use
of BDDs as an efficient representation for ad-hoc non-binary boolean
constraints and a new GAC algorithm, bddc, which is tailored for the
BDD representation.  We show that bddc is efficient both in terms of
memory and time.