[gecode-users] Getting domain values after posting

[Guido Tack]

Hi.

> I would like to get the consistent values of the space after propagation,
> which are for the first variable, the value 0, for the second variable the
> values 3 and 5 and for the third variable the values 7 and 9. The value 1
> for example belongs to the space of the first variable but it's
> inconsistent because it doesn't satisfy the constraint.
> [...]
> I am assuming that Gecode depending on the nature of the constraint
> sometimes reduces the space by removing inconsistent values, and other
> times it doesn't. If that's the case I am wondering if there is a way to
> reduce the space without me manually assigning a value to each variable,
> then performing propagation, getting the report and removing that value
> from the space of the variable if the propagation has failed.

You are experiencing that constraint propagation is not a complete inference 
method.

The only requirement for propagators is that they are "sound", i.e. that they 
don't remove solutions and that they can tell whether an /assignment/ is a 
solution. Propagators, in particular Boolean combinations of reified 
propagators, are not required to be complete.

In your example, the reified constraints that you use
( q[i]==values[i] <=> firstConjunction[i]) can only propagate if q[i] is 
already determined to be values[i].

In order to solve problems with incomplete propagation, you need branching and 
search. You can use the predefined branching strategies and search engines in 
Gecode to determine all possible solutions of your problem.

If you want to know more about the strength of different propagators, you 
could read about notions like arc consistency and generalized arc consistency 
(also called domain consistency).

Cheers,
	Guido

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