[Gecode] New constraint: lex for lexical ordering

[Christian Schulte]

Dear all,

Gecode features now lex as a new global constraint expressing
lexical order amoung two sequences (arrays) of variables.

The constraint is posted by

	lex(home, x, r, y)

where home refers to the home space, x and y are arrays of
integer variables of same length and r is an inequality relation
(that is: REL_LQ, REL_LE, REL_GR, REL_GQ). It enforces that x and
y are lexicographically ordered with respect to r.

The propagator for lex is domain-consistent (but only bounds for
subsumtion). Each invocation costs O(n) in the worst case,
however typically it will be much better as it aggressively
eliminates assigned variables and variables known to be not any
longer relevant for decision (those that occur after a pair of
variables which are strictly ordered).

The constraint is useful (example will come) for symmetry breaking 
in matrix models.

Cheers
Christian

The algorithm is from:

 * This propagator uses the algorithm (and also the automaton)
 * from:
 *   Mats Carlsson, Nicolas Beldiceanu, Revisiting the
 *   Lexicographic Ordering Constraint. SICS Technical
 *   Report T2002:17, SICS, Sweden, 2002.

--
Christian Schulte, http://www.imit.kth.se/~schulte/