i'm working on a distribution issue with gnu prolog. Im trying to distribute teachers to several school subject based on time conditions. The Code for the ideal case looks like this.
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 6,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 6,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
The Variable X above holds all 3 Teachers with their subject, they are able to teach. T stands for Teacher, 1 is an ID for the person and M = Math, E = Englisch and H = History. The subject constraits mean, that each subject needs to be taught 6 hours a week. Teacher constraints hold the minimum and maximum weekly hours they can teach.
This example perfectly works because all contraints are even and the equation simply works. But im facing cases where Teachers can not match the subject constraints. So if that happens, the code simply doesnt work.
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
This code will not return any solution. The response is just "no".
Thats why i loosened the subject constraints to #< instead of #= but this...
soln(X) :-
X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
fd_domain(X, 0, 10),
%% subject constraints
T1M + T2M + T3M #=< 6,
T1E + T2E + T3E #=< 6,
T1H + T2H + T3H #=< 6,
%% teacher constraints b/w 0 and 6 hrs
0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
fd_labeling(X).
...will result in X = [0,0,0,0,0,0,0,0,0] ? So Prolog is just fullfilling the minimum condition.
To describe the outcome i need i will make it even more simple.
Subjects at the school: Math - English - History Each of these 3 subject needs to be taught 6 hours per week.
Teacher 1 can teach Math and English with a total of 3 hours per week Teacher 2 can teach English and History with a total of 8 hours per week Teacher 3 can teach Math and History with a total of 2 hours per week
My first requirement is to prioritize the subjects in the given order. With that i mean, Math needs to be covered first. So if there aren't enough teachers, every possible hours needs to be directed to Math. If Math received the maximum possible hours, even tho that means its still not fully covered, Englisch is the next one to cover. This is also my second requirement, to get as close to the requirement as possible, not just stop at the minimum.
For the given Example above, my expected outcome would be: Teacher 1 and Teacher 3 are assigned to Math because its the first prioritized subject. They both will only get to 5 instead of the needed 6 hours, but i want it to get as close a possible. So both teachers 100% to Math. From teacher 2, 6 hours will be assigned to English. This is because its the second prioritized subject and it needs 6 hours to be covered. The remaining 2 hours will go into History.
Math: 5 Hours (Teacher 1 + Teacher 3) English: 6 Hours (Teacher 2) History: 2 Hours (Teacher 2)
I read that there is fd_maximize in gnu-prolog. It sounds like it could possibly solve my issue but i cant make it work so far. It always resolves in an error. Is there anyway to reach my desired goal?
Thanks everyone in advance.
I want to share with you the solution i was looking for. I hope this might help anyone with the same problem.
So i was looking for 2 things. Getting as close to the subject requirements as possible and use a prioritization for the subjects. A friend of mine came up with a cool logic to solve it. Here is the Code for the example i wrote in my original post.
soln(T1M,T1E,T2E,T2H,T3M,T3H) :-
VARIABLES = [
T1M, % Teacher 1 can teach Math
T1E, % Teacher 1 can teach English
T2E, % Teacher 2 can teach English
T2H, % Teacher 2 can teach History
T3M, % Teacher 1 can teach Math
T3H, % Teacher 1 can teach History
PM, % If we cannot cover the Math hours, there will be PM penalities
PE, % If we cannot cover the English hours, there will be PE penalities
PH % If we cannot cover the History hours, there will be PH penalities
],
fd_domain(VARIABLES, 0, 10), % Each of the variables can take 0 to 10 (at most 8 for this case, larger is okay)
% Constraints for teachers
T1M + T1E #=< 3, % Teacher 1 can have at most 3 hours
T2E + T2H #=< 8, % Teacher 2 can have at most 8 hours
T3M + T3H #=< 2, % Teacher 3 can have at most 2 hours
% Constraints for subjects % To prevent the solver to fail solving when the constraint cannot match
T1M + T3M + PM #= 6, % Instead of insisting there must be at least 6 hours
T1E + T2E + PE #= 6, % but it will be penalized by the optimizer
T2H + T3H + PH #= 6, % below
% Constraints for penalities % penalities can only be positive
PM #>= 0,
PE #>= 0,
PH #>= 0,
%% Optimization
F #= PM * 100 + PE * 10 + PH, % Note how we use the multipliers to enforce the priority, the optimizer will
% always optimize for math first because it is penalized heavily
% F can reach 0 only if the constraints are feasible
fd_minimize(fd_labeling(VARIABLES), F).
main :- soln(T1M,T1E,T2E,T2H,T3M,T3H),
write('Teacher 1 spent '), write(T1M), write(' hours on Math'),nl,
write('Teacher 1 spent '), write(T1E), write(' hours on English'),nl,
write('Teacher 2 spent '), write(T2E), write(' hours on English'),nl,
write('Teacher 2 spent '), write(T2H), write(' hours on History'),nl,
write('Teacher 3 spent '), write(T3M), write(' hours on Math'),nl,
write('Teacher 3 spent '), write(T3H), write(' hours on History'),nl.
I hope you find this helpful. At least it solved my problem. I also apologize if my initial question wasn't clear enough to lead to this solution.
By the way i want to share with you 2 more insights i had during this process. It was unclear to me that this solver can only handle integer vlaues. My real life Data was using decimal values. I used this solution for a real school which had 45 teachers. In this case, gnu-prolog becomes extremely slow because of the number of values (2 hours was the longest i have waited^^). Thats the reason i stopped using GNU-Prolog on this project and i'm now trying to solve it in R.