The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks.
Now consider the following generalization: Instead of specifying a cost of a single agent-task pair, assume that you can specify a cost of an arbitrary set of agent-task pairs. The problem is then defined by a set of constraints, where each constraint is a cost
c and a set
S of task-agent pairs. Meaning of a such constraint is that a cost
c occurs when all pairs in
S are "satisfied", and the overall cost is the sum of costs of all satisfied constraints.
Note that this problem can be encoded as Weighted Partial MAX-SAT, where hard clauses encode one-to-one assignment between agents and tasks, and each constraint is a (weighted) soft clause.
However, I am interested if this can be reduced to something simpler or if this is a known problem, but so far wasn't able to find an answer.
Thanks for your help.