2
$\begingroup$

I am trying to solve an optimization problem (variation of assignment problem). I'm stuck with how to represent this problem (as an LP or graph based). If it's formulated as a LP, I'm unsure of how to formulate it. (I have limited Math knowledge, and it's been quite long so I really could use some help).
Assume there are some students, and some teachers. There are different types of students, say based on their subject preference. Similarly, there are different types of teachers, say based on their expertise (Science, Math etc.). Students and teachers can have multiple types. Also, each student and teacher type has certain minimum and maximum assignments possible. The total assignments required for each student and teacher is fixed. There is a cost associated with assigning any student and teacher (the fees). We need to minimize the total fees paid by all students combined


For example:
Student1_subject denotes the number of credits Student1 takes of subject. Similarly, Teacher1_subject denotes the number of credits (number of classes) the teacher teaches (with constraints) for subject. The fees matrix shows the fees paid by student_i to teacher_j. If Student_x is paired with Teacher_y, fees charged is as per the table. If student_x and teacher_y are not paired, then fees charged is 0.

$1 \leq student1_{science} \leq 3 ;\\$ $3 \leq student1_{math} \leq 5 ;\\$ $\sum_{subj = science, math} student1_{subj} = 5 ;\\$

$2 \leq student2_{science} \leq 4 ;\\$ $6 \leq student2_{math} \leq 10 ;\\$ $\sum_{subj = science, math} student2_{subj} = 11 ;\\$

$ \\\\$ $2 \leq teacher1_{science} \leq 2 ;\\$ $\sum_{subj = science} teacher1_{subj} = 2 ;\\$

$3 \leq teacher2_{science} \leq 5 ;\\$ $0 \leq teacher2_{math} \leq 2 ;\\$ $\sum_{subj = science, math} teacher2_{subj} = 4 ;\\$

$0 \leq teacher3_{science} \leq 5 ;\\$ $3 \leq teacher3_{math} \leq 5 ;\\$ $\sum_{subj = science, math} teacher3_{subj} = 5 ;\\$

Now the fee matrix is as follows:


               | Teacher1   | Teacher2 | Teacher3
Student1       |    10      |    15    |    30 
Student2       |    4       |    23    |    19 
Student3       |    12      |    32    |    56 

$$ min: \sum_{teacher=1}^3 \sum_{student=1}^2 fees_{student, teacher} $$ where $fees_{student, teacher}$ is equal to the corresponding value in table if $student$ and $teacher$ are paired, else 0.

We need to match these students and teachers together, ensuring that the total fees paid by all students combined is minimized. (Note: One pairing of teacher and student costs just once, not based on their capacities).

This is just an example of what I'm trying to do, but if I'm unclear, I could take another more detailed example.

$\endgroup$
  • $\begingroup$ What do you mean by something like "Teacher $i$ takes $x$ credits"? Is $x$ the number of classes they teach? Also, for Teacher 3, why not just say they need to take $4$ credits? Why bother with saying at least $3$ and at most $5$ if in the end the constraint is exactly $4$? I also don't understand the constraint for Teacher $2$: It seems you are saying that on one hand they need to take at least $5$ credits, but then also that the total must be exactly $4$ $\endgroup$ – Casteels May 13 '15 at 9:33
  • $\begingroup$ @Casteels: Thanks for the reply. I've changed the question to make it more clear. You're right, Teacher $i$ taking $x$ credits means the number of classes they teach. And I've updated the example to depict that teachers can have different capacities for different courses, but they need to take a total of $tot$ courses. Also, please note that if teacher and student are paired, they are charged just once (irrespective of the number of courses they teach) $\endgroup$ – amcoolguy May 13 '15 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.