[prev] [prev-tail] [tail] [up]

3.4 Decomposed constraints

Decomposed constraints do not define any new constraints and related pruning algorithms. They are translated into existing JaCoP constraints. Sequence and Stretch constraints are decomposed using Regular constraint.

Decomposed constraints are imposed using imposeDecomposition method instead of ordinary impose method.

3.4.1 Sequence constraint

Sequence constraint restricts values assigned to variables from a list of variables in such a way that any sub-sequence of length q contains N values from a specified set of values. Value N is further restricted by specifying min and max allowed values. Value q, min and max must be integer.

The following code defines restrictions for a list of five variables. Each sub-sequence of size 3 must contain 2 (min = 2 and max = 2) values 1.

   IntVar[] var = new IntVar[5]; 
   for (int i=0; i<var.length; i++) 
      var[i] = new IntVar(store, "v"+i, 0, 2); 
 
   store.imposeDecomposition(new Sequence(var, //variable list 
                        new IntervalDomain(1,1), //set of values 
                        3, // q, sequence length 
                        2, // min 
                        2  // max 
                      ));

There exist ten solutions: [01101, 01121, 10110, 10112, 11011, 11211, 12110, 12112, 21101, 21121]

3.4.2 Stretch constraint

Stretch constraint defines what values can be taken by variables from a list and how sub-sequences of these values are formed. For each possible value it specifies a minimum (min) and maximum (max) length of the sub-sequence of these values.

For example, consider a list of five variables that can be assigned values 1 or 2. Moreover we constraint that the sub-sequence of value 1 must have length 1 or 2 and the sub-sequence of value 2 must have length either 2 or 3. The following code specifies these restrictions.

   IntVar[] var = new IntVar[5]; 
   for (int i=0; i<var.length; i++) 
      var[i] = new IntVar(store, "v"+i, 1, 2); 
 
   store.imposeDecomposition( 
                     new Stretch(new int[] {1, 2},  // values 
                                 new int[] {1, 2},  // min for 1 & 2 
                                 new int[] {2, 3},  // max for 1 & 2 
                                 var // variables 
                            ));

This program produces six solutions: [11221, 11222, 12211, 12221, 22122, 22211]

3.4.3 Lex constraint

The Lex constraint enforces ascending lexicographic order between n vectors that can be of different size. The constraints makes it possible to enforce strict ascending lexicographic order, that is vector i must be always before vector i + 1 in the lexicographical order, or it can allow equality between consecutive vectors. This is controlled by the last parameter of the constraint that is either true for strictly ascending lexicographic order or false otherwise. The default is non-strictly ascending lexicographic order when no second parameter is defined.

The following code specifies Lex constraint that holds when the strict ascending lexicographic order holds between four vectors of different sizes.

      IntVar[] d = new IntVar[6]; 
      for (int i = 0; i < d.length; i++) { 
          d[i] = new IntVar(store, "d["+i+"]", 0, 2); 
      } 
 
      IntVar[][] x = { {d[0],d[1]}, {d[2]}, {d[3],d[4]}, {d[5]} }; 
 
      store.imposeDecomposition(new Lex(x, true));

This program produces nine following solutions.

[[0, 0], [1], [1, 0], [2]],

[[0, 0], [1], [1, 1], [2]],

[[0, 0], [1], [1, 2], [2]],

[[0, 1], [1], [1, 0], [2]],

[[0, 1], [1], [1, 1], [2]],

[[0, 1], [1], [1, 2], [2]],

[[0, 2], [1], [1, 0], [2]],

[[0, 2], [1], [1, 1], [2]],

[[0, 2], [1], [1, 2], [2]]

3.4.4 Soft-Alldifferent

Soft-alldifferent makes it possible to violate to some degree the alldifferent relation. The violations will come at a cost which is represented by cost variable. This constraint is decomposed with the help of network flow constraint.

There are two violation measures supported, decomposition based, where violation of any inequality relation between any pair contributes one unit of cost to the cost metric. The other violation measure is called variable based, which simply states how many times a variable takes value that is already taken by another variable.

The code below imposes a soft-alldifferent constraint over five variables with cost defined as being between 0 and 20.

   IntVar[] x = new IntVar[5]; 
   for (int i=0; i< x.length; i++) 
      x[i] = new IntVar(store, "x"+i, 1, 4); 
   IntVar cost = new IntVar(store, "cost", 0, 20); 
 
   store.imposeDecomposition(new SoftAlldifferent(x, cost, 
                             ViolationMeasure.DECOMPOSITION_BASED );

3.4.5 Soft-GCC

Soft-GCC constraint makes it possible to violate to some degree GCC constraint. The Soft-GCC constraint requires number of arguments. In the code example below, vars specify the list of variables, which values are being counted, and the list of integers countedValues specifies the values that are counted. Values are counted in two counters specified by a programmer. The first list of counter variables, denoted by hardCounters in our example, specifies the hard limits that can not be violated. The second list, softCounters, specifies preferred values for counters and can be violated. Each position of a variable on these lists corresponds to the position of the value being counted on list countedValues. In practice, domains of variables on list hardCounters should be larger than domains of corresponding variables on list softCounters.

Soft-GCC accepts only value based violation metric that, for each counted value, sums up the shortage or the excess of a given value among vars. There are other constructors of Soft-GCC constraint that allows to specify hard and soft counting constraints in multitude of different ways.

store.imposeDecomposition(new SoftGCC(vars, hardCounters, 
                          countedValues, softCounters, 
                          cost, ViolationMeasure.VALUE_BASED));

[prev] [prev-tail] [front] [up]