具有优先级的无法实现的分配
Unfulfillable distribution with prioritization
我正在处理 gnu prolog 的分发问题。我试图根据时间条件将教师分配给几个学校科目。理想情况下的代码如下所示。
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).
上面的变量 X 包含所有 3 位教师及其学科，他们能够教学。 T 代表教师，1 是此人的 ID，M = 数学，E = 英语，H = 历史。
学科限制意味着每门学科每周需要教授 6 小时。
教师限制规定了他们每周可以教的最短和最长时数。
这个例子非常有效，因为所有的约束条件都是偶数，方程式很简单。但我面临着教师无法匹配学科约束的情况。因此，如果发生这种情况，代码根本不起作用。
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).
此代码不会return任何解决方案。回答只是“不”。
这就是为什么我将主题限制放宽为 #< 而不是 #= 但这...
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).
...将导致 X = [0,0,0,0,0,0,0,0,0] ? 所以 Prolog 只是满足最小条件。
为了描述我需要的结果，我会让它变得更简单。
学校科目：数学 - 英语 - 历史
这 3 门学科每门都需要每周教授 6 小时。
老师 1 可以教授数学和英语，每周总计 3 小时
老师 2 可以教授英语和历史，每周总计 8 小时
老师 3 可以教数学和历史，每周总共 2 小时
我的第一个要求是按照给定的顺序对主题进行优先排序。我的意思是，首先需要涵盖数学。因此，如果没有足够的教师，则需要将所有可能的时间都用于数学。如果数学获得了最大可能的时间，即使这意味着它仍然没有完全涵盖，英语是下一个要涵盖的。这也是我的第二个要求，尽量接近要求，不要止步于最低。
对于上面给出的示例，我的预期结果是：
老师 1 和老师 3 被分配到数学，因为它是第一个优先科目。他们都只会达到 5 小时，而不是所需的 6 小时，但我希望它尽可能接近。所以两位老师都 100% 学习数学。从老师 2 开始，6 个小时将分配给英语。这是因为它是第二个优先主题，需要 6 个小时才能完成。剩下的2小时将载入史册。
数学：5 小时（老师 1 + 老师 3）
英语：6小时（老师2）
历史：2 小时（老师 2）
我读到 gnu-prolog 中有 fd_maximize。听起来它可能会解决我的问题，但到目前为止我无法让它发挥作用。它总是在错误中解决。
有什么方法可以达到我想要的目标吗？
先谢谢大家了。
对主题的初始约束意味着所有 Tij 的总和 = 3 * 6 = 18。因此对教师的约束（这意味着不同顺序的相同总和）不能 < 18。因此您的公式为：
%% 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,
没有解决方案（因此 No 由 gprolog 回答）。
顺便说一句，0 #=< T1M + T1E + T1H 形式的约束是无用的：所有变量都≥ 0，它们的总和也≥ 0。
放宽所有约束，就像您在所有地方用 #=< 替换所有 '#=' 一样，显然提供了许多解决方案，第一个是所有 Tij = 0。您可以使用 fd_maximize 寻找更多有趣的解决方案（见下文）。
这里是一个版本，对科目的限制保持在6，对教师的限制放宽为≤6（如上所述不能<6）。它最大化总和（并且 returns 它作为 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).
执行给出：
| ?- 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
...
共有406个解。
如果你想“平衡”分布以最小化教师之间的差异，你可以最大化所有 Tij 的最小值，如下所示：
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).
现在只有一种解决方案：
| ?- soln(L, F).
F = 2
L = [2,2,2,2,2,2,2,2,2]
你最初的问题没有解决方案（我们称之为 over-constrained 问题），但你想找到解决方案放松 一些约束。
首先，over-constrained 问题通常（很多？）比承认至少一个解决方案的问题更难解决（因为发现它没有解决方案需要对搜索进行详尽的探索 space).
在目前的情况下，我们可以通过在关于主题的约束中添加人工变量来缓解问题：
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
成为
T1M + T2M + T3M + A1 #= 6,
T1E + T2E + T3E + A2 #= 6,
T1H + T2H + T3H + A3 #= 6,
其中A1, A2, A3是新的人工变量。这样做，我们用不等式 (≤) 代替等式 (=)，因为所有 Aj 都是正的。为了避免所有 Tij = 0 的解决方案，我们可以寻求一个解决方案，该解决方案将 Aj 和 fd_minimize 最小化。我们甚至可以通过系数来考虑您的优先级（数学 3，英语 2，历史 1）。我们称这些系数为权重。
这是程序：
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).
正在解决：
| ?- 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)
...
共有101个解。
我想与您分享我一直在寻找的解决方案。我希望这可以帮助任何遇到同样问题的人。
所以我在找两件事。尽可能接近主题要求并对主题使用优先级。我的一个朋友想出了一个很酷的逻辑来解决它。这是我在原始 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.
希望对您有所帮助。至少它解决了我的问题。如果我最初的问题不够清楚，无法得出这个解决方案，我也深表歉意。
顺便说一句，我想与您分享我在此过程中的另外 2 个见解。我不清楚这个求解器只能处理整数值。我现实生活中的数据使用的是十进制值。我将此解决方案用于一所拥有 45 名教师的真实学校。在这种情况下，gnu-prolog 由于值的数量而变得非常慢（2 小时是我等待的最长时间^^）。这就是我停止在这个项目上使用 GNU-Prolog 的原因，我现在正试图在 R 中解决它。
我正在处理 gnu prolog 的分发问题。我试图根据时间条件将教师分配给几个学校科目。理想情况下的代码如下所示。
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).
上面的变量 X 包含所有 3 位教师及其学科，他们能够教学。 T 代表教师，1 是此人的 ID，M = 数学，E = 英语，H = 历史。 学科限制意味着每门学科每周需要教授 6 小时。 教师限制规定了他们每周可以教的最短和最长时数。
这个例子非常有效，因为所有的约束条件都是偶数，方程式很简单。但我面临着教师无法匹配学科约束的情况。因此，如果发生这种情况，代码根本不起作用。
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).
此代码不会return任何解决方案。回答只是“不”。
这就是为什么我将主题限制放宽为 #< 而不是 #= 但这...
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).
...将导致 X = [0,0,0,0,0,0,0,0,0] ? 所以 Prolog 只是满足最小条件。
为了描述我需要的结果，我会让它变得更简单。
学校科目：数学 - 英语 - 历史 这 3 门学科每门都需要每周教授 6 小时。
老师 1 可以教授数学和英语，每周总计 3 小时 老师 2 可以教授英语和历史，每周总计 8 小时 老师 3 可以教数学和历史，每周总共 2 小时
我的第一个要求是按照给定的顺序对主题进行优先排序。我的意思是，首先需要涵盖数学。因此，如果没有足够的教师，则需要将所有可能的时间都用于数学。如果数学获得了最大可能的时间，即使这意味着它仍然没有完全涵盖，英语是下一个要涵盖的。这也是我的第二个要求，尽量接近要求，不要止步于最低。
对于上面给出的示例，我的预期结果是： 老师 1 和老师 3 被分配到数学，因为它是第一个优先科目。他们都只会达到 5 小时，而不是所需的 6 小时，但我希望它尽可能接近。所以两位老师都 100% 学习数学。从老师 2 开始，6 个小时将分配给英语。这是因为它是第二个优先主题，需要 6 个小时才能完成。剩下的2小时将载入史册。
数学：5 小时（老师 1 + 老师 3） 英语：6小时（老师2） 历史：2 小时（老师 2）
我读到 gnu-prolog 中有 fd_maximize。听起来它可能会解决我的问题，但到目前为止我无法让它发挥作用。它总是在错误中解决。 有什么方法可以达到我想要的目标吗？
先谢谢大家了。
对主题的初始约束意味着所有 Tij 的总和 = 3 * 6 = 18。因此对教师的约束（这意味着不同顺序的相同总和）不能 < 18。因此您的公式为：
%% 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,
没有解决方案（因此 No 由 gprolog 回答）。
顺便说一句，0 #=< T1M + T1E + T1H 形式的约束是无用的：所有变量都≥ 0，它们的总和也≥ 0。
放宽所有约束，就像您在所有地方用 #=< 替换所有 '#=' 一样，显然提供了许多解决方案，第一个是所有 Tij = 0。您可以使用 fd_maximize 寻找更多有趣的解决方案（见下文）。
这里是一个版本，对科目的限制保持在6，对教师的限制放宽为≤6（如上所述不能<6）。它最大化总和（并且 returns 它作为 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).
执行给出：
| ?- 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
...
共有406个解。
如果你想“平衡”分布以最小化教师之间的差异，你可以最大化所有 Tij 的最小值，如下所示：
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).
现在只有一种解决方案：
| ?- soln(L, F).
F = 2
L = [2,2,2,2,2,2,2,2,2]
你最初的问题没有解决方案（我们称之为 over-constrained 问题），但你想找到解决方案放松 一些约束。
首先，over-constrained 问题通常（很多？）比承认至少一个解决方案的问题更难解决（因为发现它没有解决方案需要对搜索进行详尽的探索 space).
在目前的情况下，我们可以通过在关于主题的约束中添加人工变量来缓解问题：
T1M + T2M + T3M #= 6,
T1E + T2E + T3E #= 6,
T1H + T2H + T3H #= 6,
成为
T1M + T2M + T3M + A1 #= 6,
T1E + T2E + T3E + A2 #= 6,
T1H + T2H + T3H + A3 #= 6,
其中A1, A2, A3是新的人工变量。这样做，我们用不等式 (≤) 代替等式 (=)，因为所有 Aj 都是正的。为了避免所有 Tij = 0 的解决方案，我们可以寻求一个解决方案，该解决方案将 Aj 和 fd_minimize 最小化。我们甚至可以通过系数来考虑您的优先级（数学 3，英语 2，历史 1）。我们称这些系数为权重。
这是程序：
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).
正在解决：
| ?- 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)
...
共有101个解。
我想与您分享我一直在寻找的解决方案。我希望这可以帮助任何遇到同样问题的人。
所以我在找两件事。尽可能接近主题要求并对主题使用优先级。我的一个朋友想出了一个很酷的逻辑来解决它。这是我在原始 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.
希望对您有所帮助。至少它解决了我的问题。如果我最初的问题不够清楚，无法得出这个解决方案，我也深表歉意。
顺便说一句，我想与您分享我在此过程中的另外 2 个见解。我不清楚这个求解器只能处理整数值。我现实生活中的数据使用的是十进制值。我将此解决方案用于一所拥有 45 名教师的真实学校。在这种情况下，gnu-prolog 由于值的数量而变得非常慢（2 小时是我等待的最长时间^^）。这就是我停止在这个项目上使用 GNU-Prolog 的原因，我现在正试图在 R 中解决它。