CODEWITHSUNDEEP
minizinc
aejh
aejh

Reputation: 13

Minizinc constraints from another array

I'm attempting my first constraint programming with minizinc. I'm trying to create a schedule, with n slots and n people, with a different person allocated to each slot. I'm using an array of var int to model the schedule, usingalldifferent() to ensure a different person in each slot. A separate array of size n, names contains their names, as below:

% Pseudo enum
set of int: NameIndex = 1..2;
int: Forename = 1;
int: Surname = 2;

int: n = 4; % Number of slots and people
set of int: slots = 1..n;

array[slots, NameIndex] of string: names = [| "John", "Doe" 
                                            | "Ann", "Jones" 
                                            | "Fred", "Doe"
                                            | "Barry", "Doe" |];                  
% The schedule
array[slots] of var slots: schedule;

% Every person is scheduled:
include "alldifferent.mzn";
constraint alldifferent(schedule);

% How to constrain by a value from names, say alphabetic order by forename.
% Want to compare each value in schedule to the next one.
%constraint forall (i in 1..n-1) (names[schedule[i],Forename] < names[schedule[i+1],Forename]);

solve satisfy;

output [show(i) ++ ": " ++ show(names[schedule[i], Forename]) ++ " " ++ show(names[schedule[i], Surname])  ++ "\n"
    | i in slots]
% should be:
%  | i in schedule]

How can I constrain schdule by values from names? In my (broken) example above, when the forall constraint is uncommented, i get (using the Minizinc IDE): 

in call 'forall'
in array comprehension expression
  with i = 1
in binary '<' operator expression
in array access
cannot find matching declaration

I follow the error until not understanding which declaration cannot be found. The output block show()s values from names quite happily when I index into array from the schdule value.

What am I missing? Is there a better way to model the names? I'm hoping to extend names to additional 'attributes' of people and create additional constraints. I'm sure both the model and my forall constraint are quite naive!

Upvotes: 1

Views: 1130

Answers (1)

hakank
hakank

Reputation: 6854

The problem is that MiniZinc don't have much support for strings; and specific for your example: there's no support for comparing strings ("<").

That said, there are some plans to support var strings (i.e. using strings as decision variables), but I don't know the exact status when it will be released.

Here's a very simple fix but it requires some preprocessing:

1) Create a new array which includes the (ordering) index of each name:

  array[slots] of int: names_ix = [4, % John Doe
                                   1, % Ann Jones
                                   3, % Fred Doe
                                   2, % Barry Doe
                                   ];

2) Change the ordering constraint to use this new array

constraint 
   forall (i in 1..n-1) (
      names_ix[schedule[i]] <= names_ix[schedule[i+1]]
   );

[There's a more complex variant that requires that you convert each character in the names to integers (in a matrix of "var int"), and then require that the words - as collection of integers - are ordered. Note that this tends to be quite messy, for example to handle strings of different lengths etc.]

Upvotes: 1

Related Questions