optimization - 针对调度问题优化 MiniZinc 约束

Question

我正在尝试使用 MiniZinc 来解决调度问题。这是主要设置:

• 我有一定数量的学生
• 他们按偏好对 7 个主题进行排名
• 他们将被分配 4 个这样的主题
• 时间表中有 4 个时间段可用于所有这些

当然学生不能同时参加两个主题，每个主题也有最小/最大人数(但同一主题可能有不同的类(class)，或者另一个主题没有类(class))。这是最重要的约束条件，我们可以将其视为可满足性问题，尽管尝试最大限度地提高学生的快乐度是一个很好的奖励。

我尝试了以下方法，翻译了我所有的约束:

int: n; % number of students
int: m; % number of topics
int: c; % number of courses each student will take
int: maxseats; % number of seats available per course max
int: minseats; % number of seats minimum per course
int: timeslots; % possible time slots for the courses

set of int: STUDENTS=1..n; % students
set of int: PREFERENCE=1..m; % possible preference rankings
set of int: TOPICS=1..m; % different topics
set of int: TIMESLOTS=1..timeslots; 

array[STUDENTS,TOPICS] of PREFERENCE: preference; % ranking of topics by each student

array[STUDENTS,1..c] of var TOPICS: course; % topics assigned to each student
array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to topics

include "alldifferent.mzn";
constraint % students have different topics
  forall(student in STUDENTS)(alldifferent([course[student,i] | i in 1..c])); 
  
constraint % no student has two topics at the same time
  forall(student in STUDENTS)(forall(i,j in 1..c where i<j)(schedule[course[student,i]] != schedule[course[student,j]])); 
  
constraint % less students per topic than available seats (NOTE : groups can be duplicated)
  forall(topic in TOPICS)(sum(student in STUDENTS where exists(i in 1..c)(course[student,i] = topic))(1) <= maxseats); 
  
constraint % more students per topic than the minimum
  forall(topic in TOPICS)(sum(student in STUDENTS where exists(i in 1..c)(course[student,i] = topic))(1) >= minseats); 

var int: satisfaction = sum(student in STUDENTS)(sum(i in 1..c)(preference[student, course[student,i]])); 

solve minimize satisfaction; 

问题是这只适用于少数学生，但对于我的学生名单(我有大约 100 个，虽然我没有那么多，但即使是 20 个也没有得出任何结论)，这还远远不够十分钟后)。

