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.
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.