Benefits of constraint programming

Nonlinear costs or constraints

For example, a quadratic assignment problem can be modeled in CP as follows:

A quadratic assignment problem (CP)

using CP;

int nbPerm = ...;
range r = 1..nbPerm;
int dist[r][r] = ...;
int flow[r][r] =...;

execute {
        cp.param.Workers = 1;
                cp.param.timeLimit=30;
}


dvar int perm[1..nbPerm] in r;

dexpr int cost[i in r][j in r] = dist[i][j]*flow[perm[i]][perm[j]];

minimize sum(i in r, j in r) cost[i][j];
subject to {

  allDifferent(perm);

};

Logical constraints and statements

For example, forall statements, such as the following one, are efficiently taken into account by constraint programming:

A forall statement in CP

  forall(s in 1..nbSlabs)
    colorCt: sum (c in 1..nbColors) (or(o in 1..nbOrders : colors[o] == c) (where[o] == s)) <= 2; 

Constraints on and between interval variables

CP scheduling can express several types of constraint on and between interval variables:

• to limit the possible positions of an interval variable (forbidden start/end values or extent values),

• to specify precedence relations between two interval variables,

• to relate the position of an interval variable with one of a set of interval variables (spanning, synchronization, alternative).

Compatibility or incompatibility constraints

For instance, the following example is a concise model of the knight problem:

The knight problem

using CP;

int N = 18;
range K = 1..N;
range R = 1..8;

dvar int x[K] in R;
dvar int y[K] in R;

dvar int used[R][R] in 0..1;

constraints {
   forall(ordered k1,k2 in K) {
     forbiddenAssignments(
        {<i1,j1,i1,j1> | i1,j1 in R} 
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1+1 && j2==j1+2}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1+1 && j2==j1-2}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1-1 && j2==j1+2}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1-1 && j2==j1-2}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1+2 && j2==j1+1}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1+2 && j2==j1-1}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1-2 && j2==j1+1}
        union
        {<i1,j1,i2,j2> | i1,j1,i2,j2 in R : i2==i1-2 && j2==j1-1},
        x[k1], y[k1], x[k2], y[k2] );
   }

   forall(k in K) {
      used[x[k]][y[k]] ==1;
   }

   N == sum(i,j in R) used[i][j];
}

More useful features

When it comes to computing operational plans or schedules that must be executable, you cannot always use the linear form to simplifying costs or constraints. Fortunately, constraint programming can accurately model these problems.

Constraint programming can also be used as a fast generator of feasible solutions. This can be extremely useful in combination with other models and engines, for instance to implement column generation for a complex optimization model.