这是我的部分数据文件(为简单起见，删掉了一些学生，但已经太长了:

n = 10;
m = 7;
c = 3; 
maxseats=18; 
minseats=1; 
timeslots=4; 

preference =[|
1,2,5,3,7,4,6|
6,4,7,5,1,2,3|
1,2,6,4,5,7,3|
5,3,1,2,6,4,7|
5,2,1,6,3,7,4|
7,5,1,6,3,2,4|
1,7,6,4,5,3,2|
1,4,2,6,3,5,7|
4,6,1,5,2,3,7|
1,6,4,3,5,7,2|
|]; 

我可以添加任何相关约束或结构来帮助求解器完成工作吗？

*** 编辑。这是进一步的尝试。我注意到另一个问题:基本上，组不能太大(小于 maxseats)，因此每个主题会有不同的组(同一个老师)。因此，学生不仅不能同时上课，而且同一主题的不同群体也应该区分，不能同时上课。这看起来像是一个更大的组合问题!也许有一个聪明的方法来打包它，但现在我基本上选择了复制主题。

这是模型:

    int: n; % number of students
    int: m; % number of topics
    int: c; % number of courses each student will take
    int: g=5; % number of instances of each course
    int: maxseats; % number of seats available per course max
    int: minseats; % number of seats minimum per course
    int: timeslots; % possible time slots for the courses

    set of int: STUDENTS=1..n; % students
    set of int: PREFERENCE=1..m; % possible preference rankings
    set of int: TOPICS=1..g*m; % different topics
    set of int: TIMESLOTS=0..timeslots; 

    array[STUDENTS,1..m] of PREFERENCE: preference; % ranking of topics by each student
    array[STUDENTS, PREFERENCE] of TOPICS: prefRank = array2d(STUDENTS, PREFERENCE, [rank
       | student in STUDENTS, p in 1..m, rank in 1..m where preference[student, rank] == p]);

    array[STUDENTS,1..c] of var TOPICS: course; % topics assigned to each student
    array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to topics

    function int: topicToGroupFix(var int: t) =
        fix(((t-1) mod g) + 1);
    
    function var int: topicToTopic(var int: t) =
        ((t-1) div g) + 1;
    function int: topicToTopicFix(var int: t) =
        fix(((t-1) div g) + 1);

    function int: topicGroupToTopic(int: t, int: gg) =
        ((t-1) * g) + gg;
    
    array[TOPICS] of var 0..maxseats: number; % number of people taking each course
    constraint 
      forall (topic in TOPICS)(number[topic] = sum(student in STUDENTS, i in 1..c)(course[student,i] == topic)); 

    include "globals.mzn";

    constraint % before using another topic group make sure the previous one has students in it
      forall(t in 1..m, gg in 1..g-1)( number[topicGroupToTopic(t,gg+1)] > 0 -> number[topicGroupToTopic(t,gg)] >= minseats );

    constraint % if students are assigned to a topic group it must have enough
      forall(t in TOPICS)( number[t] > 0 -> number[t] >= minseats );

   constraint % make sure topics are slotted at different times
       forall(t in 1..m)( alldifferent_except_0([schedule[x] | x in topicGroupToTopic(t,1)..topicGroupToTopic(t,g)]));

    array[STUDENTS,1..c] of var PREFERENCE: courseRank;

    constraint % channeling constraint to obtain topic ranking
      forall(student in STUDENTS, i in 1..c)(courseRank[student, i] = prefRank[student, topicToTopic(course[student, i])]);

    constraint % no student has two topics at the same time
      forall(student in STUDENTS)(alldifferent([schedule[course[student,i]] | i in 1..c]));

    constraint % students have different topics (and break symmetries)
      forall(student in STUDENTS)(strictly_increasing([courseRank[student, i] | i in 1..c]));
      
    constraint % students have different topics
      forall(student in STUDENTS)(alldifferent([topicToTopic(course[student, i]) | i in 1..c])); 

    constraint % fairness - don't want any one student to get a bad schedule relative to others
      forall(student in STUDENTS)(sum([courseRank[student,i] | i in 1..c]) <= 
                                   min([sum([courseRank[s,i] | i in 1..c]) | s in STUDENTS where s != student])+1);
    %constraint % fairness - don't want any one student to get a bad schedule relative to others
    %  forall(student in STUDENTS)(sum([courseRank[student,i] | i in 1..c]) <= 
    %                               min([sum([courseRank[s,i] | i in 1..c]) | s in STUDENTS])+1);

    constraint % fairness - don't a student get a much worse choice than others
      forall(student in STUDENTS)(courseRank[student,c] <= min([courseRank[s,c] | s in STUDENTS where s != student])+1);
    %constraint % fairness - don't a student get a much worse choice than others
    %  forall(student in STUDENTS)(courseRank[student,c] <= min([courseRank[s,c] | s in STUDENTS])+1);

    % break symmetries on the schedule
    constraint forall(t in TOPICS)(if number[t] == 0 then schedule[t] == 0 else schedule[t] >= 1 /\ schedule[t] <= t endif);
    %constraint forall(t in 1..m)(schedule[t] <= t);
    constraint forall(t in 1..m*g-1)(schedule[t+1] <= (max(x in TOPICS)(schedule[x])+1));   
      
    var int: satisfaction = sum(student in STUDENTS, i in 1..c)(courseRank[student,i]);

    solve :: int_search(courseRank, smallest, indomain_min)
       minimize satisfaction;
    %solve minimize satisfaction;

    output(["satisfaction Level: \(satisfaction)\n"]);
    output(["student", "\t", "topic", "\t\t", "group", "\t\t", "courseRank", "\n"]);
    output([show(student) ++ "\t" ++ show([topicToTopicFix(course[student,i]) | i in 1..c]) ++ "\t" ++
                                     show([topicToGroupFix(course[student,i]) | i in 1..c]) ++ "\t" ++
            show([courseRank[student,i] | i in 1..c]) ++ "\n" | student in STUDENTS]);

    output(["studentsPerTopic: \(number)\n"]);
    output(["schedule: \([schedule[x] | x in TOPICS])\n"]);

可以使用相同的数据文件，但是有 100 个学生，即使 c=1(即只分配一节课，这应该是微不足道的!)也不会在数小时内完成...

有什么我可以做的，或者这个问题对于 MiniZinc 来说真的太大了吗？

Answer 1

我试着调整你的模型:

include "globals.mzn";
int: n; % number of students
int: m; % number of topics
int: c; % number of courses each student will take
int: maxseats; % number of seats available per course max
int: minseats; % number of seats minimum per course
int: timeslots; % possible time slots for the courses

set of int: STUDENTS=1..n; % students
set of int: PREFERENCE=1..m; % possible preference rankings
set of int: TOPICS=1..m; % different topics
set of int: TIMESLOTS=1..timeslots; 
set of int: COURSES=1..c;

array[STUDENTS,TOPICS] of PREFERENCE: preference; % ranking of topics by each student

array[STUDENTS,COURSES] of var TOPICS: course; % topics assigned to each student
array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to topics

constraint % students have different topics; we thus enforce topics per student to be sorted
  forall(student in STUDENTS, i in 1..c-1)(course[student,i] < course[student,i+1]); 
  
constraint % no student has two topics at the same time
  forall(student in STUDENTS)(alldifferent([schedule[course[student,i]] | i in COURSES])); 
  
constraint % students per topic within allowed bounds (NOTE : groups can be duplicated)
  forall(topic in TOPICS)(sum([(course[student,i] == topic)| student in STUDENTS, i in COURSES]) in minseats .. maxseats); 
  
var n..n*m: dissatisfaction = sum(student in STUDENTS)(sum(i in COURSES)(preference[student, course[student,i]])); 

constraint dissatisfaction < n * 5;

遗憾的是，对于给定的数据集，求解时间仍然超出我的耐心。

---

更新:

我第二次尝试使用 bool 决策变量来表示每个主题是否存在学生。

include "globals.mzn";
int: n; % number of students
int: m; % number of topics
int: c; % number of courses each student will take
int: maxseats; % number of seats available per course max
int: minseats; % number of seats minimum per course
int: timeslots; % possible time slots for the courses

set of int: STUDENTS=1..n; % students
set of int: PREFERENCE=1..m; % possible preference rankings
set of int: TOPICS=1..m; % different topics
set of int: TIMESLOTS=1..timeslots; 
set of int: COURSES=1..c;

array[STUDENTS,TOPICS] of PREFERENCE: preference; % ranking of topics by each student

array[TOPICS, STUDENTS] of var bool: course; % students assigned to topics
array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to topics
 
constraint % enforce the number of courses per student
  forall(student in STUDENTS)(c = sum([course[t, student] | t in TOPICS]));
  
constraint % no student has two topics at the same time
  forall(student in STUDENTS)(alldifferent([schedule[t] | t in TOPICS where course[t, student]])); 
  
constraint % students per topic within allowed bounds (NOTE : groups can be duplicated)
  forall(topic in TOPICS)(sum([course[topic, student] | student in STUDENTS]) in minseats .. maxseats); 
  
constraint %  limit the dissatisfaction of students
  max([preference[student, t] | student in STUDENTS, t in TOPICS where course[t, student]]) < 4;

使用求解器后端 Chuffed、Google OR 工具或 COIN-BC，这个问题在 10 秒内解决了。
如果最差偏好值的上限低于 3，则没有找到解决方案。选择两个主题并不奇怪。