Suppose we have an office with $n$ employees and we want to make a planning for the upcoming $T$ weeks. In each week there are $m_t, t\in \{1, 2, \ldots, T\},$ jobs to do.

Each employee can give a top three preferred jobs for each week. When there are no further constraints and $n = m_t$ one can easily solve this by the Hungarian algorithm.

However, I have some constraints:
1 - Each employee gets at least once a first choice.
2 - Each employee only gets preferred jobs.
3 - If the same job appears in several weeks, a employee can only be assigned once to this job
4 - Each job is done by at least $min_i$ employees and by at most $max_i$ employees. So these bounds can differ per job.

Furthermore, some employees do not have a preference and can be assigned to each job.

It is not that hard to model this as a MIP and solve it for example in AIMMS (AIMMS only needs less than a second). However, I want to solve it in C++11 without a 'black box' library to increase my knowledge of the problem and therefore I need to come up with the algorithm myself. My first thought was to solve it with a Branch-and-bound. However, I'm afraid that this will take too long since in the given instance we have $n \approx 450$, $m_t \approx 25$ $\forall t$, $min_i \approx 18$, $max_i = 22$, and $T = 3$. Assuming that each employee has three preferences this lead to a tree with $(T\cdot n)^{\# preferences} = (3\cdot 450)^3$ nodes, where the power is only three and not 25 due to the second constraint.

Does anyone know an algorithm to solve this problem? Or will a branch-and-bound be an option? But then the question arises, which bound to use?

Furthermore, I know that there is a feasible solution for my current instance. But is there a way to check this in advance?

Thanks in advance


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.