Need help for defining appropriate constraints

Question

I'm very new to constraint programming and try to find some real situations to test it. I found one i think may be solved with CP.

Here it is : I have a group of kids that i have to assign to some activities. These kids fill a form where they specify 3 choices in order of preference. Activities have a max number of participant so, the idea is to find a solution where the choices are respected for the best without exceedind max.

So, in first approach, i defined vars for kids with [1,2,3] for domain (the link between the number of choice, activity and children being known somewhere else).

But then, i don't really know how to define relevant constraints so I have all the permutation (very long) and then, i have to give a note to each (adding the numbers of choices to get the min) and eliminate results with to big groups.

I think there must be a good way to do this using CP but i can't figure it out.

Does someone can help me ?

Thanks

Answer 1

I'm not sure that I understand everything in your description, for example "so I have all the permutation (very long)" and "i have to give a note to each (adding the numbers of choices to get the min)". That said, here is a simple encoding of what I think would be a model of your problem, or at least a starter.

It's written in MiniZinc and is shown below with a small example of 6 kids and 4 activities. The full model (including variants of some constraints) is here as well: http://hakank.org/minizinc/max_activity.mzn

Description of the variables: "x" is an array of decision variables containing the selected activity for each kid. "scores" is the scores (1, 2, or 3 depending on which activity that was selected) for the selected activity, and "total_score" just sums the "scores" array.

include "globals.mzn"; 
int: num_kids;
array[1..num_kids, 1..3] of int: prefs;

int: num_activities;
array[1..num_activities] of int: activity_size;

% decision variables
array[1..num_kids] of var 1..num_activities: x; % the selected activity
array[1..num_kids] of var 1..num_activities: scores;
var int: total_score = sum(scores);

solve maximize total_score;

constraint
   forall(k in 1..num_kids) (
     % select one of the prefered activities
     let {
        var 1..3: p
     } in 
       x[k] = prefs[k,p] /\
       scores[k] = 4-p % score for the selected activity
    )

   /\ % ensure size of the activities
   global_cardinality_low_up(x, [i | i in 1..num_activities], [0 | i in 1..num_activities], activity_size)
 ;

output [
  "x     : ", show(x), "\n",
  "scores: ", show(scores), "\n",
  "total_score: ", show(total_score), "\n",
];

%
% some small fake data
%
num_kids = 6;
num_activities = 4;

% Activity preferences for each kid
prefs = array2d(1..num_kids, 1..3,
  [
    1,2,3,
    4,2,1,
    2,1,4,
    4,2,1,
    3,2,4,
    4,1,3
 ]);

% max size of activity
activity_size = [2,2,2,3];

The solution of this problem instance is:

x     : [1, 4, 2, 4, 3, 4]
scores: [3, 3, 3, 3, 3, 3]
total_score: 18

This is a unique solution.

Using a slightly smaller activity_size ([2,2,2,2]) we get another optimal solution (total_score = 17), since there can be just 2 kids in activity #4 (kid #6 is here forced to take activity #1 instead)

x : [1, 4, 2, 4, 3, 1] scores: [3, 3, 3, 3, 3, 2] total_score: 17

There is two other possible selections for the second variant, namely

x     : [1, 4, 2, 2, 3, 4]
scores: [3, 3, 3, 2, 3, 3]
total_score: 17
----------
x     : [1, 2, 2, 4, 3, 4]
scores: [3, 2, 3, 3, 3, 3]
total_score: 17

Update: I also did a Picat model using the same principal approach: http://hakank.org/picat/max_activity.pi .

Update 2: The above model assumes that all kids get some of their preferred activities. When this assumption is not met one have then fix this somehow instead of just throwing a "UNSATISFIED" as an answer. One way is to select some other - not preferred - activity to kid which will yield a score of 0. This is done in this model: http://hakank.org/minizinc/max_activity2.mzn

The changes compared to the original model are small:

• the domain of "scores" are 0..num_activities
• we add a disjunction "/ scores[k] = 0" to the forall loop that selects the activity

Since this is a maximization problem a score of 0 will not be used unless it is necessary.

I also added a sanity check that there are enough activities for all kids:

constraint
  assert(sum(activity_size) >= num_kids, "There is not activities enough for all kids.")
;