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

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 x i , j if a student i is assigned to the group with leader j ( x i , j = 1) or not ( x i , j = 0). The variable yj shall denote whether student j is a leader ( y j ) or not ( = 0).
I assumed that there are n students and m leaders. Then I came up with the following LP:
max i = 1 n j = 1 m x i , j collaboration i , j + j = 1 m y j leadership j s.t.
j = 1 m x i , j = 1 i { 1 , , n }
g j = 1 m y j G
x i , j y j i { 1 , , n } j { 1 , , m }
x i , j { 0 , 1 } i { 1 , , n } j { 1 , , m }
y j { 0 , 1 } j { 1 , , m }
This is as far as I have gotten. I know I'm missing the connection between x i , j and y j . Also I'm not sure about my function I want to maximize. Help would be appreciated.

Answer & Explanation

teleriasacr

teleriasacr

Beginner2022-11-09Added 21 answers

Step 1
Your current model admits the possibility of a leader being assigned to another leader. You can eliminate this either by changing the first constraint to j ( x i , j + y i ) = 1 (leaders are not assigned to anyone) or by adding the constraint x i , i = y i i (leaders, and only leaders, are assigned to themselves).
Step 2
If the collaboration value of assigning someone to herself is not 0, you should use the second approach to ensure proper credit in the objective function.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?