Minizinc: How to apply this constraint for scheduling model?

Question

I am working on a scheduling model and I'd like to figure out how to use this constraint: I am using Minizinc 2.0.2 version & MinizincIDE-0.9.7-linux and G12-MIP & Gecode solvers.

array[1..2,1..48] of var 0..1: table;
array[1..48] of int:demand;
array[1..2] of int: cost;
constraint forall(j in 1..48)(sum(i in 1..2)(table[i,j]) >= demand[j] );
solve minimize sum(i in 1..2)(sum(j in 1..48)(table[i,j])*cost[i]);
output [show(table)];

Sample data.dzn file:

demand=[0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
cost=[3,5];

Output Table array using G12-MIP solver gives this result:

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

This model is for 2 points and 48 hours(i.e 2 days).The constraint I wanted to add is to for each employee have shift each day without any break if alloted any. In this desired output is :

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

Approach I tried:

var 1..5: k;
array[1..2,1..2] of var 1..48: key2;
array[1..2,1..2] of var 1..48: key1;

% My aim is to store the first and last index for which table[i,j]=1 for each point (i) for each day (k)
constraint forall(i in 1..2,j in 1..48 where k= ceil(j/24))(if 
        table[i,j]==1 then key2[i,k]=j else true endif) 
         /\ forall(i in 1..2,j in 48..1 where k= ceil(j/24))(if 
        table[i,j]==1 then key1[i,k]=j else true endif);

% make all table[i,j]=1 between first index and last index for which table[i,j]=1
constraint forall(i in 1..2,k in 1..2)(forall(t in key1[i,k]..key2[i,k])(table[i,t]=1));   

When I ran it through Linux terminal using this command: mzn-g12mip test.mzn data.dzn It gave same previous result. When I ran it through MinizincIDE-0.9.7-linux It gave this error :

MiniZinc: type error: type error in operator application for `..'. No matching operator found with left-hand side type `var int' and right-hand side type `var int'

Is there any problem with this code or is there any other way to satisfy this constraint?

Answer 1

Two notes:

I got the same result as you: running via the command line works. Using MiniZincIDE give the same error, but after resetting the MZN_STDLIB_DIR in the terminal that run MiniZincIDE.sh then it works. Do you have MZN_STDLIB_DIR set? Then try to reset it with this command.

     export MZN_STDLIB_DIR=

Regarding the shift constraint, you can probably use the global constraint "regular". See the MiniZinc Tutorial for an example. The specific constraint you want here is "contiguity" constraint which requires that all 1s are collected. It's not built-in in MiniZinc, but you can see my model for an example: http://hakank.org/minizinc/contiguity_regular.mzn

Here's my version of your model, including the definition of contiguity.

include "globals.mzn"; 

array[1..2,1..48] of var 0..1: table;
array[1..48] of int:demand;
array[1..2] of int: cost;

var int: z = sum(i in 1..2)(sum(j in 1..48)(table[i,j])*cost[i]);

constraint forall(j in 1..48)(sum(i in 1..2)(table[i,j]) >= demand[j] );

constraint
  forall(i in 1..2) (
    contiguity([table[i,j] | j in 1..48])
  )
;

predicate contiguity(array[int] of var int: a) =
  let {
        int: n_states = 3,
        int: input_max = 2,
        int: initial_state = 1,
        set of int: accepting_states = {1,2,3},
        % the transition matrix
        array[1..n_states, 1..input_max] of int: transition_fn =
    array2d(1..n_states, 1..input_max,
    [ 
      % note:all states are accepting states
      1,2, % state 1 (start): input 0 -> state 1, input 1 -> state 2 i.e. 0*
      3,2, % state 2: 1* 
      3,0, % state 3: 0* 
    ]),
      int: len = length(a),
      % note: regular cannot handle 0 values, it must be > 0
      array[1..len] of var 1..2: reg_input
  } in
   forall(i in 1..len) (
     reg_input[i] = a[i] + 1
   )
   /\
   regular(reg_input, n_states, input_max, transition_fn,
                    initial_state, accepting_states)
;


solve minimize z;

output [
  "table: ", show(table), "\n",
  "z: ", show(z), "\n",
]
++ ["\ntable:"] ++
[
  if j = 1 then "\n" else " " endif ++
    show(table[i,j])
  | i in 1..2, j in 1..48
]
;

demand=[0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
cost=[3,5];

The optimal solution using this model is not the same as your solution since the tasks without any demand costs too much if person 1 must take all "empty" tasks between the mandatory tasks. If you have some other constraint that don't allow this separation of tasks, you have to add this in the model.

table:
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0