Modeling Integer LP. In the next semester, the school plans to replace the tutorials by self-organized student groups. Your task is to find the best possible partition of students into groups and to appoint a group leader for each group. To achieve this task, you are given a list of students students. Each student needs to be assigned to exactly one group, and each group needs to have a (student) leader. Every student can be a leader, but we can have only one per group.
Arendrogfkl
Answered question
2022-11-08
Modeling Integer LP
In the next semester, the school plans to replace the tutorials by self-organized student groups. Your task is to find the best possible partition of students into groups and to appoint a group leader for each group. To achieve this task, you are given a list of students students. Each student needs to be assigned to exactly one group, and each group needs to have a (student) leader. Every student can be a leader, but we can have only one per group. A leader needs to be assigned to the group he is leading. The number of groups needs to be at least g and at most G. The quality of the groups depends on two criteria. First, the collaboration quality of a student i in a group with leader j is given by collaboration[i,j]. Furthermore, each student i has a certain leadership quality given by leadership[j]. You have to maximize the overall collaboration quality plus the sum of the leadership qualities of the leaders.
I have come up with the following and was wondering if I'm missing something or if someone can show me in the right direction:
I used the variable if a student i is assigned to the group with leader j () or not (). The variable yj shall denote whether student j is a leader () or not ().
I assumed that there are n students and m leaders. Then I came up with the following LP:
max s.t.
This is as far as I have gotten. I know I'm missing the connection between and . Also I'm not sure about my function I want to maximize. Help would be appreciated.