The assignment problem is defined as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one task to each agent in such a way that the total cost of the assignment is minimized.

The number of tasks is larger than the number of agents.

My problem statement though imposes an additional constraint on the above.

Each task belongs to exactly one 'category'. Each 'category' has an associated maximum number of tasks that can be assigned. Enforce this constraint on the earlier definition.

For a layman's example, consider this -

A restaurant serves n customers (agents), and has on it's menu m possible dishes (tasks), with m > n. Each customer gives his preference for each of the m dishes, which is the cost for this particular assignment problem. Find a solution which minimizes cost i.e. which gives each customer a dish that is as high on their preference as possible.

Additionally, each dish belong to a certain cuisine (category). The restaurant can only make a certain number of dishes per cuisine. Enforce this constraint on the problem above.

I understand that this is a very specific problem, but any help would be appreciated.

I am currently solving the first part of the problem using the Hungarian Algorithm for assignment.

  • 2
    $\begingroup$ You should be able to reformulate this as a Maximum-Flow Problem $\endgroup$ – Francesco Gramano Jan 15 '15 at 18:45

Introduce dummy variables with zero cost so that it becomes a balanced assignment, which can be solved with Hungarian Algorithm.

| cite | improve this answer | |
  • $\begingroup$ Does not work for the additional constraint. $\endgroup$ – Rohan Sood Jul 5 '15 at 11:51

This can be formulated as an instance of minimum-cost flow problem. Have a graph with one vertex per agent, one vertex per task, and one vertex per category. Now add edges:

  • Add an edge from the source to each agent, with capacity 1 and cost 0.

  • Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment.

  • Add an edge from each task to the category it is part of, with capacity 1 and cost 0.

  • Add an edge from each category to the sink, with capacity given by the maximum number of tasks assignable in that category and cost 0.

Now find the minimum-cost flow of size $t$, where $t$ is the number of tasks. There are polynomial-time algorithms for that.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.