Implementing additional constraints in assignment problems.

5 views (last 30 days)
Dear all,
is there a standard function to solve assignment problems with extra constraints?
Example: You would like to assign classrooms to teachers.
Room 1 is available on monday from 7-9, 9-11 and 11-13 and also on tuesday from 9-11 and 11-13.
Room 2 is available on tuesday from 7-9
So you have in fact 6 classrooms.
There are 3 teachers.
Teacher A give his course 3 times a week,
Teacher B once a week,
Teacher C gives 2 different courses a week
Standard constraints for rowsums and column sums are well known.
Extra constraints:
Teacher A cannot be scheduled on one day
Teacher C can come only once a week to the institute (so both courses should be schedule on one day).
These extra constraints would tell me that the sum of all the diagonals within block of teacher A should each be less then or equal to zero. The sum of the diagonal of teacher C should be equal to 2.
How can I implement /add such constraints for solving assignment problem in matlab? The output should be such a schedule returning ones (assigned) and zeros (not assigned).
|-|MonRoom1_7-9|MonRoom1_9-11|MonRoom1_11-13|TueRoom1_9-11|TueRoom1_11-13|WedRoom2_7-9|
| -------- | -------- | ---------- | --------- | ---------- | ---------- | ---------- |
|A1| | | | | | |
|A2| | | | | | |
|A3| | | | | | |
|B1| | | | | | |
|C1| | | | | | |
|C2| | | | | | |
Let's say that the sum of the diagonals (inclusive, super and sub) should be less then 2. How can these constraints easily be concluded in the coding?

Answers (1)

John D'Errico
John D'Errico on 27 Oct 2021
Is there some general function that has been written to solve this problem? No. Of course not. Why not?
There is likely no unique solution that satisfies all of the constraints. Instead, there will almost always be multiple solutions, all of which are equally acceptable under the constraints supplied, or if not, then there will be no solution that satisfies everything. In the latter case, there is no indication provided in how to decide which of the constraints may be relaxed, and in what order of precedence.
So what can you do? You can learn how to use tools for optimization. In this case, it sounds like a binary integer programming tool might be appropriate. Will I teach you how to use such a tool to solve this problem? In NO way would I even attempt that, as it looks like you would need to spend a fair amount of time learning what an optimization tool does, and how it works. In turn, you would then learn how to formulate such a problem for the task at hand. And all of that would take far more than I would put into an answer. Effectively, one would need to teach an entire course on optimization, and an aswer is simply not the place to teach that much mathematics and theory. (Sorry, but this is what I read from the vagueness of your question.)
If I had to make a suggestion, what you need is to find a person, perhaps at a local university who already understands the use of optimization tools. It might be a grad student, for example, who is willing for some small compensation to help you to solve your problem. Or you can spend the time learning about how to formulate your problem in an integer programming context.
  1 Comment
Clarisha Nijman
Clarisha Nijman on 27 Oct 2021
Thank you for your advice John.
I think the part of the output confused you the most. It should be a table. For somebody who is used to solving assignment problems it could be clear that the output here is a table with indeed binary decission variables. Mine should be a table telling which classroom is assigned to which teacher. For example on Monday 7-9 room 1 is (or is not) assigned to teacher C1.
In fact we have to solve a far more bigger problem (6 days a week, each day 7 time periods, and more then 20 different classrooms). I just zoomed in on the part I need advice for.
I noticed an inbuilt function in r, in python and in excel for solving assignment problems. In excel I solved a miniproblem even with the extra constraints deduced from parts of the diagonals of the table with the decission variables. In my example some extra constraints for teacher A would be: x_11+x_22+x_33<=1, x_12+x_23<=1, x_21+x_32<=1, x_21+x_12<=1, ........, for teacher C: x_51+x_62=2, (relaxing on this point)
So the answer on my question is that matlab has an optimization toolbox to tackle assignment problems with additional constraints. I was looking for some function as linprog() or so.
Thank you for the eye opener that is new to me! We will explore this at the office.
kind regards.

Sign in to comment.

Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!