Unfulfillable distribution with prioritization

Question

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.

Answer 1

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.

Answer 2

The initial constraints on subject imply that the sum of all Tij = 3 * 6 = 18. Thus the constraints on teachers (which imply the same sum in a different order) cannot be < 18. So your formulation with:

    %% 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,

has no solution (thus the No answered by gprolog).

BTW, the constraints of the form 0 #=< T1M + T1E + T1H are useless : all variables being ≥ 0, their sum is also ≥ 0.

Relaxing ALL constraints as you did replacing all '#=' by #=< everywhere provide obviously many solutions, the first one being all Tij = 0. You can use fd_maximize to look for more interesting solutions (see below).

Here is a version where the constraints on subjects are kept to 6 and constraints on teachers are relaxed to be ≤ 6 (cannot be < 6 as explained above). It maximizes the sum (and returns it as F).

soln(X, F) :-
    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
    T1M + T1E + T1H #=< 6,
    T2M + T2E + T2H #=< 6,
    T3M + T3E + T3H #=< 6,

    %% Optimization: objective function (value put in a variable F)
    F #= T1M + T1E + T1H + T2M + T2E + T2H + T3M + T3E + T3H,
    
    fd_maximize(fd_labeling(X), F).

Execution gives:

| ?- soln(L, F).

L = [0,0,6,0,6,0,6,0,0]
F = 18 ? ;

L = [0,0,6,1,5,0,5,1,0]
F = 18 ? ;

L = [0,0,6,2,4,0,4,2,0]
F = 18 ? ;

L = [0,0,6,3,3,0,3,3,0]
F = 18 ? a
...

There are 406 solutions.

If you want to "balance" the distribution to minimize the difference between teachers you can maximize the minimum of all Tij as follows:

soln(X, F) :-
    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
    T1M + T1E + T1H #=< 6,
    T2M + T2E + T2H #=< 6,
    T3M + T3E + T3H #=< 6,

    %% Optimization: objective function (value put in a variable F)
    min(X, F),
    
    fd_maximize(fd_labeling(X), F).


min([X], X) :-
    !.

min([X|Xs], M) :-
        M #= min(X, M1),
        min(Xs, M1).

Now there is only one solution:

| ?- soln(L, F).                  

F = 2
L = [2,2,2,2,2,2,2,2,2]

Answer 3

Your initial problem has no solution (we call this an over-constrained problem), but you would like to find a solution relaxing some constraints.

First, an over-constrained problem is generally (much?) more difficult to tackle than a problem admitting at least one solution (because discovering it has no solution requires an exhaustive exploration of the search space).

In the present case, we can relax the problem by adding artificial variables in constraints about subjects:

    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

become

    T1M + T2M + T3M + A1 #= 6,
    T1E + T2E + T3E + A2 #= 6,
    T1H + T2H + T3H + A3 #= 6,

where A1, A2, A3 are new artificial variables. Doing this, we replace equations (=) by inequations (≤) since all Aj are positive. In order to avoid a solution with all Tij = 0 we can ask a solution which minimizes the sum Aj with fd_minimize. We can even take into account your priority with coefficients (3 for Math, 2 for English, 1 for History). We call these coefficients weights. Here is the program:

soln(X, F) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M + A1 #= 6,
    T1E + T2E + T3E + A2 #= 6,
    T1H + T2H + T3H + A3 #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    T1M + T1E + T1H #=< 4,
    T2M + T2E + T2H #=< 4,
    T3M + T3E + T3H #=< 6,

    %% Optimization: objective function (value put in a variable F)
    F #= 3*A1 + 2*A2 + A3,
    
    fd_minimize(fd_labeling(X), F).

Solving it:

| ?- soln(L, F).

F = 4
L = [0,2,2,0,4,0,6,0,0] ? ;

F = 4
L = [0,2,2,1,3,0,5,1,0] ? ;

F = 4
L = [0,2,2,2,2,0,4,2,0] ? a (to obtain all solutions)

...

There are 101 solutions.