# How can I solve this constrained assignment problem?

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.

• You should be able to reformulate this as a Maximum-Flow Problem – 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.

• Does not work for the additional constraint. – 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.

I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer. The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed.

• Could you please describe the branch and bound algorithm in detail? – xskxzr Sep 1 '20 at 1:12
• it is tree like method, based on : 1) solving a relaxation of your problem,, a good relaxation (without some complicating constraints). 2) setting up a branching criteria (a way how you construct the subproblems). You have to manage with bounds, upper and lowers bounds. There are ways to fathom (cut it out) a vertex or branch of the tree according to the bounds. if it is a min problem, then a lower bound is determined by the value obtained by solving the relaxed problem, and an upper bound is the value of any feasible solution (that satisfies all the constraints of the initial problem). – Rima Awhid Sep 2 '20 at 23:15