/*
Max activity problem in Picat.
From
Need help for defining appropriate constraints
http://stackoverflow.com/questions/25806906/need-help-for-defining-appropriate-constraints
"""
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 ?
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
go =>
prefs(Prefs),
activity_size(1,ActivitySize),
max_activity(Prefs,ActivitySize, X, Scores,TotalScore),
println(x=X),
println(scores=Scores),
println(totalScore=TotalScore),
nl.
% find all solutions for second activity size
go2 ?=>
prefs(Prefs),
activity_size(2,ActivitySize),
max_activity(Prefs,ActivitySize, X, Scores,TotalScore),
println(x=X),
println(scores=Scores),
println(totalScore=TotalScore),
println("All optimal solutions:"),
All = findall([x=X2,scores=Scores2], max_activity(Prefs,ActivitySize, X2, Scores2,TotalScore)),
foreach(Row in All)
println(Row)
end,
nl.
max_activity(Prefs,ActivitySize, X, Scores,TotalScore) =>
NumKids = Prefs.length,
NumActivities = ActivitySize.length,
NumPrefs = Prefs[1].length, % number of stated preferences
% decision variables
X = new_list(NumKids),
X :: 1..NumActivities,
Scores = new_list(NumKids),
Scores :: 1..3,
TotalScore #= sum(Scores),
foreach(K in 1..NumKids)
% select one of the prefered activities
P :: 1..3,
% X[K] #= Prefs[K,P],
element(P,Prefs[K],X[K]),
Scores[K] #= NumPrefs-P+1 % score for the selected activity
end,
% ensure size of the activities
%
foreach(A in 1..NumActivities)
sum([X[K] #= A : K in 1..NumKids]) #<= ActivitySize[A]
end,
% global_cardinality_low_up(x, [i | i in 1..num_activities], [0 | i in 1..num_activities], activity_size)
% TotalScore #A= 17 % for solve satisfy and the second activity_size
Vars = X ++ Scores,
if var(TotalScore) then
solve($[max(TotalScore)], Vars)
else
solve(Vars)
end.
% Activity preferences for each kid
prefs(Prefs) =>
Prefs =
[
[1,2,3],
[4,2,1],
[2,1,4],
[4,2,1],
[3,2,4],
[4,1,3]
].
% max size of activity
activity_size(1,ActivitySize) =>
ActivitySize = [2,2,2,3].
% smaller activity #4
activity_size(2,ActivitySize) =>
ActivitySize = [2,2,2,2].