[gecode-users] Analysing search performance

[Guido Tack]

Hi!

> I'm currently using gecode to solve some industrial product
> configuraiton problems. The indstry defines their constaints in a tabular
> form. The columns in the table correspond to different attributes of the
> product (e.g., the kind of mohterboard for a PC), and each row defines
> valid configurations of the attributes. The problem is of course that these
> tables interact such that it is hard to find a valid global configuration.
>
> My question is whether Gecode has a direct way of encoding such tables? It
> can of course be encoded using a DNF formula where each conjunct
> corresponds to a row, but I wonder if this is the most efficient way.

We don't currently have a special propagator for this kind of ad-hoc 
constraints. What you would probably need is something like the work 
described in [1] or [2].
We already have ad-hoc (or extensional, or relation) constraints on our 
agenda, but we cannot say yet when we are going to implement this.

If anyone of you is keen on learning how to write propagators for Gecode, this 
may be an interesting and useful starting point! ;-)

Cheers,
	Guido

[1] Cheng, C.K.; Lee, J.H. & Stuckey, P.J. Box Constraint Collections for 
Adhoc Constraints. CP 2003

[2] Christian Bessière, Jean-Charles Régin: Enforcing Arc Consistency on 
Global Constraints by Solving Subproblems on the Fly. CP 1999

-- 
Guido Tack
Programming Systems Lab, Saarland University, Germany
http://www.ps.uni-sb.de/~tack