4.2.2.2. Lexicographic constraints

In this section: lex2, lex2_strict, lex_chain, lex_chain_greater, lex_chain_greatereq, lex_chain_greatereq_orbitope, lex_chain_less, lex_chain_lesseq, lex_chain_lesseq_orbitope, lex_greater, lex_greatereq, lex_less, lex_lesseq, seq_precede_chain, strict_lex2, value_precede, value_precede_chain.

lex2

predicate lex2(array [int,int] of var int: x)
Require adjacent rows and adjacent columns in the array x to be lexicographically ordered. Adjacent rows and adjacent columns may be equal.

lex2_strict

predicate lex2_strict(array [int,int] of var int: x)
Require adjacent rows and adjacent columns in the array x to be lexicographically ordered. Adjacent rows and adjacent columns cannot be equal.

lex_chain

predicate lex_chain(array [int,int] of var bool: a)
predicate lex_chain(array [int,int] of var int: a)
Requires that the columns of matrix a are lexicographically sorted, non-decreasing.

lex_chain_greater

predicate lex_chain_greater(array [int,int] of var bool: a)
predicate lex_chain_greater(array [int,int] of var int: a)
Requires that the columns of matrix a are lexicographically sorted, strictly decreasing.

lex_chain_greatereq

predicate lex_chain_greatereq(array [int,int] of var bool: a)
predicate lex_chain_greatereq(array [int,int] of var int: a)
Requires that the columns of matrix a are lexicographically sorted, non-increasing.

lex_chain_greatereq_orbitope

predicate lex_chain_greatereq_orbitope(array [int,int] of var int: a,
                                       int: kind)
Requires that the columns of binary matrix a are lexicographically sorted, non-increasing. Moreover, the second parameter kind has the following meaning: 0: no further constraints, 1: set-partitioning orbitope, 2: set-packing orbitope

lex_chain_less

predicate lex_chain_less(array [int,int] of var bool: a)
predicate lex_chain_less(array [int,int] of var int: a)
Requires that the columns of matrix a are lexicographically sorted, strictly increasing.

lex_chain_lesseq

predicate lex_chain_lesseq(array [int,int] of var bool: a)
predicate lex_chain_lesseq(array [int,int] of var int: a)
Requires that the columns of matrix a are lexicographically sorted, non-decreasing.

lex_chain_lesseq_orbitope

predicate lex_chain_lesseq_orbitope(array [int,int] of var int: a,
                                    int: kind)
Requires that the columns of binary matrix a are lexicographically sorted, non-decreasing. Moreover, the second parameter kind has the following meaning: 0: no further constraints, 1: set-partitioning orbitope, 2: set-packing orbitope

lex_greater

predicate lex_greater(array [int] of var bool: x,
                      array [int] of var bool: y)
predicate lex_greater(array [int] of var int: x,
                      array [int] of var int: y)
predicate lex_greater(array [int] of var float: x,
                      array [int] of var float: y)
predicate lex_greater(array [int] of var set of int: x,
                      array [int] of var set of int: y)
Requires that the array x is strictly lexicographically greater than array y. Compares them from first to last element, regardless of indices.

lex_greatereq

predicate lex_greatereq(array [int] of var bool: x,
                        array [int] of var bool: y)
predicate lex_greatereq(array [int] of var int: x,
                        array [int] of var int: y)
predicate lex_greatereq(array [int] of var float: x,
                        array [int] of var float: y)
predicate lex_greatereq(array [int] of var set of int: x,
                        array [int] of var set of int: y)
Requires that the array x is lexicographically greater than or equal to array y. Compares them from first to last element, regardless of indices.

lex_less

predicate lex_less(array [int] of var bool: x,
                   array [int] of var bool: y)
predicate lex_less(array [int] of var int: x,
                   array [int] of var int: y)
predicate lex_less(array [int] of var float: x,
                   array [int] of var float: y)
predicate lex_less(array [int] of var set of int: x,
                   array [int] of var set of int: y)
Requires that the array x is strictly lexicographically less than array y. Compares them from first to last element, regardless of indices.

lex_lesseq

predicate lex_lesseq(array [int] of var bool: x,
                     array [int] of var bool: y)
predicate lex_lesseq(array [int] of var float: x,
                     array [int] of var float: y)
predicate lex_lesseq(array [int] of var int: x,
                     array [int] of var int: y)
predicate lex_lesseq(array [int] of var set of int: x,
                     array [int] of var set of int: y)
Requires that the array x is lexicographically less than or equal to array y. Compares them from first to last element, regardless of indices.

seq_precede_chain

1.  predicate seq_precede_chain(array [int] of var int: x)

2.  predicate seq_precede_chain(array [int] of var set of int: x)
  1. Requires that i precedes i+1 in the array x for all positive i.

  2. Requires that i appears in a set in array x before i+1 for all positive i

strict_lex2

predicate strict_lex2(array [int,int] of var int: x)
Requires adjacent rows and adjacent columns in the array x to be lexicographically ordered. Adjacent rows and adjacent columns cannot be equal.

value_precede

1.  predicate value_precede($$E: s, $$E: t, array [int] of var $$E: x)

2.  predicate value_precede($$E: s, $$E: t, array [int] of var opt $$E: x)

3.  predicate value_precede($$E: s,
                            $$E: t,
                            array [int] of var set of $$E: x)
1, 2.

Requires that s precede t in the array x.

Precedence means that if any element of x is equal to t, then another element of x with a lower index is equal to s.

  1. Requires that s precede t in the array x.

    Precedence means that if an element of x contains t but not s, then another element of x with lower index contains s but not t.

value_precede_chain

1.  predicate value_precede_chain(array [int] of $$E: c,
                                  array [int] of var $$E: x)

2.  predicate value_precede_chain(array [int] of int: c,
                                  array [int] of var opt int: x)

3.  predicate value_precede_chain(array [int] of $$E: c,
                                  array [int] of var set of $$E: x)
1, 2.

Requires that c[i] precedes c[i +1] in the array x.

Precedence means that if any element of x is equal to c[i +1], then another element of x with a lower index is equal to c[i].

  1. Requires that c[i] precedes c[i +1] in the array x.

    Precedence means that if an element of x contains c[i +1] but not c[i], then another element of x with lower index contains c[i] but not c[i +1].